Operations Research II: Einführung in die kombinatorische Optimierung
	Vorlesung im Wintersemester 2015/16
	Dozent: Peter Becker
	Studiengang: Bachelor Informatik, 5. Semester, Wahlpflicht

Vorlesungsankündigung

Unterlagen zur Vorlesung

1. Unimodularität

   • Vorbemerkungen
   • Wiederholung: Transport- und Zuordnungsprobleme
   • u-v-Methode, Zuordnungsproblem
   • Total unimodulare Matrizen, Inzidenzmatrix
   • Optimierungsprobleme auf Graphen
   • Maximalflussproblem aus Beispiel 1.25 als LP (CPLEX-Format)
   • Weitere Quellen:
     • Wikipedia: Transportproblem
     • Wikipedia: Zuordnungsproblem
     • Wikipedia: LP-Relaxation
     • Wikipedia: Total unimodulare Matrix
     • Wikipedia: Inzidenzmatrix
     • Wikipedia: Flüsse und Schnitte in Netzwerken
     • Wikipedia: Min-Cost-Flow-Problem
     • Wikipedia: Max-Flow-Min-Cut-Theorem
     • Wikipedia: Algorithmus von Ford und Fulkerson
     • Wikipedia: Algorithmus von Edmonds und Karp

2. Schnittebenenverfahren

   • Schnittebenen, Konstruktion, Auswahl
   • Weitere Quellen:
     • Wikipedia: Ganzzahlige Lineare Optimierung
     • Wikipedia: Schnittebenenverfahren

3. Branch-and-Bound und Varianten

   • Branch-and-Bound
   • Anwendungsbeispiele
   • Branch-and-Cut
   • Beispiel 3.17, 1. LP-Relaxation
   • Beispiel 3.17, 2. LP-Relaxation
   • Beispiel 3.17, 3. LP-Relaxation
   • Beispiel 3.17, 4. LP-Relaxation
   • Beispiel 3.17, 5. LP-Relaxation
   • Beispiel 3.17, 6. LP-Relaxation
   • Weitere Quellen:
     • Wikipedia: Branch-and-Bound
     • Wikipedia: Branch-and-Cut
     • Wikipedia: Problem des Handlungsreisenden

4. Dynamische Programmierung

   • Dynamische Optimierung, Bellmansches Optimalitätsprinzip
   • Stochastische dynamische Optimierung
   • Beispiel: Berechnung der Levenshtein-Distanz
   • Weitere Quellen:
     • Richard Bellman on the Birth of Dynamic Programming, von S. Dreyfus, Operations Research, Vol. 50 (1), S. 48-51, 2002.
     • Wikipedia: Dynamische Programmierung
     • Wikipedia: Optimalitätsprinzip von Bellman
     • Wikipedia: Bellman-Ford-Algorithmus

5. Matroide und Heuristiken

   • Weitere Quellen:
     • Wikipedia: Unabhängigkeitssystem
     • Wikipedia: Matroid
     • Wikipedia: Greedy-Algorithmus
     • Wikipedia: Algorithmus von Christofides

Übungen

• Blatt 1 (06.10.2015)
• Blatt 2 (13.10.2015)
• Blatt 3 (20.10.2015)
• Blatt 4 (29.10.2015)
• Blatt 5 (14.11.2015)
• Blatt 6 (17.11.2015)
• Blatt 7 (29.11.2015)
• Blatt 8 (04.12.2015)
  • LP-Relaxation zu Aufgabe 2
• Blatt 9 (04.01.2016)
• Blatt 10 (10.01.2016)

Literatur

Softwarewerkzeuge

• GNU Linear Programming Toolkit (GLPK)
• lp_solve Open Source LP-Solver
• LINGO von LINDO Systems Inc., Trial Versionen verfügbar
• Gurobi Optimizer Der zur Zeit wohl beste kommerzielle LP-Solver.
• IBM ILOG CPLEX Weit verbreiteter LP-Optimizer von IBM.