Vorlesung Ganzzahlige Lineare Optimierung (SS 10)

>> Eintrag im

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, Lift-and-Project, Lovasz-Schrijver Hierarchie, Schnittebenen für gemischt-ganzzahlige lineare Optimierung (MIP), Praktische Aspekte moderner MIP-Löser und eventuell Erzeugendenfunktionen der ganzzahligen Punkte in Polyedern.

Termine

Keine Vorlesung:

Statt dessen Vorlesung 7:30-9:00 in G03-214:

(Campus-Plan)

Über das Semester verteilt werden einige der Vorlesungstermine als Übungsstunden verwendet. Dafür wird jeweis eine Woche zuvor ein Aufgabenblatt verteilt.

Folien

Die in Kapitel 8 verwendeten Folien finden Sie hier.

Übungsblätter

Literatur