Dr. Stefan Thienel


Vorlesung Der Handlungsreisende und seine Verwandten
Mo 14 - 16, Mi 13 - 15 im Hörsaal 301, Institut für Informatik


Übungen zur obigen Vorlesung
2 Std. nach Vereinbarung

Anhand des Problems des Handlungsreisenden (Traveling Salesman Problem) werden die wichtigsten algorithmischen Methoden der Kombinatorischen Optimierung vorgestellt.

Im ersten Teil der Vorlesung werden verschiedene heuristische Verfahren diskutiert. Der zweite Teil ist den exakten Verfahren zur Bestimmung von Optimallösungen gewidmet. Ausführlich werden Branch-and-Cut Verfahren erläutert, die der derzeit beste Ansatz zur Berechnung der optimalen Lösung sind. Verwandte Optimierungsprobleme des Handlungsreisendenproblems, wie z.B. die Fahrzeugeinsatzplanung, werden im letzten Teil der Vorlesung behandelt. In diesem Rahmen werden Branch-and-Price Algorithmen vorgestellt, die seit kurzem sehr erfolgreich zur Lösung von kombinatorischen Optimierungsproblemen eingesetzt werden.

Neben den Grundvorlesungen der Informatik sind Kenntnisse der Linearen Optimierung für das Verständnis der Vorlesung erforderlich.

In den Übungen wird der Vorlesungsstoff vertieft. Schriftliche Übungsaufgaben und Programmieraufgaben (C++) werden unter Anleitung eines Tutors besprochen. Bei erfolgreicher Teilnahme kann ein Übungsschein erworben werden, der zur Vorlage für die Diplom-Hauptprüfung verwendet werden kann. Die Vorlesung kann als ein Teilgebiet für Diplomprüfungen in Informatik und Wirtschaftsinformatik bei Prof. Jünger gewählt werden.