Computerpraktikum zur Optimierung 2

Homepage zur Optimierung 2

Personen und Sprechstunden ↑

Dozent:	Dipl.-Math. Michael Ritter

Aktuelles ↑

• 07. Januar 2009: Das Blockpraktikum findet voraussichtlich in der Zeit vom 19. Februar 2009 bis zum 24. Februar 2009 statt (4 Termine zu je 3 vollen Stunden). Wenn Sie am Blockpraktikum teilnehmen möchten, melden Sie sich bitte möglichst bis zum 16. Januar 2009 per E-Mail an m.ritterma.tum.de an (mit Name und Matrikelnummer). Falls Sie gerne teilnehmen möchten, mit dem Zeitraum aber Terminprobleme haben, teilen Sie mir das bitte ebenfalls per E-Mail mit, evtl. lässt sich noch eine Ausweichmöglichkeit finden.
• 22. Oktober 2008: Erster Termin fürs Computerpraktikum: Mittwoch, 29. Oktober 2008.
• 22. Oktober 2008: In der Rechnerhalle wurde ein Update für XpressMP eingespielt, dort ist ab sofort (nur noch) die Version 2008A verfügbar.
• 02. Oktober 2008: Die Ergebnisse der Evaluierung vom Sommersemester 2008 können Sie hier einsehen. Vielen Dank für Ihre Teilnahme!

Termine ↑

Das Computerpraktikum findet während des Semesters in Form einer Vorlesung statt. Zu Beginn der Semesterferien wird es dann ein mehrtägiges Blockpraktikum geben, in dem Sie die Kenntnisse aus der Vorlesung in praktischen Übungen am Rechner umsetzen können.

Termine für Sprechstunden finden Sie auf der Homepage zur Optimierung 2.

Termine für die Vorlesung ↑

Datum	Uhrzeit	Raum	Thema
29.10.2008	14:15 - 15:45	MI 00.07.011	Spannbäume und Steinerbäume, Teil 1
12.11.2008	14:00 - 15:30	MI 00.07.011	Spannbäume und Steinerbäume, Teil 2
26.11.2008	14:00 - 15:30	MI 00.07.011	Spannbäume und Steinerbäume, Teil 3
10.12.2008	14:00 - 15:30	MI 00.07.011	Routenplanung, kürzeste Wege
17.12.2008	14:00 - 15:30	MI 00.07.011	tba
07.01.2009	14:00 - 15:30	MI 00.07.011	Schnittebenen und Knapsack Cover Inequalities

Termine fürs Blockpraktikum ↑

Das Blockpraktikum fand in der Zeit vom 25. bis zum 27. Februar 2009 an drei Terminen zu je 4 vollen Stunden statt.

Material zu den Vorlesungen ↑

Übungsblätter und Lösungen ↑

• CPBlatt01.pdf: Blatt 1 - Spannbaum und Steinerbaum
• CPBlatt02.pdf: Blatt 2 - Kürzeste Wege-Probleme und Varianten
• CPBlock01.pdf: Blockpraktikum Blatt 1 - Knapsack Cover Inequalities
• CPBlock02.pdf: Blockpraktikum Blatt 2 - Branch and Bound

Testdaten zum Blockpraktikum ↑

• knapsack_1.dat: Testbeispiel zum Knapsack-Algorithmus (Kapazität T, n Gegenstände mit Gewichten w und Werten v)
• knapsack_2.dat: Testbeispiel zum Knapsack-Algorithmus (Kapazität T, n Gegenstände mit Gewichten w und Werten v)
• knapsack_3.dat: Testbeispiel zum Knapsack-Algorithmus (Kapazität T, n Gegenstände mit Gewichten w und Werten v)
• knapsacks.dat: Testbeispiel zum Branch and Bound

Mosel-Dateien ↑

• knapsack.mos: Knapsack-Algorithmus von Markus Reiter
• knapsack_ritter.mos: Knapsack-Algorithmus mit Lösungsfindung
• cover.mos: Separation von Cover Inequalities von Markus Reiter

Einführung in Xpress-Mosel ↑

Links zur Vorlesung ↑

• Eine (eingeschränkte) Studentenversion von Dash Xpress kann von http://www.dashoptimization.com/home/products/evaluation/student_request.html  heruntergeladen werden (nur für Windows-Rechner).
• Eine Vollversion von Mosel steht in der Rechnerhalle bereit. Um damit zu arbeiten, gibt man nach dem Login auf einem Terminal den Befehl source /usr/local/applic/packages/xpress/2008A/bin/xpvars.sh ein (setzt einige Umgebungsvariablen). Dann kann Mosel mit dem Kommando mosel gestartet werden. Dokumentation zu Xpress-Mosel finden Sie übrigens ebenfalls in der Rechnerhalle im Verzeichnis /usr/local/applic/packages/xpress/2008A/docs/mosel.
• Andere kommerzielle Optimierungssoftware:
  • CPLEX , für lineare und ganzzahlige Probleme
  • Software des ZIB (Zuse Institut Berlin) , unter anderem SoPlex, Scip und Zimpl (für kommerzielle Verwendung ist eine Lizenz erforderlich)
• Freie Optimierungssoftware:
  • lp_solve  für lineare und ganzzahlige Optimierung
  • COIN-OR  Softwaresammlung für verschiedene Optimierungsprobleme, unter anderem CLP 
• Einen Überblick über (kommerzielle, kostenlose und freie) Optimierungssoftware für verschiedenste Problemstellungen bietet der Decision Tree for Optimization Software .