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 mit integrierter Übung:

• Montag, 11:15-12:45, G02-020
• Dienstag, 9:15-10:45, G03-214

Eintrag im LSF

(Campus-Plan)

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

• Handschriftlicher Teil 02.04.
• Handschriftlicher Teil 08.04.
• Handschriftlicher Teil 09.04.
• (15.04. Vertretung durch Jonas Frede, Tafelanschrieb)
• (16.04. Übung, Vertretung durch Mirjam Friesen)
• Handschriftlicher Teil 23.04.
• Handschriftlicher Teil 29.04.
• Handschriftlicher Teil 30.04.
• Handschriftlicher Teil 06.05.
• Handschriftlicher Teil 07.05.
• Handschriftlicher Teil 20.05.
• Handschriftlicher Teil 21.05.
• Handschriftlicher Teil 27.05.
• Handschriftlicher Teil 03.06.
• Handschriftlicher Teil 04.06.
• Handschriftlicher Teil 11.06.
• Handschriftlicher Teil 17.06.
• Handschriftlicher Teil 18.06.
• Handschriftlicher Teil 24.06.
• Handschriftlicher Teil 25.06.
• Handschriftlicher Teil 01.07.

Übungsblätter

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

• 1. Übungsblatt (Besprechung am Dienstag, 16.4.)
• 2. Übungsblatt (Besprechung am Dienstag, 28.5.)
• 3. Übungsblatt (Besprechung am Dienstag, 2.7.)

Literatur

• A. Schrijver: Theory of linear and integer programming. Wiley 1986
• G. Nemhauser, L. Wolsey: Integer and Combinatorial Optimization. Wiley 1988 (Paperback 1999)
• D. Bertsimas, R. Weismantel: Optimization over Integers. Dynamic Ideas, Belmont, MA 2005
• L. A. Wolsey: Integer Programming. Wiley 1998