Computerpraktikum zur Optimierung 1

Personen

Dozent: Michael Ritter

Aktuelles

  • 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 können Sie hier einsehen. Vielen Dank für Ihre Teilnahme!

  • 26. August 2008: Die Evaluierung zum Computerpraktikum ist online. Wenn Sie am Blockpraktikum teilgenommen haben, sind Sie bereits für die Evaluierung angemeldet und haben eine entsprechende E-Mail erhalten. Auch wenn Sie nur an der Vorlesung teilgenommen haben, freue ich mich über Feedback, Kritik und Verbesserungsvorschläge. Hier erfahren Sie, wie Sie an der Evaluierung teilnehmen können.

  • 1. August 2008: Beim Blockpraktikum ist ein Laptop-Netzteil liegengeblieben. Wenn der Besitzer das vermisst: Bitte melden Sie sich bei Steffen Borgwardt, der kann Ihnen das Netzteil zurückgeben.

  • 23. Juli 2008: Die genauen Zeiten fürs Blockpraktikum sind jetzt fest (und unverändert gegenüber den angekündigten). Die angemeldeten TeilnehmerInnen erhalten in den nächsten Tagen noch eine E-Mail mit weiteren Details.

  • 10. Juni 2008: Zum nächsten Termin werden wir die Containment-Beispiele abschließen, anschließend behandeln wir ein einfaches Produktionsplanungsmodell. Danach (also wahrscheinlich erst am 1. Juli) werden wir noch Traveling Salesman Probleme betrachten. In diesem Kontext gibt es dann auch eine kurze Einführung in ganzzahlige lineare Optimierung und Lösungsverfahren.

  • 20. Mai 2008: Weil wir die Beispiele zum Containment heute nicht alle bearbeiten konnten, gibt es zum nächsten Termin voraussichtlich eine Fortsetzung. Wenn Sie sich aber was ganz anderes wünschen, sagen Sie mir (m.ritterma.tum.de) einfach Bescheid.

Evaluierung

Die Evaluierung des Computerpraktikums ist abgeschlossen. Vielen Dank an alle, die sich an der Evaluierung beteiligt haben, insbesondere für die vielen hilfreichen Kommentare. Ein paar Anmerkungen dazu:

  • Das Blockpraktikum kam sehr gut an, das werde ich auf jeden Fall beibehalten.
  • Die Option, die Veranstaltung komplett in die Semesterferien zu legen, kam bei Ihnen nicht so gut an. Ein alternativer Vorschlag war, kleine Vorlesungabschnitt während des Blockpraktikums einzubauen. Mit gefällt diese Option, das sollten wir ggf. diskutieren.
  • "Studenten weniger Fragen stellen", "Während der Vorlesung [...] weniger Mitarbeit von den Studenten erwarten": Ein anderer Kommentar in dieser Richtung war "Die Vorlesung fand ich etwas weniger hilfreich, da man durch das Selberprogrammieren viel, viel mehr lernt." Genau aus diesem Grund will ich keine Vorlesung halten, in der ich den Stoff nur vorführe. Auch wenn der Stoffumfang dadurch geringer wird, bin ich der Meinung, dass Sie von der Vorlesung nur profitieren, wenn Sie auch aktiv mitarbeiten können. Und gerade in einer "kleinen" Vorlesung ohne festen Stoffumfang haben wir die Möglichkeit, den Stoff je nach Lerngeschwindigkeit und Interesse zu variieren. Ich gestehe Ihnen aber zu, dass die Eigenarbeit zu wenig organisiert und vielleicht auch zu wenig klar definiert war, da besteht sicher noch Verbesserungspotential.
  • "Nur ein Termin am Tag": Da stimme ich zu, der Doppeltermin war wohl doch etwas zu viel.
  • "Die Übersicht über Mosel nicht nur ausdrucken, sondern ins Netz stellen": Bei dieser Übersicht handelt es sich um Auszüge aus der Original-Dokumentation, die ich wegen Copyright leider nicht einfach ins Netz stellen kann. Evtl. greife ich aber einen anderen Vorschlag auf und bereite fürs nächste Mal eine Kurzübersicht der wichtigsten Kommandos vor.

Die komplette Evaluierung zum Download: Evaluierung.pdf

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 1.

Termine für die Vorlesung

Datum Uhrzeit Raum Thema
29. April 2008 15:00 - 16:30 MI HS 2 Einführung in Xpress-Model
20. Mai 2008 14:40 - 16:10 MI HS 2 Containment-Probleme, Teil 1
03. Juni 2008 14:40 - 16:10 MI HS 2 Containment-Probleme, Teil 2
17. Juni 2008 14:40 - 16:10 MI HS 2 Containment und Partitionierung, Produktionsplanung
01. Juli 2008 14:40 - 16:10 MI HS 2 Produktionsplanung, Traveling Salesman und Grundlagen ganzzahliger linearer Optimierung

Termine fürs Blockpraktikum

Datum Uhrzeit Raum Thema
Mi, 30. Juli 2008 13:00 - 16:00 00.07.011 Mosel: Wiederholung und Übungen
Do, 31. Juli 2008 9:00 - 12:00 00.07.011 tba
Do, 31. Juli 2008 13:00 - 16:00 00.07.011 tba
Fr, 01. August 2008 11:00 - 14:00 00.07.011 Das Traveling Salesman-Problem: IP-basierte Ansätze

  • Die Uhrzeiten und der Raum stehen jetzt fest.
  • Wenn Sie einen Laptop mit Windows-Betriebssystem mitbringen können, installieren Sie bitte die Studentenversion von Xpress-MP (Links siehe unten). Für andere Systeme (Linux, MacOS X etc.) sollten Sie entweder einen geeigneten Emulator benutzen, oder ein Programm für den ssh-Zugang zur Rechnerhalle sowie einen geeigneten Editor installiert haben (dann können Sie die dort installierte Vollversion verwenden, haben aber keine IDE zur Verfügung).
  • Idealerweise finden Sie sich schon vor der Veranstaltung in Gruppen zu zwei oder drei Personen zusammen, von denen wenigstens einer einen Laptop mitbringen sollte. Wenn Sie keinen Partner haben, schreiben Sie mir eine E-Mail (m.ritterma.tum.de).

Material zu den Vorlesungen

Einführung in Xpress-Mosel

  • 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 steht in der Rechnerhalle bereit. Dazu 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.
  • Andere kommerzielle Optimierungssoftware:
  • 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 .

Beispieldateien aus der Vorlesung

Mensa1.lp LP-Datei fürs Breimischungs-Problem
Mensa1.mos Breimischungs-Problem als einfaches Mosel-Modell: Grundlagen von Mosel
Mensa2.mos Breimischungs-Problem als fortgeschrittenes Mosel Programm: Array, Summen und Schleifen
stable.mos Stabile Menge auf dem vollständigen Graphen mit n Knoten als Mosel-Modell

Containment-Probleme, Teil 1

Aufgabenblatt und Vorlagen

Blatt01 (PDF) Aufgabenblatt für diesen Termin (und voraussichtlich auch für den nächsten)
LuigiTemplate.mos Mosel-Vorlage mit Testdaten fürs Eisverkäufer-Problem

Beispieldateien aus der Vorlesung

LuigiA-1.mos Lösung zu Aufgabe 1.1 a)
LuigiA-2.mos Alternative Lösung zu Aufgabe 1.1 a)

Containment-Probleme, Teil 2

Beispieldateien aus der Vorlesung

ContainmentKran.mos Containment mit einem Container
ContainmentKranKreuzpolytop.mos Approximation mittels Kreuzpolytop
ContainmentKranMinimumR.mos Containment mit Radiusminimierung
ContainmentFeuerwehrKreuzpolytop.mos Containment mit zwei Containern
neubaugebiet.dat Beispieldaten zum Feuerwehr-Problem

Produktionsplanung

Aufgabenblatt

CPBlatt02.pdf Aufgabenblatt zu Produktionsplanungsproblemen

Partitionierung und Traveling Salesman

CPBlatt03.pdf Aufgabenblatt zu Partitionierungsproblemen und Traveling Salesman

Material zum Blockpraktikum

Aufgabenblätter

Blatt 1 (PDF) Aufgabenblatt zum ersten Termin: Übungen zu Mosel
Blatt 2 (PDF) Aufgabenblatt zum zweiten Termin: Das Knapsack-Problem
Blatt 3 (PDF) Aufgabenblatt zum dritten Termin: Zuordnungs-Probleme
Blatt 4 (PDF) Aufgabenblatt zum vierten Termin: Irrfahrten und Rundreisen

Daten zu den Übungsaufgaben

Freundschaften.mos Testdaten für Aufgabe 3.1 g)
tsp-template.mos Template für die "Odyssee-Aufgabe"

Musterlösungen

Teil 1: Loesung_1.1.mos, Loesung_1.2.mos, Loesung_1.3.mos
Teil 2: Loesung_2.1_a_b.mos, Loesung_2.1_c.mos, Loesung_2.2_a_b.mos,
  Loesung_2.2_c.mos, Loesung_2.2.mos mit Animation
Teil 3: Loesung_3.1_a_b_c.mos, Loesung_3.1_d.mos, Loesung_3.1_e.mos,
  Loesung_3.1_f.mos, Loesung_3.1_g.mos
Teil 4: Loesung_4.1_a_b.mos, Loesung_4.1_c_d.mos,
  Loesung_4.1_c_d.mos mit ungerichteten Kanten und allen Subtour-Nebenbedingungen