Ganzzahlige Lineare Optimierung (SoSe 2017)

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)

Nach jeder Vorlesung stelle ich hier den in der Vorlesung erzeugten handschriftlichen Teil (ersetzt einen Tafelanschrieb) zur Verfügung:

Übungsblätter

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

Literatur