Dr. Sigrid Knust, Christian Viergutz
	Einführung in die Kombinatorische Optimierung SS 08

Inhalt: Einführung in Grundbegriffe der kombinatorischen Optimierung Lineare Programmierung Ganzzahlige lineare Programmierung Netzflussalgorithmen Branch-and-Bound-Algorithmen Lokale Suchverfahren Praxisbeispiele

Termine: Vorlesung: Sigrid Knust Tag Zeit Raum Mo 12:15-13:45 31/E05 Mi 10:15-11:45 31/E05 Übung: Christian Viergutz Tag Zeit Raum Fr 14:00-15:30 69/E18

Formulieren und Lösen von LPs und MIPs:
Zur Lösung von LP- und MIP-Problemen soll in den Übungen die ZIB Optimization Suite eingesetzt werden, die die Programme Zimpl, SCIP und SoPlex enthält. Diese sind für den akademischen Einsatz frei verfügbar.
Zimpl dient zur Modellierung von LPs und MIPs und bietet eine mächtige formale Eingabesprache, aus der Eingabeformate für das anschließende Lösen mit LP- bzw. MIP-Solvern (wie SCIP/SoPlex) generiert werden können.
SCIP (Solving Constraint Integer Programs) ist ein Löser für gemischt-ganzzahlige lineare Programme, der intern einen LP-Löser benötigt, wobei standardmäßig SoPlex zum Einsatz kommt (was aber modular austauschbar ist).
Die Programme sind auf den Rechnern im CIP-Pool (31/339) installiert; wer möchte, kann sie aber auch auf dem eigenen Computer verwenden. Die Verwendung unter Windows XP/Vista ist evtl. über Cygwin oder MinGW möglich.

Material zur Vorlesung :

• Folien: Organisatorisches, Themenüberblick und Lernziele
• Errata zum gedruckten Skript
• ZIB Optimization Suite (enthält Zimpl, SCIP und SoPlex)
• Folien vom 14.5.08 (LPs, Simplexalgorithmus und Zimpl-Einführung)
• Lösung zu Aufgabe 20 (allgemeines LP)
• Lösung zu Aufgabe 29b (Min-Fluss-Problem)
• Lösung zu Aufgabe 31 (Transportnetzwerk)

Literatur:

• E.H.L. Aarts, J.K. Lenstra: Local Search in Combinatorial Optimization, John Wiley, 1997.
• R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows, Prentice Hall, 1993
• P. Brucker, S. Knust: Complex Scheduling, Springer, 2006.
• V. Chvatal: Linear Programming, W.H. Freeman and Company, New York - San Francisco, 1983.
• W. Domschke, A. Drexl: Einführung in Operations Research, Springer, 7. Auflage, 2007.
• M. Garey, D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
• T. Grünert, S. Irnich: Optimierung im Transport, Shaker, 2005.
• K. Neumann, M. Morlock: Operations Research, Hanser, 2. Auflage, 2002.
• C.H. Papadimitriou, K. Steiglitz: Combinatorial Optimization, Prentice Hall, Englewood Cliffs, N.J., 1982.
• A. Schrijver: Combinatorial Optimization, Springer, 2003.
• R. Vanderbei: Linear Programming, Foundations and Extensions Springer, 2. Auflage, 2001.
• Vanderbei: LP
• Maximale Flüsse

Teilnahme :

Schein :