19235801
Lecture
WiSe 17/18: Optimierung II
Ralf Borndörfer
Additional information / Pre-requisites
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.
Weitere Informationen finden Sie auf der Homepage der Vorlesung: http://www.zib.de/ws17_Optimierung_II
closeComments
Diese Vorlesung ist der zweite Teil eines dreisemestrigen Zyklus. Teil II behandelt die kombinatorische und gemischt-ganzzahlige Optimierung. Die Vorlesung ist auf Englisch.
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
Suggested reading
Literatur
M. Grötschel, Einführung in die Lineare und Kombinatorische Optimierung, eines der Vorlesungsskripte
A. Schrijver, Throry of Linear and Integer Programming, Wiley, 1986
G. Nemhauser, L. Wolsey, Integer and Combinatorial Optimization, Wiley, 1999
B. Korte, J. Vygen, Combinatorial Optimization, Springer, 2012
close32 Class schedule
Regular appointments
Mon, 2017-10-16 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2017-10-23 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2017-10-30 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2017-11-06 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2017-11-13 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2017-11-20 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2017-11-27 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2017-12-04 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17 findet die Veranstaltung im SR 053 in der Takustr. 9 statt.
Mon, 2017-12-11 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2017-12-18 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2018-01-08 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2018-01-15 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2018-01-22 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2018-01-29 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2018-02-05 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Mon, 2018-02-12 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-10-18 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-10-25 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-11-01 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-11-08 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-11-15 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-11-22 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-11-29 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-12-06 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-12-13 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2017-12-20 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2018-01-10 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2018-01-17 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2018-01-24 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2018-01-31 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2018-02-07 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.
Wed, 2018-02-14 10:00 - 12:00
Die Veranstaltung findet immer Mo und Mi von 10-12 im ZIB Hörsaal statt außer am Mo, dem 04.12.17.