Diese Vorlesung ist der zweite Teil eines dreisemestrigen Zyklus. Teil II behandelt die kombinatorische und gemischt-ganzzahlige Optimierung. Die Vorlesung ist auf Englisch.

Inhalt

1. Grundlagen der Nichtlinearen Optimierung: Quadratische Optimierungsprobleme, Behandlung von Gleichungen, Behandlung von Ungleichungen mit der Active Set Methode
2. Innere-Punkte-Verfahren: Karmarkar-Algorithmus, Barriere-Methoden, zentraler Pfad
3. Ellipsoidmethode: Löwner-John-Ellipsoid, Lineare Optimierung
4. Grundlagen: Problemformulierungen, Beispiele und Anwendungen, Kombinatorische Optimierungsprobleme, Graphentheorie, Datenstrukturen zur Speicherung von Graphen
5. Komplexität: Komplexitätsmaße, Laufzeit von Algorithmen, die Klassen P und NP, NP-Vollständigkeit
6. Bäume und Branchings: Bäume, Wälder, Branchings, Arboreszenzen
7. Matroide und Unabhängigkeitssysteme: Unabhängigkeitssysteme, Matroide, Orakel, Optimierung über Unabhängigkeitssystemen
8. Kürzeste Wege: Nichtnegative Gewichte, allgemeine Gewichte, all pairs
9. Netzwerflüsse: Das Max-Flow-Min-Cut Theorem, Augmentierende Wege, Minimalkostenflüsse, Transport- und Zuordnungsprobleme
10. Heuristiken: Einfache Scheduling-Probleme, Bin Packing, Ganzzahlige Programmierung, Eröffnungs- und Verbesserungsverfahren, Gütemaße, Duale Heuristiken, Relaxierungen
11. Das Rucksackproblem
12. Branch-and-Bound-Verfahren
13. Ganzzahlige Programmierung: Ganzzahlige Punkte in rationalen Polyedern, Schnittebenenverfahren für ganzahlige und gemischt-ganzzahlige Probleme, Separierung und Optimierung
14. Polyedrische Kombinatorik: Theorie, Beispiel