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
- Grundlagen der Nichtlinearen Optimierung: Quadratische Optimierungsprobleme, Behandlung von Gleichungen, Behandlung von Ungleichungen mit der Active Set Methode
- Innere-Punkte-Verfahren: Karmarkar-Algorithmus, Barriere-Methoden, zentraler Pfad
- Ellipsoidmethode: Löwner-John-Ellipsoid, Lineare Optimierung
- Grundlagen: Problemformulierungen, Beispiele und Anwendungen, Kombinatorische Optimierungsprobleme, Graphentheorie, Datenstrukturen zur Speicherung von Graphen
- Komplexität: Komplexitätsmaße, Laufzeit von Algorithmen, die Klassen P und NP, NP-Vollständigkeit
- Bäume und Branchings: Bäume, Wälder, Branchings, Arboreszenzen
- Matroide und Unabhängigkeitssysteme: Unabhängigkeitssysteme, Matroide, Orakel, Optimierung über Unabhängigkeitssystemen
- Kürzeste Wege: Nichtnegative Gewichte, allgemeine Gewichte, all pairs
- Netzwerflüsse: Das Max-Flow-Min-Cut Theorem, Augmentierende Wege, Minimalkostenflüsse, Transport- und Zuordnungsprobleme
- Heuristiken: Einfache Scheduling-Probleme, Bin Packing, Ganzzahlige Programmierung, Eröffnungs- und Verbesserungsverfahren, Gütemaße, Duale Heuristiken, Relaxierungen
- Das Rucksackproblem
- Branch-and-Bound-Verfahren
- Ganzzahlige Programmierung: Ganzzahlige Punkte in rationalen Polyedern, Schnittebenenverfahren für ganzahlige und gemischt-ganzzahlige Probleme, Separierung und Optimierung
- 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.
M. Grötschel, Lineare Optimierung, eines der Vorlesungsskripte
V. Chvátal, Linear Programming, Freeman 1983
G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963
R. Rockafellar, Convex Analysis, Princeton University Press, 1970
Nemhauser, George L., and Laurence A. Wolsey. Integer programming and combinatorial optimization, 1988.
B. Korte, J. Vygen. Combinatorial Optimization, 2000. (German Edition: Kombinatorische Optimierung)
Vorlesung | Mo, 10-12 | Takustr. 7, ZIB Hörsaal |
Vorlesung | Mi, 10-12 | Takustr. 7, ZIB Hörsaal |
Übung | Tu, 14-16 | Arnimallee 6, SR 031 |
Bei Fragen zu dieser Veranstaltung kontaktieren Sie bitte Isabel Beckenbach (siehe unten).
Sprechstunde | Raum | Telefon | ||
Prof. Dr. Ralf Borndörfer | auf Anfrage | ZIB 3033 | 84185 - 243 | borndoerfer |
Isabel Beckenbach | auf Anfrage | ZIB 3301 | 84185 - 134 | beckenbach |