Fortgeschrittene Methoden der Ganzzahligen Linearen Programmierung (SS07)

(ADM III)

Sommersemester 2007

LV-Nr.: 0230 L 233

Inhalt

Die Vorlesung ist der dritte Teil des Zyklus "Algorithmische Diskrete Mathematik". Das zentrale Thema lautet: Wie löst man wirklich große (gemischt-)ganzzahlige Programe (mit mehreren Millionen Variablen und/oder Nebenbedingungen) optimal oder nahezu optimal in der Theorie und in der Praxis? Welche neuen Methoden könnten in der Zukunft helfen, solche Problem noch besser zu lösen? Die derzeit gängigen Methoden zur Behandlung sehr großer ganzzahliger Programme sind Schnittebenen- und Column-Generation-Verfahren, die auf polyedrischer Kombinatorik und LP-Theorie basieren. Diese Themen werden ausführlich und anhand konkreter Anwendungsbeispiele behandelt. Neuere Ideen sind Lift-and-Project, Testmengen und andere primale Verfahren sowie Gitterbasis-Reduktion. Diese Methoden werden kurz erläutert. Daneben wird es voraussichtlich kuze Abrisse der kombinatorischen Online-Optimierung und eine Einführung in kombinatorische Optimierung mit mehren gleichzeitigen Zielfunktionen geben (Pareto-Mengen etc.).

Language

There have been requests from foreign students visiting TU Berlin to give this class in English. This issue will be resolved during the first lecture on Wednesday, April 18, starting at 10:15 in room MA 313. If students show up with an insufficient command of German the lectures will be in English.

Voraussetzungen:

In der Vorlesung werden Kenntnisse der linearen Optimierung und der Graphentheorie in dem Umfang vorausgesetzt, wie diese Gebiete in den beiden Vorgängervorlesungen ADM I und ADM II gelehrt wurden.

Übungen

Ein wichtiges Ziel der Veranstaltung ist, praktische Kenntnisse in den behandelten Methoden zu vermitteln. Daher werden zusätzliche Übungen angeboten, die teilweise am PC durchgeführt werden. Schwerpunkte sind

Modellierung mit der Modellierungssprache ZIMPL zur Bewertung verschiedener Modelle
Implementierung von problemspezifischen Cutting Planes im MIP-Framework SCIP
Implementierung von Column-Generation-Verfahren im MIP-Framework SCIP

Die Implementierung soll in C++ erfolgen. Um den Implementierungsaufwand gering zu halten, sollen Algorithmen aus der C++-Graphen-Bibliothek von Boost verwendet werden.

Literatur

R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows: Theory, Algorithms, and Applications , Prentice-Hall, 1993
D. L. Applegate, R. E. Bixby, V. Chvátal, W. J. Cook: The Traveling Salesman Problem: A Computational Study , Princeton University Press, 2006
D. Bertsimas, R. Weismantel: Optimization over Integers , Dynamic Ideas, Belmont, Massachusetts, 2005
W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver: Combinatorial Optimization , Wiley, 1998
G. Desaulniers, J. Desrosiers, M. M. Solomon (eds): Column Generation , Springer, 2005
M. Grötschel, L. Lovasz: Combinatorial Optimization , in R. L. Graham, M. Grötschel, L. Lovasz: "Handbook of Combinatorics", Band 2, Amsterdam, North-Holland, 1995, S. 1541-1597
M. Grötschel, L. Lovasz, A. Schrijver Geometric Algorithms and Combinatorial Optimization , second corrected edition, Algorithms and Combinatorics 2, Springer, 1993.
B. Korte, J. Vygen: Combinatorial Optimization , Theory and Algorithms, Springer, 2000 (3. Auflage, 2006)
A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency (3 volumes) , Springer, 2003 (auch verfügbar auf CD-ROM)

Zeiten

Vorlesung:	Mi	10:15 - 11:45	MA 313	Prof. Dr. Martin Grötschel
Vorlesung:	Mi	14:15 - 15:45	MA 313	Prof. Dr. Martin Grötschel
Übung:	Do	8:15 - 9:45	MA 313	Andreas Bley, Benjamin Hiller

Vorlesungsbeginn ist am 18.04.2007.

Kontakte

		Sprechstunde	Raum	Telefon	email
Dozent:	Prof. Dr. Martin Grötschel	n.V.	MA 302	84185-210	groetschelzib.de
Assistent:	Andreas Bley	n.V.	ZIB 3106	80185-229	bleyzib.de
Assistent:	Benjamin Hiller	n.V.	ZIB 3101	80185-406	hillerzib.de

Material for lectures

Book chapter on polyhedral combinatorics of the TSP (M. Grötschel, M. W. Padberg: Polyhedral theory, in: The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization, 1985.)
Slides of Timo Berthold's talk on SCIP and primal heuristics in SCIP
Slides of Kati Wolter's talk on cutting planes in SCIP

Material for exercises

Zuletzt aktualisiert: $Date: 2007-07-04 18:09:32 +0200 (Mi, 04 Jul 2007) $