Prof. Dr. Sigrid Knust, Dipl.-Math. Stefan Waldherr
	Einführung in die Kombinatorische Optimierung SS 11

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

Termine: Vorlesung: Tag Zeit Raum Mo 12:15-13:45 69/125 Di 14:15-15:45 32/107 Übung: Tag Zeit Raum Do 12:15-13:45 69/125 Klausur: Tag Zeit Raum 12.07.11 14:00-16:00 35/E23-E24

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.
Hier finden Sie die aktuellen Versionen von Zimpl und SCIP zur Benutzung auf dem eigenen Computer. Um Zimpl bzw. SCIP in allen Verzeichnissen ausführen zu können, müssen Sie das Installationsverzeichnis in der PATH Variable hinzufügen. Eine Beschreibung dazu finden Sie z.B. hier

Material zur Vorlesung :

• Folien: Organisatorisches, Themenüberblick und Lernziele
• ZIB Optimization Suite (enthält Zimpl, SCIP und SoPlex)
• 1. Übung, Einführung in Zimpl

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 :