SoSe 18: Optimierung III
Ralf Borndörfer
Additional information / Pre-requisites
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
closeComments
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
Suggested reading
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
close27 Class schedule
Additional appointments
Fri, 2018-10-12 10:00 - 12:00Regular appointments