Polyedertheorie und Algorithmen für das Graphische Travelling-Salesman-Problem

• Applicant: Professor Dr. Gerhard Reinelt
• Subject Area: Mathematics
• Term: from 2005 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 17239119

Das Graphische Traveling-Salesman-Problem (GTSP) ist eine Verallgemeinerung des klassischen Traveling-Salesman-Problems (STSP). Wie beim STSP ist eine kürzeste Rundreise durch alle Knoten eines Graphen gesucht, beim GTSP ist es allerdings erlaubt, dabei Kanten und Knoten mehrfach zu benutzen. Beide Problem haben eine Fülle praktischer Anwendungen. In diesem Projekt sollen Beiträge zu polyedrischen Untersuchungen für die beiden Probleme sowie zur algorithmischen Lösung des GTSP auf Graphen mit wenigen Kanten durch Ausnutzung spezieller Struktureigenschaften geleistet werden. Zentral ist die Untersuchung der Beziehungen zwischen den dem STSP und dem GTSP zugeordneten Polyedern zueinander. Eine seit langem offene Vermutung bezüglich der Übertragbarkeit von facettendefinierenden Ungleichungen konnte kürzlich von uns widerlegt werden. Mit dazu entwickelten Techniken sollen offene Fragen, insbesondere bzgl. des 0-Node-Liftings bearbeitet werden. Weitere Forschung betrifft das GTSP-Polyeder auf Graphen mit wenigen Kanten. Algorithmen zur Lösung des GTSP transformieren üblicherweise das Problem zunächst auf ein STSP im vollständigen Graphen und wenden dann Methoden für das STSP an. Hierdurch wird zum einen möglicherweise die Variablenzahl drastisch von O(n) auf O(n2) erhöht und zum anderen wird eine eventuell vorhandene nutzbare Struktur des Eingabegraphen ignoriert. Basierend auf den theoretischen Untersuchungen soll ein neuer, Dekompositionsmöglichkeiten ausnutzender Algorithmus für das GTSP in Graphen mit wenigen Kanten entwickelt werden.

• DFG Programme: Research Grants