Diese Vorlesung ist der dritte Teil eines dreisemestrigen Zyklus. Teil III behandelt die gemischt-ganzzahlige Optimierung.

Inhalt

1. Heuristiken: Einfache Scheduling-Probleme, Bin Packing, Ganzzahlige Programmierung, Eröffnungs- und Verbesserungsverfahren
2. Gütemaße: Duale Heuristiken, Relaxierungen, Subdifferentialrechnung
3. Das Rucksackproblem
4. Branch-and-Bound-Verfahren
5. Ganzzahlige Programmierung: Ganzzahlige Punkte in rationalen Polyedern, Schnittebenenverfahren für ganzahlige und gemischt-ganzzahlige Probleme, Separierung und Optimierung
6. Polyedrische Kombinatorik: Theorie, Beispiel
7. Min-Max Beziehungen: Polarität, Blocking und Antiblocking, Total duale Ganzzahligkeit
8. Dekomposition: Lagrange-Relaxierung, Benders-Dekomposition

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

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