Kaktus-Repräsentation der minimalen Schnitte eines Graphen und Anwendung im Branch-and-Cut Ansatz für das TSP
- Art: Diplomarbeit
- Autor: Klaus Wenger
- Abgabedatum: Oktober 1999
- Umfang: 244 Seiten
- Dateigröße: 1,1 MB
- Note: 1,0
- Institution / Hochschule: Ruprecht-Karls-Universität Heidelberg Deutschland
- ISBN (eBook): 978-3-8324-7803-2
-
ISBN (Paperback) :
978-3-8324-7803-2 P - ISBN (CD) :978-3-8324-7803-2 CD
- Sprache: Deutsch
- Prämierung:
- Arbeit zitieren: Wenger, Klaus Oktober 1999: Kaktus-Repräsentation der minimalen Schnitte eines Graphen und Anwendung im Branch-and-Cut Ansatz für das TSP, Hamburg: Diplomica Verlag
- Schlagworte: Traveling Salesman Problem, Schnittebene, Graphentheorie, Optimierung, Diskrete Mathematik
In den Warenkorb
38,00 €
Diplomarbeit von Klaus Wenger
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:
| 1. | Einleitung | 5 |
| 2. | Das Traveling Salesman Problem | 7 |
| 2.1 | Anwendungen | 8 |
| 2.2 | Das TSP als schweres Optimierungsproblem | 8 |
| 2.3 | Lösungsansätze | 10 |
| 2.4 | Polyedertheorie und TSP-Polytope | 13 |
| 2.5 | Lösung des LP-Modells | 16 |
| 2.6 | Softwaresysteme zur Lösung von TSPs | 24 |
| 3. | Minimale Schnitte in Graphen | 25 |
| 3.1 | Definitionen und Schreibweisen | 25 |
| 3.2 | Strukturbeschreibung der Menge M | 27 |
| 3.3 | Kettendarstellung von M | 30 |
| 3.4 | Berechnung minimaler Schnitte | 31 |
| 3.5 | Implementierung | 39 |
| 3.6 | Rechenergebnisse | 40 |
| 4. | Kakteen | 43 |
| 4.1 | Definition | 43 |
| 4.2 | Beispiele | 44 |
| 4.3 | Eigenschaften von Kaktus-Darstellungen | 47 |
| 4.4 | Kanonisierung der Darstellung | 49 |
| 4.5 | Konstruktion des Kaktus K(G) zu einem Graphen G | 52 |
| 4.6 | Kakteen zu TSP-Trägergraphen | 64 |
| 4.7 | Implementierung der Kaktuskonstruktion | 67 |
| 4.8 | Rechenergebnisse zur Kaktuskonstruktion | 69 |
| 5. | Kontraktion von Trägergraphen | 73 |
| 5.1 | Das Ziel und Vorüberlegungen | 73 |
| 5.2 | Schrumpfbare Knotenmengen und 1-Pfade | 76 |
| 5.3 | Enumeration kontrahierter Graphen | 77 |
| 5.4 | Zwei Vorschläge für Kontraktionsalgorithmen | 79 |
| 5.5 | Implementierung | 85 |
| 5.6 | Rechenergebnisse | 87 |
| 5.7 | Vergleich der beiden Kontraktionsalgorithmen | 89 |
| 6. | Schnittebenenbestimmung | 91 |
| 6.1 | Separierung bei bekannter linearer Beschreibung | 91 |
| 6.2 | Liften von Ungleichungen | 93 |
| 6.3 | Rechenexperimente | 96 |
| 6.4 | Ein umfassendes Beispiel: pr76 | 99 |
| 7. | Zusammenfassung und Ausblick | 103 |
| A. | Quelltexte | 105 |
| A.1 | Berechnung minimaler Schnitte | 106 |
| A.2 | Kaktuskonstruktion | 131 |
| A.3 | Kontraktionsalgorithmen | 194 |
| A.4 | Hilfsmodule | 207 |
| A.5 | Ausführbare Programme | 223 |
| B. | Testgraphen | 233 |
von G dar, wobei Uj−1 := {u1 , . . . , uj−1 }. Ist λ(Uj−1 , uj ) > λ, so gibt es keine DAGDarstellung von (Uj−1 , uj )-Minimalschnitten. Die durch den H-O Algorithmus gelieferten DAG-Darstellungen stellen jeden Minimalschnitt von G genau einmal dar. Der Speicherbedarf daf¨ r ist quadratisch in n. u Man ben¨tigt zur Kaktuskonstruktion eine Kettendarstellung von M. W¨re (u1 , . . . , un ) o a eine Adjazenzordnung, so ließen sich die (U j−1 , uj )-Minimalschnitte bereits durch Ketten darstellen, denn nach Hilfssatz 3.21 liegen die u j enthaltenden geschachtelt. Da man im H-O Algorithmus zu geringe Wahlm¨glichkeiten f¨ r die neue Senke uj+1 hat, kann man o u nicht erzwingen, dass (u1 , . . . , un ) eine Adjazenzordnung ist. Sei (v1 , . . . , vn ) ab jetzt eine Adjazenzordnung der Knoten von G mit v 1 = 1. Es wird darum gehen, die DAGDarstellungen in (Vi−1 , vi )-Minimalschnitte darstellende Ketten umzuwandeln. [...]
In Abschnitt 3.4.3 haben wir mittels des H-O Algorithmus und der Arbeit [PQ80] aus G mehrere DAG-Darstellungen von gesamtminimalen (S, t)-Schnitten berechnet. Die Quellknotenmenge S ist dabei um ehemalige Senken gewachsen und neue Senken wurden nach einem festen Kriterium gew¨hlt (minimaler Distanzwert). Der Knoten 1 war a der erste Quellknoten in S. Jeder Knoten aus V \ {1} war genau einmal die Senke, der Knoten 2 war die erste Senke. Dies liefert die sogenannte Senkenordnung (u 1 , . . . , un ) der Knoten von G. Setze u1 := 1, u2 := 2, u3 := zweite Senke, . . . , un := letzte Senke. Die DAG-Darstellung zur Senke uj stellt f¨ r j = 2, . . . , n alle (Uj−1 , uj )-Minimalschnitte u [...]
Lisa Fleischer hat in [Fle98a, Fle98b] einen der schnellsten deterministischen Algorithmen zur Konstruktion des kanonischen Kaktus zu G angegeben. Die Konstruktion l¨uft uber 4 Stufen. Die erste stellt den Flaschenhals dar und basiert auf dem in Aba ¨ schnitt 3.4.3 vorgestellen Algorithmus von Hao und Orlin. Wird er mittels dynamischer B¨ume implementiert, so resultiert f¨ r ihn und den Kaktus-Konstruktionsalgorithmus a u 2 /m). In dieser Arbeit wurde die Variante mit Highest-Leveldie Laufzeit O(nm log n √ Pushing der Laufzeit O(n2 m) verwendet. Da der Flaschenhals der verbleibenden 3 Stufen O(n2 log n) ist, resultiert die √ Laufzeit O(n2 m) f¨ r den hier implementierten Kaktus-Konstruktionsalgorithmus. Neben [Fle98a] gibt es u weitere schnelle Konstruktionsalgorithmen f¨ r Kaktus-Darstellungen [NNI97]. u [...]
In den Warenkorb
38,00 €
Link zur Arbeit:
http://www.diplom.de/ean/9783832478032
Arbeit zitieren:
Wenger, Klaus Oktober 1999: Kaktus-Repräsentation der minimalen Schnitte eines Graphen und Anwendung im Branch-and-Cut Ansatz für das TSP, Hamburg: Diplomica Verlag
Schlagworte:
Traveling Salesman Problem, Schnittebene, Graphentheorie, Optimierung, Diskrete Mathematik
Entdecken Sie mehr zum Thema
