Algorithmen und Komplexität - Hauptseite Algorithmen und Komplexität

Vorlesung: Kombinatorische Optimierung II

Dozent: Mark Proksch

Termine

VL Freitag 11:00 - 13:00 (RUD 25, 4.110)
PR Freitag 09:00 - 11:00 (RUD 25, 3.415)

Zuordnung

  • Hauptstudium, 2. Teil eines Halbkurses
  • Theoretische Informatik

Inhalte und Lernziele

Man betrachte sich folgende Probleme:
  • Ein Reisender will eine bestimmte Menge von Städten besuchen und sucht nach einer möglichst kurzen (oder auch möglichst billigen) Route, mit der er jeden Ort genau einmal besucht. (Traveling Salesman Problem)
  • Eine Betrieb stellt eine Menge von Produkten mit Hilfe einer Menge verschiedener Maschinen her. Jedes Produkt erfordert zu seiner Herstellung die Benutzung bestimmter Maschinen in einer bestimmten Reihenfolge und jeweiliger Bearbeitungszeit. Anhand von Auftragslage und Lieferterminen ist nun ein Fertigungsplan zu erstellen, der alle Termine und Stückzahlen einhält und sowohl die Standzeiten der Maschinen (freie Kapazität für weitere Aufträge) als auch die Durchlaufzeiten der Produkte (Lagerhaltungskosten) minimiert. (Maschinenbelegungsproblem)
  • Ein Verkehrsbetrieb will einen Fahrplan erstellen. Die Taktzeiten jeder Linie sind vorgegeben. Die genauen Abfahrtzeiten sind so zu wählen, daß an Wendestellen genügend Wartezeit für Pausen und Verspätungspuffer zur Verfügung stehen und die Anschlüsse optimiert (durchschnittliche Wartezeiten der Kunden minimiert) werden.
  • Eine Fluggesellschaft möchte den monatlichen Einsatzplan seines fliegenden Personals erstellen. Dieser Plan muß zunächst den gesetzlichen und tarifvertraglichen Vorschriften (Ruhezeiten, maximale Flugzeiten) genügen und alle anfallenden Dienste mit Hilfe des vorhandenen Personals abdecken. Darüber hinaus möchte die Fluggesellschaft Wartezeiten des Personals minimieren, Hotel- und zusätzliche Transportkosten senken und die Robustheit des Einsatzplans gegenüber Verspätungen erhöhen. (Crew Scheduling Problem)

Diesen Problemen ist gemein, daß die Generierung einer beliebigen, zulässigen Lösung vergleichsweise einfach, aber das Auffinden einer kostengünstigen bzw. effizienten Lösung sehr schwer ist. In Bereichen wie Logistik, Transport und Produktion finden sich eine Vielzahl ähnlicher Problemstellungen, deren Lösung zu einem ökonomischen Einsatz von Ressourcen, erhöhter Effizienz von Prozessen oder einer Verbesserung der Produktqualität beiträgt.

Die Vorlesung widmet sich verschiedenen Lösungsverfahren solcher kombinatorischer Optimierungsprobleme. Sie besteht aus zwei Teilen, in denen die zwei bedeutendsten Algorithmenfamilien behandelt werden.

Der erste Teil dieser Vorlesung fand bereits im Wintersemester statt und widmete sich lokalen Suchverfahren.

Dieser zweite Teil befaßt sich mit linearer und ganzzahliger Programmierung. Es werden gängige Verfahren wie die Primal-Dual-Methode, der Simplexalgorithmus und die Ellipsoidmethode erarbeitet und analysiert.

Beide Teile bilden zusammen einen Halbkurs und werden im Sommer gemeinsam geprüft.

Programmierpraktikum

Betreuer: Mark Proksch

Das Programmierpraktikum soll eine Möglichkeit bieten, die im ersten Teil der Vorlesung erlernten Methoden in die Praxis umzusetzen. Um eine gemeinsame Schnittstelle zwischen Problem und Algorithmus herum sollen verschiedene Problemmodellierungen und Algorithmen implementiert werden, die dann miteinander kombinierbar sind.

Als Prüfungsvoraussetzung wird zwar von jedem eine aktive Mitarbeit im Praktikum erwartet, wie weit sich der Einzelne jedoch einbringen will, kann er selbst bestimmen.

Als Termin für das Praktikum haben wir uns auf Freitag, 09:30 Uhr geeinigt. Die Vorlesung findet gleich im Anschluß statt. Da nicht in jeder Woche ein Praktikumstermin nötig sein wird, findet sich hier eine Tabelle mit den nächsten stattfindenen Terminen. Ich bitte um regelmäßige Beachtung.

20.04.kein Praktikum
27.04.Vortrag: "Lokale Suchverfahren in der Praxis"
04.05.Verteilung der Praktikumsaufgaben
11.05.Vorstellung erster Ideen
18.05.kein Praktikum
25.05.kein Praktikum
01.06.Vorlesung der Vorwoche wird nachgeholt
08.06.Vorstellung der Grundstruktur
15.06.kein Praktikum
22.06.kein Praktikum
29.06.Vorstellung der Ergebnisse I
06.07.kein Praktikum
13.07.Vorstellung der Ergebnisse II
20.07.Vorstellung der Ergebnisse III
zuletzt geändert am 23.01.2006 (alkox-www)