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

ISBN-13: 9783838678030 / Niemiecki / Miękka / 2004 / 250 str.

Klaus Wenger

Opis

Diplomarbeit aus dem Jahr 1999 im Fachbereich Mathematik - Angewandte Mathematik, Note: 1,0, Ruprecht-Karls-Universitat Heidelberg (Mathematik), Sprache: Deutsch, Abstract: Inhaltsangabe: Zusammenfassung: Diese Diplomarbeit leistet einen Beitrag zur algorithmischen Losung des Problems des Handelsreisenden (Traveling Salesman Problem, TSP). Der Handelsreisende sucht eine kurzeste Rundreise durch eine fest gegebene Menge von Stadten, wobei die Weglangen zwischen je zwei Stadten bekannt sind. Die Anwendungen des TSPs gehen weit uber Fahrtroutenoptimierung hinaus. Das erfolgreichste Verfahren zur exakten Losung 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 Tragergraphen, welche innerhalb des Branch-and-Cut Verfahrens fur 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 Uberlappungsstruktur 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 Tragergraphen aussichtsreich zu schrumpfen. Fu