SoSe 18: Optimierung III
Ralf Borndörfer
Zusätzl. Angaben / Voraussetzungen
Zielgruppe
Diese Veranstaltung richtet sich an Studierende der Mathematik mit Vorkenntnissen in Linearer Algebra, Analysis, Linearer, Nicht-linearer und kombinatorischer Optmierung. Einige Übungsaufgaben erfordern den Einsatz eines Computers.
Weitere Informationen finden Sie auf der Homepage der Vorlesung: http://www.zib.de/ss17_Optimierung_III
SchließenKommentar
Diese Vorlesung ist der dritte Teil eines dreisemestrigen Zyklus. Teil III behandelt die gemischt-ganzzahlige Optimierung.
Inhalt
- Heuristiken: Einfache Scheduling-Probleme, Bin Packing, Ganzzahlige Programmierung, Eröffnungs- und Verbesserungsverfahren
- Gütemaße: Duale Heuristiken, Relaxierungen, Subdifferentialrechnung
- 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
- Min-Max Beziehungen: Polarität, Blocking und Antiblocking, Total duale Ganzzahligkeit
- Dekomposition: Lagrange-Relaxierung, Benders-Dekomposition
Literaturhinweise
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ßen27 Termine
Zusätzliche Termine
Fr, 12.10.2018 10:00 - 12:00Regelmäßige Termine der Lehrveranstaltung