Vorlesung Algorithmische Methoden für schwere Optimierungsprobleme

  • Leitung: Juniorprof. Dr. Henning Meyerhenke
  • Zeit: Dienstags 11:30-13:00 (SR -118) und donnerstags 14:00-15:30 (SR 236), jeweils 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

  • 19.02.: Heute finden die Projektpräsentationen zu gewohnter Zeit im gewohnten Raum statt (14:00 Uhr, SR 236)!
  • Prüfungsvorbereitung auch am 19.2. wegen Konflikt am 24.2. Bitte reichen Sie Ihre Fragen bis 18.2. mittags ein!
  • 12.02.: Vorläufige Prüfungsplanung ist online.
  • 28.01.: Letzter Foliensatz online.
  • 26.01.: Übungsblatt 5 ist online und wie angekündigt am Donnerstag fällig!
  • 13.01.: Hausaufgabe bis Donnerstag: Beweis zum Greedy-Matching fortführen!
  • 29.12.: Prüfungstermine sind online. Anmeldung per E-Mail bei mir! Bitte Name, Tag, Matrikelnummer angeben!
  • 29.12.: Projektarbeiter: Bitte senden Sie mir eine E-Mail mit Angabe Ihres besprochenen Wunschprojektes ASAP, sofern noch nicht vor Weihnachten geschehen!
  • 12.12.: Übungsblatt 4 online, Foliensatz 9 korrigiert, 10 online.

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 Teilnehmer 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 anhand 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

Übungszettel

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.

KW Di (11:30-13:00) Do (14:00-15:30)
43 V: Einführung und Bin-Packing V: Bin-Packing
44 V: TSP: Approximation Ü/V: TSP: Heuristiken
45 V: Online-TSP Ü/V
46 --- ---
47 Ü/V: Max-SAT V: Max-SAT randomisiert, Max-SAT mit Tabusuche
48 --- ---
49 Ü/V Ü: SAT
50 V: Graphclustering V: Graphclustering: PLM, VNS
51 Ü: NetworKit,
V: Graphclustering 		---
2 Feiertag V: Graphclustering sowie Graphpartitionierung mit KL
3 Übung, V: Graphpartitionierung mit FM, Multilevel Ü: NetworKit, V: Vergröberung für Multilevel-Verfahren
4 Ü/V: NetworKit and Cython sowie Ameisenalgorithmen V: Grapheinbettung
5 V: Evolutionäre Algorithmen Ü/V: Grapheinbettung, Wiederholung
8 19. Februar: Projektpräsentationen und Prüfungsvorbereitung