Uni-Logo

(Master-) Seminar Anwendungen der
kombinatorischen Optimierung WS 08/09

Termine:

Seminar (S2):
Do 10:15 - 11:45 69/127

Inhalt:

Grafische Lösung eines LPs mit 2 Variablen

Aufbauend auf den Themen der Vorlesung "Einführung in die kombinatorische Optimierung" (zuletzt im SS 08) sollen in diesem Seminar Anwendungen der kombinatorischen Optimierung im Vordergrund stehen. Anhand von ausgewählten Artikeln sollen spezielle Problemstellungen in diesem Bereich betrachtet und Modelle und Lösungsalgorithmen dazu untersucht und vorgestellt werden.

Ziele des Seminars:

  • Vertiefung der Kenntnisse aus der Vorlesung "Einf. in die kombinatorische Optimierung"
  • Kennenlernen von Anwendungen und Modellen aus der komb. Optimierung
  • Kennenlernen verschiedener Methoden zur Lösung kombinatorischer Optimierungsprobleme
  • Schriftliche Ausabeitung: Einen wissenschaftlichen Text selbstständig verstehen und strukturiert wiedergeben können (Vorbereitung für Abschlussarbeit); Recherche weiterführender Literatur
  • Vortrag: Einen wissenschaftlichen Vortrag ausarbeiten und vor einem kleinen Zuhörerkreis präsentieren können
  • Als Zuhörer: Wissen aus einem Vortrag erwerben können; kritisches Zuhören

Inhalt der einzelnen Termine:

Nr. Termin Vortragende(r) Thema/Inhalt Literatur
1 30.10.08 Sigrid Knust,
Christian Viergutz		 Organisatorisches, Einführung
2 06.11.08 Alle Teilnehmer Präsentationstechnik und Gestaltung von Ausarbeitungen
 [s.u.]
3 13.11.08 Bettina Schütte Obtaining selection-optimal schedules from network flows
[W95]
4 27.11.08 Mareike Paul A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem
[BF06]
5 04.12.08 Alle Teilnehmer Besprechung der Ausarbeitungen von B. Schütte, M. Paul
6 18.12.08 Juliane Ludwig Mixed integer programming for strategic decision support in the slaughter by-product chain
[SBUBH97]
7 08.01.09 Andreas Rickling An efficient genetic algorithm with uniform crossover for air traffic control
[HP09]
8 15.01.09 Marcel Trame Flight-Gate Scheduling as a Clique Partitioning Problem
[DJP08]
9 22.01.09 Alle Teilnehmer Besprechung der Ausarbeitungen von J. Ludwig, A. Rickling
10 29.01.09 Johannes Emden Analysis, modeling and solution of the concrete delivery problem
[ADP09]
11 12.02.09 Robin Kogelberg Vehicle routing with coupled time windows
[F06]
12 19.02.09 Alle Teilnehmer Besprechung der Ausarbeitungen von M. Trame, J. Emden, R. Kogelberg, Abschlussbesprechung und Evaluation

Regeln für den Ablauf des Seminars:

  1. Der Vortrag soll mit dem/der Betreuer(in) jeweils spätestens eine Woche vor dem Termin durchgesprochen werden. Bitte selbstständig einen Termin vereinbaren!
  2. Die schriftliche Ausarbeitung sollte in LaTeX verfasst und spätestens eine Woche nach dem Vortrag abgegeben werden.
  3. Die Zeit für eine Präsentation beträgt ca. 45 bis maximal 60 Minuten. Dieser schließt sich eine fachliche Diskussion und eine Feedback-Runde an.

Benötigte Vorkenntnisse:

Kenntnisse aus der Vorlesung "Einführung in die komb. Optimierung" werden nicht zwingend vorausgesetzt, sie sind jedoch sehr hilfreich für das Verständnis der einzelnen Themengebiete des Seminars.

Schein:

Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmäßige aktive Teilnahme am Seminar (maximal zwei entschuldigte Fehlstunden) und das Halten eines Vortrages mit einer zugehörigen schriftlichen Ausarbeitung in LaTeX.

Teilnehmer:

Teilnehmen können alle interessierten Master- und Diplom-Studierenden aus den Studiengängen Informatik, Mathematik, Angewandte Systemwissenschaft, Cognitive Science.

Literatur:

[ADP09]
L. Asbach, U. Dorndorf, E. Pesch (2009). Analysis, modeling and solution of the concrete delivery problem, European Journal of Operational Research, 193, 820 - 835.
[BF06]
S. Bertels, T. Fahle (2006). A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem, Computers & Operations Research, 33, 2866 - 2890.
[D02]
U. Dorndorf (2002). Project scheduling with time windows - from theory to applications, Chapter 7.2 Gate scheduling. Contributions to Management Science, Physica-Verlag, Heidelberg.
[DJP08]
U. Dorndorf, F. Jaehn, E. Pesch (2008). Modelling Robust Flight-Gate Scheduling as a Clique Partitioning Problem. Transportation Science, 42(3), 292 - 301.
[F06]
A. Fügenschuh (2006). The vehicle routing problem with coupled time windows, Central European Journal of Operations Research, 14, 157 - 176.
[HP09]
X. Hu, E. Di Paolo (2009). An efficient genetic algorithm with uniform crossover for air traffic control, Computers & Operations Research, 36, 245 - 259.
[KB07]
D. Kim, C. Barnhart (2007). Flight schedule design for a charter airline, Computers & Operations Research, 34, 1516 - 1531.
[SBUBH97]
J.Th.M. van Sonsbeek, P. van Beek, H.A.P. Urlings, P.G.H. Bijker, J.F.L. Hagelaar (1997). Mixed integer programming for strategic decision support in the slaughter by-product chain, OR Spektrum, 19, 159 - 168.
[W95]
M. Wennink (1995). Algorithmic support for automated planning boards, Ph.D. thesis Technical University Eindhoven, Chapter 3.

Präsentationstechnik und Gestaltung von Ausarbeitungen

[BR93]
R. Bromme, R. Rambow (1993): Verbesserung der mündlichen Präsentation von Referaten: Ein Ausbildungsziel und zugleich ein Beitrag zur Qualität der Lehre, Das Hochschulwesen (41. Jg., Heft 6, S. 289-297), Leitfaden zur Vorbereitung und Durchführung mündlicher Seminarpräsentationen
[Ki06]
E. Kindler (2006): Präsentation "Gut vortragen! Aber wie?" (PDF)
[Lehn]
M. Lehn: Wie halte ich einen Seminarvortrag? Homepage des Instituts für Mathematik der Universität zu Mainz, Wie halte ich einen Seminarvortrag?
[Pfahler]
P. Pfahler, Institut für Informatik, Universität Paderborn: Seminare: Hinweise für Vortrag und Ausarbeitung
[Re03]
P. Rechenberg (2006): Technisches Schreiben (nicht nur) für Informatiker, 3. Aufl., Hanser
[Zo05]
J. Zobel (2005): Writing for computer science, 2nd Ed., Springer

Zuletzt geändert: 11.03.2009 (CV/SK)