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

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.