Lectures and additional material are available via the FU box-cloud:

https://box.fu-berlin.de/s/KKirGQ97PtGam4z

 

 

 

Diese Vorlesung führt in die Ganzzahlige Optimierung ein.

Inhalt

Woche 1 (Ganzzahlige Optimierungsprobleme): Einführung, Definitionen, Beispiele

Woche 2 (Branch-and-Bound): LP-Relaxierung, Baumsuche

Woche 3 (Relaxierungen): Untere Schranken, Lagrange-Relaxierung

Woche 4 (Primalheuristiken): Eröffnungs- und Verbesserungsverfahren, Approximation, Beispiele

Woche 5 (Ganzzahlige Punkte in Rationalen Polyedern): Ganzzahlige Polyeder, Ganzzahlige Punkte in Rationalen Polyedren, Komplexität

Woche 6 (Schnittebenentheorie): Elementarer Abschluss, Rang

Woche 7 (Schnittebenenverfahren für IPs): Gomory-Schnitte 1. Art

Woche 8 (Schnittebenenverfahren für MIPs): Gomory-Schnitte 2. Art

Woche 9 (Polyedrische Kombinatorik): Matroid-Polytop

Woche 10 (Polyedrische Kombinatorik): Matching-Polytop

Woche 11 (Polyedrische Kombinatorik): TSP-Polytop

Woche 12 (Allgemeines Schnittebenenverfahren): Äquivalenz von Separierung und Optimierung

Woche 13 (Schnittebenenverfahren): Implementation (Tricks)

Week 14: Klausur

 

Literatur

 

G. Nemhauser, L. Wolsey, Integer and Combinatorial Optimization, Wiley 1988

L. Schrijver, Combinatorial Optimization, Springer 2003

B. Korte, J. Vygen, Combinatorial Optimization, Springer 2018

V. Chvátal, Linear Programming, Freeman 1983

 

Zusätzliche Informationen

Diese Vorlesung ist eine Forsetzung von Optimierung I.

Voraussetzungen: Diskrete Mathematik I, Algorithmische Graphentheorie, Lineare Programmierung.

Einge Übungen erfordern elementare Programmierkenntnisse.

Die Klausur findet in der letzten Vorlesung statt.

Die Nachklausur findet in der letzten Woche vor dem Wiederbeginn der Vorlesungen statt.

Das Hausaufgabenkriterium ist 50%/ To pass the course you'll need 50% of the points on the exercise sheets (cumulative)