We decided to put Exercise 5 as a bonus exercise. The review will take place on Tuesday, October 27th, 13:00 at ZIB (together with the Opti2 review).
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)