Computerpraktika zur Linearen und Kombinatorischen Optimierung Ferienkurs

 

Die Ferienkurse werden aus Mitteln der Studienbeiträge finanziert.

Dozent:	Melanie Herzog
Umfang:	Lineare Optimierung: Blockpraktikum am 10./11. April 2012
	Kombinatorische Optimierung: Blockpraktikum am 12./13. April 2012

Aktuelles

Beschreibung

Termine

Material zum Praktikum

Links zum Praktikum

Aktuelles

• Während des Praktikum werden Sie in kleinen Gruppen (2 oder 3 Personen) arbeiten. Jede Gruppe benötigt mindestens einen Laptop. Sie dürfen sich selbst zu Gruppen zusammenfinden. Alle, die einen Laptop mitbringen, sollten vorab die Studentenversion der FICO Xpress Software  installieren! Bitte melden Sie sich, falls es dabei Probleme gibt.
• Die Anmeldung über das Ferienkurse - Portal ist freigeschaltet. Sie endet zwei Wochen vor Kursbeginn.

Beschreibung

Ziel des Praktikums ist es, die in den Vorlesungen Lineare Optimierung (MA3501) und Combinatorial Optimization (MA4502) vorgestellte Theorie in die Praxis umzusetzen. Dadurch soll das Praktikum auf weitere Veranstaltungen der Optimierung (insbesondere die Fallstudien), sowie Bachelor- und Masterarbeiten vorbereiten.

Das Praktikum gliedert sich in zwei Teile: An den ersten beiden Tagen wird die Programmiersprache Mosel eingeführt und Problemstellungen der Linearen Optimierung bearbeitet. Die verbleibenden zwei Tage dienen der praktischen Umsetzung von Verfahren der Kombinatorischen Optimierung. Die Praktikumsteile können unabhängig voneinander belegt werden, im zweiten Teil werden jedoch Grundkenntnisse in Mosel vorausgesetzt!

Während des Praktikums wird zwischen kurzen Vorlesungsabschnitten und längerer Gruppenarbeit gewechselt. Dabei sollen sollen in kleinen Gruppen (2 oder 3 Personen) Modellierungsaufgaben bearbeitet und am eigenen Laptop implementiert werden.

Vorraussetzungen

Für die Teilnahme am ersten Praktikumsteil (Linearen Optimierung, 10./11. April 2012):

• Vorlesung Lineare Optimierung (MA3501)
• Grundkenntnisse im Programmieren (in einer beliebigen Sprache) sind völlig ausreichend

Für die Teilnahme am zweiten Praktikumsteil (Kombinatorische Optimierung, 12./13. April 2012):

• Vorlesung Combinatorial Optimization (MA4502)
• Teilnahme am ersten Praktikumsteil oder anderweitig erworbene Grundkenntnisse in Mosel

Anmeldung

Die Anmeldung zum Praktikum erfolgt über das Ferienkurse - Portal.

Termine

Datum	Uhrzeit	Raum	Thema
Di, 10. April 2012	9:00 - 12:00 und 13:00 - 17:00	02.04.011	Einführung in Mosel, Lineare Optimierung
Mi, 11. April 2012	9:00 - 12:00 und 13:00 - 17:00	02.04.011	Lineare Optimierung
Do, 12. April 2012	9:00 - 12:00 und 13:00 - 17:00	02.04.011	Kombinatorische Optimierung
Fr, 13. April 2012	9:00 - 12:00 und 13:00 - 17:00	02.04.011	Kombinatorische Optimierung

Material zum Praktikum

Mosel Präsentation: hier
Mosel Kurzreferenz: hier

Aufgabe zur Einführung in Mosel

Cracken1.mos	Cracken von Rohöl als einfaches Mosel-Modell
Cracken2.mos	Cracken als fortgeschrittenes Mosel-Modell: set, range, array
Cracken3.mos	Cracken als fortgeschrittenes Mosel-Modell: record
Cracken4.mos	Cracken als fortgeschrittenes Mosel-Modell: Schleifen und Summen
Cracken5.mos	Cracken als fortgeschrittenes Mosel-Modell: Daten einlesen
Cracken.dat	Datensatz zu cracken5.mos

Aufgaben zur Linearen Optimierung

Übungsblatt 1: hier
Zusatzblatt 1: hier
Übungsblatt 2: hier
Zusatzblatt 2: hier

Aufgabe	Vorlage / Daten	Lösung
1.1 Autovermietung	Autovermietung1.dat, Autovermietung2.dat	Autovermietung.mos
1.2 Sudoku	Sudoku1.dat, Sudoku2.dat, Sudoku3.dat	Sudoku_a.mos, Sudoku_b.mos
Zusatzblatt Steinbruch	Steinbruch1.dat, Steinbruch2.dat, Steinbruch3.dat	Steinbruch.mos
2.1 Urlaubsreise	Urlaubsreise_Vorlage.mos	Urlaubsreise_a.mos, Urlaubsreise_b.mos
2.2 Gummibären	Gummibaeren_Vorlage.mos, Gummibaeren.dat	Gummibaeren_b.mos, Gummibaeren_d.mos
Zusatzblatt Tutorgruppen	Tutorgruppen1.dat, Tutorgruppen2.dat, Tutorgruppen3.dat, Tutorgruppen4.dat	Tutorgruppen_1.mos, Tutorgruppen_2.mos, Tutorgruppen_3.mos, Tutorgruppen_4.mos, Tutorgruppen_5.mos, Tutorgruppen_6.mos

Aufgaben zur Kombinatorischen Optimierung

Übungsblatt 1: hier
Übungsblatt 2: hier
-

Aufgabe	Vorlage / Daten	Lösung
1.1 Knapsack	Knapsack1.dat, Knapsack2.dat, Knapsack3.dat	Knapsack_1.mos
1.2 Branching	Branching.dat	Branching_a.mos, Branching_b.mos
1.3 Knapsack	siehe Aufgabe 1.1	Knapsack_2_a.mos, Knapsack_2_b.mos
1.4 Knapsack	siehe Aufgabe 1.1	Knapsack_3.mos
2.1 Multicommodity Flow	MulticommodityFlow1.dat, MulticommodityFlow2.dat, MulticommodityFlow_Vorlage.mos	MulticommodityFlow_b.mos, MulticommodityFlow_c.mos

Links zum Praktikum

• Eine (eingeschränkte) Studentenversion von FICO Xpress kann von http://optimization.fico.com/student-version-of-fico-xpress.html  heruntergeladen werden (leider nur für Windows-Rechner).
• Eine Übersicht zu Mosel mit einigen Beispielen gibt es hier .
• Andere kommerzielle Optimierungssoftware:
  • CPLEX , für lineare und ganzzahlige Probleme
  • Gurobi , 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 
  • GNU Linear Programming Kit  Ein LP/ILP-Solver
• Einen Überblick über (kommerzielle, kostenlose und freie) Optimierungssoftware für verschiedenste Problemstellungen bietet der Decision Tree for Optimization Software .