Lineare und Ganzzahlige Optimierung(ADM II)
Skript
Rolf MöhringWS 2010/11
Contents
1-1
1. Einführung............................................................................................................................ 31.1 Algorithmische Diskrete Mathematik (ADM)
..................................................................................................................................................................... 41.2 Inhalt von ADM II................................................................................................................................................................... 51.3 VL im WS 2010/11
2. Optimierungsprobleme................................................................................................................................................................................... 72.1 Beispiele
...................................................................................................................................................................... 82.2 Nachbarschaften............................................................................................................................................ 92.3 Konvexe Mengen und Funktionen
............................................................................................................................................ 102.4 Konvexe Optimierungsprobleme3. Der Simplexalgorithmus
.......................................................................................................................... 123.1 Formen des Linearen Optimierungsproblem....................................................................................................................................................... 133.2 Zulässige Basislösungen
............................................................................................................................. 143.3 Die Geometrie von Linearen Programmen............................................................................................................... 153.4 Lokale Suche unter den zulässigen Basislösungen
........................................................................................................................................................ 163.5 Organisation in Tableaus................................................................................................................................................... 173.6 Wahl einer günstigen Spalte
........................................................................................................................................................ 183.7 Pivotregeln und Kreiseln........................................................................................................................................... 193.8 Phase I des Simplexalgorithmus
.............................................................................................................................. 203.9 Geometrische Aspekte beim Pivotisieren4. Dualität
.................................................................................................................................. 224.1 Dualität von LPs und der Dualitätssatz................................................................................................................... 234.2 Die Bedingungen vom komplementären Schlupf
............................................................................................... 244.3 Das Kürzeste-Wege-Problem und zugehörige duale Problem................................................................................................................................................................ 254.4 Das Farkas Lemma
................................................................................................................................................ 264.5 Duale Information im Tableau............................................................................................................................................... 274.6 Der duale Simplexalgorithmus
5. Berechnungsaspekte des Simplexalgorithmus............................................................................................................................................ 295.1 Das revidierte Simplexverfahren
..................................................................................... 305.2 Algorithmische Konsequenzen des revidierten Simplex Verfahrens....................................... 315.3 Lösung des Max-Fluss Problem mit dem revidierten Simplex Verfahren und Column Generation
Contents
1-2
............................................................................................... 325.4 Der Simplex Algorithmus mit unteren und oberen Schranken................................................................................................................ 335.5 Ein Spezialfall: Der Netzwerk-Simplexalgorithmus
6. Primal-duale Algorithmen.............................................................................................................................................................................. 356.1 Einführung
................................................................................................................................................. 366.2 Der primal-duale Algorithmus....................................................................................................................... 376.3 Bemerkungen zum primal-dualen Algorithmus
............................................................................................ 386.4 Ein primal-dualer Algorithmus für das Kürzeste-Wege-Problem....................................................................................................... 396.5 Ein primal-dualer Algorithmus für das Transportproblem
............................................................................................. 406.6 Ein primal-dualer Algorithmus für Weighted Matching (Skizze)7. Ganzzahlige Lineare Optimierung
.............................................................................................................................................................................. 427.1 Einführung.......................................................................................................................................... 437.2 Vollständig unimodulare Matrizen
.............................................................................................................................................. 447.3 Branch and Bound Algorithmen............................................................................................................................................................... 457.4 Lagrange Relaxation
......................................................................................................................................................... 467.5 Schnittebenenverfahren................................................................................................................................................. 477.6 Optimierung und Separierung
8. Von Kombinatorischen Optimierungsproblemen induzierte Polytope.............................................................................................................................................................................. 498.1 Einführung
............................................................................................................................................... 508.2 Einige lineare Beschreibungen
............................................................................................................................................... 518.3 Separierung und Branch & Cut9. LP-basierte Approximationsalgorithmen
................................................................................................... 539.1 Einfaches Runden und Verwendung von dualen Lösungen......................................................................................................................................................... 549.2 Randomisiertes Runden
............................................................................................ 559.3 Primal-duale Approximationsalgorithmen und Netzwerk Design10. Komplexität der Linearen Optimierung und Innere Punkte Methoden
............................................................................................................................................................. 5710.1 LP ist in NP ∩ coNP................................................................................................................................... 5810.2 Zur Laufzeit des Simplexalgorithmus
............................................................................................................................................................ 5910.3 Die Ellipsoidmethode...................................................................................................................................................... 6010.4 Innere Punkte Methoden
1. Einführung
2
............................................................................................................................... 31.1 Algorithmische Diskrete Mathematik (ADM)........................................................................................................................................................................ 41.2 Inhalt von ADM II...................................................................................................................................................................... 51.3 VL im WS 2010/11
1. Einführung1.1 Algorithmische Diskrete Mathematik (ADM)
3-1
…Zur Entstehung der ADM
Junges Gebiet, hat Wurzeln in
Algebra, Graphentheorie, Kombinatorik
Informatik (Algorithmik)
Optimierung
Behandelt Optimierungsfragen bei Diskreten Strukturen
Graphen, Netzwerke
endliche Lösungsmenge
Anwendungen
Telekommunikations- und Verkehrsnetze
Logistik, Produktionsplanung, Standortoptimierung
...
…Vorlesungszyklus ADM an der TU Berlin
Grundvorlesungen
Graphen- und Netzwerkalgorithmen (ADM I)
1. Einführung1.1 Algorithmische Diskrete Mathematik (ADM)
3-2
Lineare Optimierung (ADM II)
Vertiefung (ADM III) eine Vorlesung aus Katalog
Scheduling Probleme
Angewandte Netzwerkoptimierung
Polyedertheorie
...
Seminar (teils bereits parallel zu ADM II oder ADM III)
Bachelorarbeit
1. Einführung1.2 Inhalt von ADM II
4-1
…Lineare Optimierungsprobleme
lineare Zielfunktion, lineare Ungleichungen als Nebenbedingungen
Lineare Optimierung: min cTx unter Ax ! b, x " 0
Simplexalgorithmus
Dualität
Geometrie linearer Optimierungsprobleme
Ax ! b, x " 0 definieren Polyeder
1. Einführung1.2 Inhalt von ADM II
4-2
Optimum wird auf Ecke angenommen
Simplexalgorithmus durchläuft Ecken
1. Einführung1.2 Inhalt von ADM II
4-3
…Diskrete Probleme als Lineare Optimierungsprobleme
Polyedertheorie
diskrete Probleme als geometrische Probleme
minimal spannende Bäume als Vektoren
gegebener Graph G
1. Einführung1.2 Inhalt von ADM II
4-4
1 2
3
minimal spannende Bäume von G als Vektoren (Inzidenzvektoren)
2
3
1 2 1
3110
!101
!011
!
Konvexe Hülle der Inzidenzvektoren = Polytop (gelbe Menge)
Polytop = gelbe Menge
Ermittlung minimal spannender Baum = lineare Optimierung über diesem Polytop
1. Einführung1.2 Inhalt von ADM II
4-5
Ganzzahlige lineare Optimierung
Variablen dürfen nur ganzzahlige Werte annehmen
deutlich schwierigere Probleme
Lösungsverfahren
Lagrange Relaxation
Schnittebenenverfahren
LP-basierte Approximationsalgorithmen
...
Übungen mit Implementationsaufgaben
1. Einführung1.3 VL im WS 2010/11
5-1
Torsten Gellert (Übung)
Christoph Hansknecht (Tutorien)
Webseite zur VL
http://www.math.tu-berlin.de/coga/teaching/wt08/adm2/
http://www.math.tu-berlin.de/coga/teaching/wt10/adm2/
Notebook: http://www.math.tu-berlin.de/~moehring/adm2/
Literatur
C.#H. Papadimitriou and K.#Steiglitz
Combinatorial Optimization: Algorithms and Complexity
Prentice Hall, Englewood Cliffs, NJ, 1982
Taschenbuch - 512 Seiten - Dover Publications
Erscheinungsdatum: Juli 1998
Auflage: Unabridged
ISBN: 0486402584
B. Korte, J. Vygen:
Combinatorial Optimization: Theory and Algorithms
Springer, 2000/2002/2006/2008
1. Einführung1.3 VL im WS 2010/11
5-2
Springer, 2000/2002/2006/2008
jetzt auch auf deutsch
V.#Chvátal
Linear Programming
Freeman, New York, 1983
W. J. Cook, W. H. Cunningham, W. R. Pulleyblank und A. Schrijver
Combinatorial Optimization
Wiley 1998
G.#L. Nemhauser and L.#A. Wolsey
Integer and Combinatorial Optimization
John Wiley & Sons, New#York, 1988
M.#Grötschel, L.#Lovász, and A.#Schrijver
Geometric Algorithms and Combinatorial Optimization
Springer-Verlag, Berlin, 2nd#ed., 1993
D.#S. Hochbaum, ed.
Approximation Algorithms for NP-hard Problems
PWS Publishing Company, Boston, MA, 1997
1. Einführung1.3 VL im WS 2010/11
5-3
PWS Publishing Company, Boston, MA, 1997
H.#M. Salkin and K.#Mathur
Foundations of Integer Programming
North-Holland, Amsterdam, 1989.
R.#J. Vanderbei
Linear Programming: Foundations and Extensions
Kluwer Acad. Publ., Dordrecht, 2nd#ed., 2001.
http://www.princeton.edu/~rvdb/LPbook/index.html
als Enzyklopädie
A. Schrijver:
Combinatorial Optimization: Polyhedra and Efficiency
Springer, 2003
3 bändig mit 1881 Seiten, auch als CD erhältlich