19235801
Vorlesung
WiSe 17/18: Optimierung II
Ralf Borndörfer
Zusätzl. Angaben / Voraussetzungen
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
SchließenKommentar
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
Literaturhinweise
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
Schließen32 Termine
Regelmäßige Termine der Lehrveranstaltung
Mo, 16.10.2017 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.
Mo, 23.10.2017 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.
Mo, 30.10.2017 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.
Mo, 06.11.2017 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.
Mo, 13.11.2017 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.
Mo, 20.11.2017 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.
Mo, 27.11.2017 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.
Mo, 04.12.2017 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.
Mo, 11.12.2017 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.
Mo, 18.12.2017 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.
Mo, 08.01.2018 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.
Mo, 15.01.2018 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.
Mo, 22.01.2018 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.
Mo, 29.01.2018 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.
Mo, 05.02.2018 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.
Mo, 12.02.2018 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.
Mi, 18.10.2017 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.
Mi, 25.10.2017 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.
Mi, 01.11.2017 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.
Mi, 08.11.2017 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.
Mi, 15.11.2017 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.
Mi, 22.11.2017 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.
Mi, 29.11.2017 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.
Mi, 06.12.2017 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.
Mi, 13.12.2017 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.
Mi, 20.12.2017 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.
Mi, 10.01.2018 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.
Mi, 17.01.2018 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.
Mi, 24.01.2018 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.
Mi, 31.01.2018 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.
Mi, 07.02.2018 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.
Mi, 14.02.2018 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.