|
|
Dr. Sigrid Knust, Christian Viergutz |
Einführung in die kombinatorische Optimierung SS 08 |
Inhalt:
|
Termine:
|
![[up]](images/up.png "nach oben")
:| Nr. | Abgabe | Blatt | Inhalt |
|---|---|---|---|
| 1 | 21.04.08 |  |
Fraktionales vs. binäres Rucksackproblem, Polynomiale Reduktionen, Vollst. Enumeration |
| 2 | 28.04.08 | |
Branch-and-Bound und dynamische Programmierung für das binäre Rucksackproblem Testinstanzen für P2 Lösungen zu den Testinstanzen Java-Programm (dyn. Progr.) |
| 3 | 05.05.08 | |
Nachbarschaften für lokale Suche, Genetische Algorithmen, Gütegarantien für Approximationsalgorithmen, Simulated Annealing |
| 4 | 13.05.08 | |
Modellierung mit LPs, Simplexverfahren |
| 5 | 19.05.08 | |
Resource-Investment-Problem, Lösbarkeit von LPs, Modellierung und Lösen mit Zimpl + SCIP/SoPlex |
| 6 | 26.05.08 | |
2-Phasen-Simplexverfahren, alternative Startbasis, Standortproblem |
| 7 | 02.06.08 | |
Dualität, IP-Modellierungstechniken |
| 8 | 09.06.08 | |
Erweiterte Verschnittprobleme, allgemeine lineare Programme |
| 9 | 16.06.08 | |
Matrixspiele, optimale Spielstrategien |
| 10 | 23.06.08 | |
Zwei-Personen-Spiele, Equilibria in Nicht-Nullsummenspielen, Branch-and-Bound für IPs |
| 11 | 30.06.08 | |
Netzwerk-Fluss-Probleme |
| 12 | 04.07.08 (!) | |
Klausuraufgabe, Max-Fluss-Problem, Algorithmus von Ford & Fulkerson (A31 korrigiert am 26.6.08) Netzwerke flow1-5.net für P6 |
Zur Abgabe der praktischen Aufgaben:
Geben Sie bei praktischen Aufgaben bitte einen Ausdruck des von Ihnen erstellten Textes (Programme,
Quellcode etc.) zusammen mit den theoretischen Aufgaben ab. Schicken sie zusätzlich eine
lauffähige Version Ihres Programms per Email an Ihre(n) Tutor(in):
Elisabeth Schumacher
bzw. Rolf Wendt
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.
:::