Kaktus-Repräsentation der minimalen Schnitte eines Graphen und Anwendung im Branch-and-Cut Ansatz für das TSP

Diplomarbeit aus dem Jahr 1999 im Fachbereich Mathematik - Angewandte Mathematik, Note: 1,0, Ruprecht-Karls-Universität Heidelberg (Mathematik), Sprache: Deutsch, Abstract: Inhaltsangabe:Zusammenfassung:
Diese Diplomarbeit leistet einen Beitrag zur algorithmischen Lösung des Problems des Handelsreisenden (Traveling Salesman Problem, TSP).
Der Handelsreisende sucht eine kürzeste Rundreise durch eine fest gegebene Menge von Städten, wobei die Weglängen zwischen je zwei Städten bekannt sind.
Die Anwendungen des TSPs gehen weit über Fahrtroutenoptimierung hinaus.
Das erfolgreichste Verfahren zur exakten Lösung NP-schwerer diskreter oder kombinatorischer Optimierungsprobleme wie dem TSP ist Branch-and-Cut.
Dieses Verfahren ist eine Kombination aus Branch-and-Bound und dem Schnittebenenverfahren.
Die Diplomarbeit stellt ein Verfahren vor in dem Schnittebenen aus linearen Beschreibungen niedrigdimensionaler TSP Polytope gewonnen werden.
Pionierarbeit in dieser Richtung wurde Mitte der 90er Jahre von Christof und Reinelt geleistet.
Das hier vorgeschlagene Verfahren unterscheidet sich von diesen ersten Experimenten vor allem durch die Art der Dimensionsreduktion.
Hierzu wird die sogenannte Kaktus-Darstellung aller minimalen Schnitte von
TSP Trägergraphen, welche innerhalb des Branch-and-Cut Verfahrens für das TSP anfallen, verwendet.
Ein Schnitt in einem Graph ist eine nichtleere echte Teilmenge der Knotenmenge.
Das Gewicht eines Schnitts ist die Summe der Gewichte der Kanten mit genau einem Endknoten im Schnitt.
Ein minimaler Schnitt ist ein Schnitt minimalen Gewichts.
Die Kaktus-Darstellung der Menge aller minimalen Schnitte eines Graphen kann als Datenstruktur angesehen werden welche die Inklusions- und Überlappungsstruktur der Menge der minimalen Schnitte unter Verwendung von wenig Speicher widerspiegelt.
Sie wurde erstmals Mitte der 70er Jahre von Dinitz et al. vorgeschlagen.
Die Kaktus-Datenstruktur wird verwendet, um TSP Trägergraphen aussichtsreich zu schrumpfen.
Für kleine geschrumpfte Graphen werden Schnittebenen in den linearen Beschreibungen von kleinen TSP Polytopen mittels des quadratischen Zuordnungsproblems (QAP) gesucht und eventuell geliftet.
Im Zuge der Arbeit wurde der Kaktus-Konstruktionsalgorithmus von Fleischer (1999) implementiert.
Dies ist als sehr seltene Implementierung eines derartigen Algorithmus anzusehen.
Es werden umfangreiche Rechenresultate präsentiert.
Das vorgestellte Verfahren zur Berechnung von Schnittebenen hat folgende Ähnlichkeit mit dem von Applegate et al. (1998,2001,2003) vorgeschlagenen im Concorde System enthaltenen local cut Verfahren:
In beiden Verfahren werden TSP Trägergraphen geschrumpft, Schnittebenen werden in niedrigdimensionalen Räumen gesucht und im Erfolgsfall geliftet.
Der Held Odysseus, König von Ithaka, hätte mit dem heutige Wissen zum TSP seine Irrfahrt durch das Mittelmeer sicherlich weit schneller als in 20 Jahren erledigen und wieder in den Armen seiner Gemahlin Penelope liegen können.
Inhaltsverzeichnis:Inhaltsverzeichnis:
1.Einleitung5
2.Das Traveling Salesman Problem7
2.1Anwendungen8
2.2Das TSP als schweres Optimierungsproblem8
2.3Lösungsansätze10
2.4Polyedertheorie und TSP-Polytope13
2.5Lösung des LP-Modells16
2.6Softwaresysteme zur Lösung von TSPs24
3.Minimale Schnitte in Graphen25
3.1Definitionen und Schreibweisen25
3.2Strukturbeschreibung der Menge M27
3.3Kettendarstellung von M30
3.4Berechnung minimaler Schnitte31
3.5Implementierung39
3.6Rechenergebnisse40
4.Kakteen43
4.1Definition43
4.2Beispiele44
4.3Eigenschaften von Kaktus-Darstellungen47
4.4Kanonisierung der Darstellung49
4.5Konstruktion des Kaktus K(G) zu einem Graphen G52
4.6Ka...