Vorlesung Algorithmische Methoden für schwere Optimierungsprobleme

  • Leitung: Juniorprof. Dr. Henning Meyerhenke
  • Zeit: Dienstags 11:30-13:00 (erstmalig am 16.04.2013) und donnerstags 15:45-17:15
  • Raum: Jeweils Geb. 50.34, SR -118
  • 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.
  • Bevorzugte Prüfungstermine: 7. August 2013, 13. September 2013 (voll); 8. November 2013 (Anmeldung bei Frau Beckert bzw. Frau Meinhart)

Aktuelles

  • NEU: Fragerunde am 5. August, 15:45 bis maximal 17:15 Uhr im Raum 236 (Geb. 50.34). Fragen sind bis zum 1. August per E-Mail einzusenden.
  • 13.06.: Anmeldung für einen Prüfungstermin (7.8. oder 13.9.) über das Sekratariat, genauer Frau Beckert. Geben Sie an, ob Sie lieber vormittags oder nachmittags geprüft werden wollen. Wir werden versuchen, das zu berücksichtigen. Sie erhalten einige Tage vor der Prüfung die genaue Uhrzeit mitgeteilt.

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