Ganzzahlige Lineare Optimierung (SoSe 2013)

Inhalt

Thema der Vorlesung werden Strukturresultate und Algorithmen für das Optimieren linearer Zielfunktionen über den ganzzahligen Punkten eines durch lineare Ungleichungen beschriebenen Polyeders sein (Integer Linear Programming, ILP). Im Gegensatz zu den Untersuchungen in der Kombinatorischen Optimierung steht jetzt die Situation im Vordergrund, dass über die Lösungen nichts bekannt ist als ein sie beschreibendes Ungleichungssystem. Daher werden Methoden der (Linearen) Algebra die Hauptrolle spielen.

Das Themenspektrum umfasst Gitter und lineare Diophantische Gleichungssysteme, Gitterbasis-Reduktion und Lenstras in fester Dimension polynomialen ILP-Algorithmus, Hilbert-Basen und total duale Ganzzahligkeit, Chvatal-Gomory Abschluss und Schnittebenen für gemischt-ganzzahlige lineare Optimierung (MIP).

Termine

Vorlesung / Übung (Prof. V. Kaibel); Eintrag im LSF

(Campus-Plan)

Übungsblätter

In etwa zweiwöchigen Abständen werden Übungsblätter ausgeteilt, deren Lösungen dann jeweils in einer Vorlesungsstunde besprochen werden.

Literatur

Die Folien zum Vortrag über den Test auf totale Unimodularität gibt es hier.