WiSe17/18: Optimization II

News

16.02.18 The second exam will take place on Thursday the 12th of April, 10:00-12:00, in the ZiB Seminar Room (besides the lecture hall).

20.02.18 There will be a seminar on Shortest Path Problems and a lecture on Public Transportation Networks next semester

Seminar: http://www.zib.de/node/3446

Lecture: http://www.zib.de/node/3447

Diese Vorlesung ist der zweite Teil eines dreisemestrigen Zyklus. Teil II behandelt die Ganzzahlige Optimierung.

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

 Zielgruppe

Diese Veranstaltung richtet sich an Studierende der Mathematik mit Vorkenntnissen in Linearer Algebra, Analysis, Linearer und nicht-linearer Optmierung. Einige Übungsaufgaben erfordern den Einsatz eines Computers.