Vorlesung Algorithmische Methoden für schwere Optimierungsprobleme

  • Semester: WS 2016/17
  • Zielgruppe: Bachelor, 3. Jahr
  • Leitung: Prof. Dr. Henning Meyerhenke
  • Zeit: Dienstags 11:30-13:00 Uhr und donnerstags 14:00-15:30 Uhr, jeweils Raum 236, Geb. 50.34
  • SWS: 2+1
  • LVNr: 2400013
  • Hinweis: Die Veranstaltung ist mit 2+1 SWS angesetzt, findet aber mit 4 Wochenstunden statt, da einige Termine im Semester aufgrund von Terminkonflikten ausfallen werden. Diese werden rechtzeitig angekündigt.

Aktuelles

  • 15.3.: Skript Version 0.4 online.
  • 31.1.: Die Projektpräsentationen finden erst am 9.2. statt. Die Prüfungsvorbereitung ist für den 21.2. um 11 Uhr im SR 301 vorgesehen.
  • 11.1.: Prüfungstermine sind online.
  • 7.12.: Foliensätze 10 und 11 aktualisiert.
  • 22.11.: Heute keine Veranstaltung!
  • 10.11.: Heute wird NetworKit eingeführt. Jedes Projektteam hat idealerweise ein Notebook dabei, auf dem NetworKit bereits installiert ist!
  • Bitte registrieren Sie sich für die Mailingliste vorlesung-amfso!

Kontext

Es gibt viele praktische Probleme, die nicht perfekt gelöst werden können oder bei denen es sehr lange dauern würde, eine optimale Lösung zu finden. Ein Beispiel dafür ist Bin-Packing, wo Objekte in Behälter (bins) einzupacken sind, wobei man möglichst wenige Behälter benutzen will. (Die Fragestellung ergibt sich bei einem großen Online-Versender tausendfach am Tag.)
Manchmal gibt es auch Probleme, bei denen man Entscheidungen treffen muss, ohne vollständige Kenntnis über die Zukunft oder die Gegenwart zu haben (Online-Probleme). Man möchte etwa beim Bin-Packing irgendwann auch Bins abschließen und wegschicken, während vielleicht noch neue Objekte ankommen.
Softwareentwickler mit Expertise in Optimierungstechniken sind in der Wirtschaft (und in der Wissenschaft) sehr gefragt.

Veranstaltungsziele

Ziel der Veranstaltung ist es, dass die Teilnehmenden zunächst die Komplexität von algorithmischen Problemen erkennen und nachweisen können. Darauf aufbauend, sollen sie mögliche Lösungsansätze erkennen und anwenden, sowie implementieren und hinsichtlich ihrer Qualität, Anwendbarkeit und Laufzeit bewerten können.

Inhalte

Da in der Praxis viele schwierige Optimierungsprobleme auftreten, werden alle besprochenen klassischen Optimierungsprobleme praktisch motiviert. In den Übungen erhalten Sie die Gelegenheit, die gelernten Methoden selbst umzusetzen. Die wesentlichen übergeordneten Lösungsmethoden, die vorgestellt werden, sind:

  • Heuristiken
  • Metaheuristiken
  • Approximationsalgorithmen
  • Online-Algorithmen
Der Schwerpunkt wird auf Heuristiken und Metaheuristiken liegen. Diese spielen in der Praxis eine große Rolle und ergänzen die Inhalte der Vorlesung Algorithmen II.

Literatur

Ablauf und zugehörige Materialien

Skript

Das Skript dient zur Zeit lediglich der Ergänzung und deckt bei weitem nicht die ganze Vorlesung ab. Es enthät aber vielfach konkrete Literaturverweise. Beachten Sie, dass das Skript momentan noch sehr unvollständig ist, wir aber an Erweiterungen und Verbesserungen arbeiten.

Aktuelle Version: 0.4 (15.3.17)

Übungszettel

Es werden in den Übungen überwiegend Präsenzaufgaben besprochen.

Veranstaltungstermine

In der folgenden Tabelle werden die Inhalte der Termine angekündigt sowie nach der Veranstaltung die zugehörigen Materialien verlinkt. Beachten Sie bitte, dass der Ablaufplan vorläufig ist und sich noch ändern kann. Mehr Termine folgen.

KW Di (11:30-13:00) Do (14:00-15:30)
42 V: Einführung und Bin-Packing V: Bin-Packing
43 Ü (R. Glantz) V: TSP: Christofides, Nichtapproximierbarkeit
44 --- (Feiertag) Ü: Harmonic, Christofides; V: TSP: (Meta)Heuristiken
45 V: TSP mit LK, SA V: Online-TSP (H. M.), Ü: NetworKit-Tutorial (E. Bergamini)
46 V: Rest Online-TSP, Einführung (Max-)SAT Ü: PAH, V: RR-Max-SAT
47 --- V/Ü: Max-SAT, Tabusuche, ILS (R. Glantz)
48 V: Rest ILS, Clusteranalyse von Graphen Ü: Modularität, V: Lokale Heuristiken
49 V/Ü: VNS, Approximation mit Flüssen V/Ü: GPP, KL/FM (R. Glantz)
50 V/Ü: Multilevel, ACO ---
51 V/Ü: Einbettung von Graphen ---
2 Übung zur Wdh. V/Ü: Einbettung von Graphen (R. Glantz)
3 V: Evolutionäre Algorithmen (R. Glantz) ---
4 --- ---
5 --- ---
6 --- Projektpräsentationen