Modulcode:	Inf-APO
Englische Bezeichnung:	Algorithms for practical optimization problems
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	jedes Jahr im WS (WS13/14 WS14/15)
Präsenzzeiten:	2V 2Ü 1PÜ
ECTS:	9
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 15 Std. Praktikum, 195 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	WI (BSc Inf (15)) WIAlg (BSc Inf) WI (MSc Inf (15)) WWi (MSc WInf (15)) WI (MEd Inf) WPI (MEd Inf) TG (TA) (MSc Inf (2-Fach)) IG (SA) (MSc Inf (2-Fach)) BM-IDWM (MSc WInf) OR (MSc WInf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-ADS

Kurzfassung:

Produktionsplanung, Transportprobleme und logistische Fragestellungen sind häufig anzutreffende Probleme in Wirtschaft und anderen Bereichen. Um sie zu modellieren und zu lösen greift man oft auf Abstraktionen und Techniken aus dem theoretischen Bereich der Optimierung zurück. Entsprechend erfolgt in der Vorlesung eine Einführung in grundlegende Algorithmen- und Optimierungstechniken; der Fokus liegt bei der Übertragung der Theorie auf die Praxis sowie der Implementation und Tests von Algorithmen für praktische Problemstellungen.

Lernziele:

Die Studierenden erlernen grundlegende Algorithmenprinzipien, Theorie und Methoden der linearen Optimierung und Algorithmen für praktische Optimierungsprobleme. Sie sind in der Lage, Optimierungsprobleme und dazugehörige Lösungsalgorithmen zu verstehen und haben erste Erfahrungen in der Implementation, experimentellen Analyse und Verbesserung von Algorithmen gesammelt. Schließlich sind sie in der Lage, selbstständig Algorithmen für Fragestellungen zu entwerfen und (auch experimentell) zu bewerten.

Lehrinhalte:

In der Vorlesung erfolgt eine Einführung in die grundlegenden Algorithmentechniken wie auch die lineare und ganzzahlige Optimierung. Inhalte dabei sind:

• Lineare Optimierung,
• Weitere Techniken der linearen und ganzzahligen Optimierung wie
  • Schnittebenenverfahren,
  • Branch und Bound,
  • Column Generation,
• Sowie approximative Algorithmen.

Der praktische Teil des Moduls beschäftigt sich mit der Übertragung der Theorie auf die Praxis und praktischen Problemstellungen wie z.B. Produktionsplanung, Routenplanung, Transportplanung und Logistik. Hier wird gezeigt, wie diese mit Hilfe der erlernten Techniken beschrieben und passende Algorithmen entworfen werden können. Einige dieser Algorithmen werden implementiert und mit realen Daten experimentell getestet und bewertet. Gleichzeitig wird auch der Frage nachgegangen, inwiefern die realen Eingabedaten auch weitere Verbesserungen, die in der Theorie nicht ohne weiteres möglich sind, erlauben.

Weitere Voraussetzungen:

Prüfungsleistung:

Die Veranstaltung gilt als bestanden, wenn Sie

• die Übungen und
• die praktischen Übungen erfolgreich bearbeitet haben.

Die Endnote des Moduls ergibt sich aus der Bewertung dieser beiden Teile. Dabei geht die Note der (normalen) Übung zu 40 %, die Note aus der praktischen Übung zu 60 % in die Endnote ein.

Bearbeitung der Übung

Es wird jede Woche ein Aufgabenblatt herausgegeben. Dieses soll in Zweiergruppen bearbeitet und abgegeben werden. Ein Übungsblatt gilt bei einem Studierenden als bestanden, wenn die Punktzahl von 4 (von 10) Punkten erreicht wurde und der Teilnehmer in der Übung, bei der die Hausaufgaben besprochen werden, anwesend ist und bei Aufforderung vorrechnen kann.

Es dürfen maximal zwei Übungszettel nicht bestanden sein, um die Übung zu bestehen. Zudem muss im Übungsverlauf einmal vorgerechnet werden.

Bearbeitung der praktischen Übung

In den praktischen Übungen werden insgesamt 7 Programmieraufgaben zu den in der Präsenz eingeführten Techniken ausgegeben. Jede Teilnehmerin/jeder Teilnehmer erstellt eine eigene Implementierung. Die erstellten Programme werden getestet. Damit ein Programm als erfolgreich abgegeben gewertet wird, muss

• das Programm korrekt arbeiten,
• das Programm die vorgestellte Technik verwenden, und
• der Quelltext sauber kommentiert sein.

Zum Bestehen müssen von den Aufgabenblättern 2-7 mindestens 4 erfolgreich bearbeitet werden.

Jede Abgabe wird benotet. Für die Endnote in der praktischen Übung wird der Mittelwert aus den 4 besten Abgaben gebildet.

Bearbeitung der Wettbewerbsaufgabe

Die erfolgreiche Bearbeitung einer Wettbewerbsaufgabe zählt als eine erfolgreich bearbeitete Programmieraufgabe der praktischen Übung.

Lehr- und Lernmethoden:

Vorlesung, Bearbeitung und Besprechung von theoretischen Übungen und Programmieraufgaben

Verwendbarkeit:

Die Vorlesung zählt zu den Masterbereichen "Vertiefende Informatik-Grundlagen" und "Vertiefende theoretische Grundlagen". Sie kann in unseren Masterprogrammen Angewandte Algorithmik und Algorithmen und Komplexität gehört werden.

Die Veranstaltung kann auch im Bachelor Mathematik gehört werden.

Literatur:

• Jansen, Klaus und Margraf, Marian: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter
• Papadimitriou und Steiglitz: Combinatorial Optimization: Algorithms and Complexity, Dover Publications
• Korte und Vygen: Combinatorial Optimization: Theory and Algorithms, Springer
• Domschke und Drexl: Einführung in Operations Research, Springer
• Werners: Grundlagen des Operations Research, Springer
• Borgwaldt: Optimierung, Operations Research, Spieltheorie, Birkhäuser
• Domschke, Scholl und Voß: Produktionsplanung, Springer
• Pinedo: Planning and Scheduling in Manufacturing and Services, Springer
• Schrijver: Theory of Linear and Integer Programming, Wiley
• Eiselt und Sandblom: Operations Research, Springer
• Ahuja, Magnant und Orlin: Network Flows, Prentice Hall
• Grötschel, Lovasz und Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer

Verweise:

Kommentar: