Hauptseminar WS 01/02
Die Welt der Handlungsreisenden: Algorithmen, Analysen und Anwendungen

Donnerstag, 14:15 bis 15:15 Uhr, S2229

[Zusammenfassung] [Themen und Literatur] [Hinweise]

Zusammenfassung

Ein Handlungsreisender möchte ausgehend von seiner Heimatstadt eine Serie von Städten bereisen. Er will die Städte in einer Reihenfolge besuchen, so dass die gesamte Reisestrecke möglichst klein wird. Er fragt sich also, was die beste Reihenfolge der Städte ist. Dieses Problem wird auch das Problem des Handlungsreisenden, oder kurz TSP (engl. Traveling Salesman Problem) genannt.

Das TSP ist eines der bekanntesten Probleme aus der kombinatorischen Optimierung und - auch wenn ganz einfach formuliert - ausgesprochen schwierig zu lösen. Da es zu den sogenannten NP-vollständigen Problemen gehört, wird es wohl auch keinen polynomiellen Algorithmus zum Auffinden einer Optimallösung geben. Trotzdem, TSP tritt häfig in verschiedenen Varianten in der Praxis auf, und es ist mittlerweile gelungen auch vergleichsweise größe Probleme optimal zu lösen. Wie dies gelingen kann, wollen wir in diesem Hauptseminar untersuchen.

Anhand des TSP werden dabei die wichtigsten algorithmischen Methoden der Kombinatorischen Optimierung vorgestellt. Wir analysieren verschiedene heuristische Verfahren und Approximationsalgorithmen, betrachten optimal lösbare Spezialfälle und beschreiben die Grundlagen fü Branch-and-Cut Verfahren. Ziel dieses Hauptseminars ist dabei, nicht nur ein einziges Problem zu lösen, sondern allgemeine Techniken zum Lösen von Optimierungsproblemen kennenzzulernen und zu vergleichen.

Neben der Algorithmenanalyse betrachten wir verschiedene Anwendungen, wie z.B. in der Fahrzeugeinsatzplanung oder der Bioinformatik und zeigen auch für diese verschiedenen Lösungsansätze auf.

Themen- und Literatur-Liste

Dem Seminar liegen folgende Bücher zugrunde:

[LLKS]: The Traveling Salesman Problem , E.L. Lawler, J.K.Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, J. Wiley Sons, Inc, 1985
[CCPS] Combinatorial Optimization, W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, J. Wiley Sons, Inc, 1998
[KV]: Combinatorial Optimization, Theory and Algorithms, B. Korte, J. Vygen, Springer 2000
[JRR] The Traveling Salesman Problem , M. Jünger, G. Reinelt und G. Rinaldi, Ch. 4 of: M.O. Ball et al (Eds.): Hanbooks in OR & MS, Vol 7. (1995) 225 - 330.

Thema Titel Vortragende(r) Termin Betreuer

1 Einführung und Überblick über das TSP Problem Jabara Zakaria 25.10.01 Ulrich Rührmair

2 Heuristische Algorithmen für das TSP Daniel Wasserrab 08.11.01 Thomas Schickinger

3 Approximationsalgorithmen Bertold Meier 15.11.01 Thomas Bayer

4 Untere Schranken der Approximierbarkeit Nina Istavrinos 22.11.01 Martin Raab

5 Das Approximationsschema von Arora Andreas Weissel 29.11.01 Mark Scharbrodt

7 Schnittebenenverfahren für das TSP Problem Jiming Yin 13.12.01 Michal Mnuk

6 Probabilistische Analyse von Instanzen im Einheitswürfel Christian Osendorfer 20.12.01 Hanjo Täubig

8 Hamiltonkreise in Zufallsgraphen Markus Holm 10.01.02 Mark Scharbrodt

Thema	Titel	Vortragende(r)	Termin	Betreuer
1	Einführung und Überblick über das TSP Problem	Jabara Zakaria	25.10.01	Ulrich Rührmair
2	Heuristische Algorithmen für das TSP	Daniel Wasserrab	08.11.01	Thomas Schickinger
3	Approximationsalgorithmen	Bertold Meier	15.11.01	Thomas Bayer
4	Untere Schranken der Approximierbarkeit	Nina Istavrinos	22.11.01	Martin Raab
5	Das Approximationsschema von Arora	Andreas Weissel	29.11.01	Mark Scharbrodt
7	Schnittebenenverfahren für das TSP Problem	Jiming Yin	13.12.01	Michal Mnuk
6	Probabilistische Analyse von Instanzen im Einheitswürfel	Christian Osendorfer	20.12.01	Hanjo Täubig
8	Hamiltonkreise in Zufallsgraphen	Markus Holm	10.01.02	Mark Scharbrodt

Hinweise zur Gestaltung der Vorträge

	Merkblatt zur Gestaltung eines Seminarvortrags. (Die Tips auf diesem Merkblatt sind keine offiziellen Anforderungen oder Bewertungskriterien der TU München, sondern aus der Praxis eines Seminarleiters heraus entstandene Ratschläge.)
	Tips zur Erstellung einer Ausarbeitung mit LaTeX (einschließlich Rahmen-Datei als Vorlage)
	Tips zur Erstellung von Folien mit LaTeX (einschließlich Rahmen-Datei als Vorlage)

Weitere Auskünfte erteilt Mark Scharbrodt.

Mark Scharbrodt