Problem des Handlungsreisenden: Durch absurde Touren zum Ziel

Christoph Pöppe

Vor einer Weile hatte ich Sie auf eine verallgemeinerte Bergwanderung mitgenommen. Es ging durch – möglicherweise – unwegsames Gelände in einem Raum mit vielen Dimensionen, und das Ziel war, den tiefsten Punkt dieses Geländes zu finden. Ich hatte die Wanderung dann – theoretisch – in die echten Alpen verlegt, weil man sich die Sache dann besser vorstellen kann. In hochdimensionalen Räumen lässt das Vorstellungsvermögen ja doch rapide nach.

Eine Weile später hatte ich vom Problem des Handlungsreisenden erzählt – nicht unbedingt, weil die Aufgabe, die kürzeste Tour durch eine große Anzahl von Städten zu finden, zu den größten Problemen der Menschheit zählen würde, sondern weil sie sich als Stellvertreter für eine große Klasse von Problemen eignet, unter denen in der Tat auch bedeutende zu finden sind: kombinatorische Optimierungsprobleme. Eigentlich geht es nur darum, eine endliche Menge von Objekten – zum Beispiel Reisezielen – in eine optimale Reihenfolge zu bringen. Und da es für endlich viele Objekte nur endlich viele Reihenfolgen gibt, könnte man sie alle durchprobieren und unter ihnen die beste auswählen.

Das scheitert sehr bald an der schieren Anzahl der Möglichkeiten. Für n Objekte gibt es n! (n-Fakultät) Reihenfolgen, das ist das Produkt aller Zahlen von 1 bis n, und das würde bereits für mittelgroße Werte von n alle Computer der Welt überfordern. Deswegen lässt man sein Computerprogramm nur eine Auswahl unter diesen unüberschaubar vielen Möglichkeiten abarbeiten. Man ändert eine vorhandene Tour nur ein bisschen ab, schaut nach, ob diese Änderung eine Besserung bringt, ändert weiter, nimmt gelegentlich eine Verschlechterung in Kauf, lässt den Zufall spielen …

Diese Strategie der kleinen Schritte hat eine gewisse Ähnlichkeit mit dem Verhalten unseres Bergwanderers. Der läuft in seinem vieldimensionalen Raum auch nur immer wieder ein kleines Stück und schaut, wie sich die Verhältnisse verändert haben. Nur hat sein Raum Koordinaten, ein Schritt ist eine kleine Veränderung dieser Koordinaten, und im Prinzip könnte man beliebig kleine Schritte machen.

Für den Kollegen in dem abstrakten Raum der Städtetouren gilt das nicht. Ein Schritt heißt, die Reihenfolge an wenigen Stellen ändern, und das geht entweder ganz oder gar nicht. Was sollte das auch heißen, dass man zur Hälfte die alte Tour läuft und zur anderen Hälfte die neue?

Jetzt kommt die Überraschung. Genau diese eigentlich absurde Idee macht aus dem kombinatorischen Optimierungsproblem eines mit Koordinaten, in dem man sich nicht nur sprunghaft, sondern eben stetig bewegen kann. Und das wiederum verhilft zu einer neuen Lösungsstrategie.

Die Grundidee geht so: Man hat n Städte und von jeder Stadt zu jeder anderen eine Verbindung – sagen wir Straße. Das macht insgesamt \( m = n(n-1)/2 \) Straßen. Diese Verbindungen sind die Koordinaten in unserem abstrakten Raum. Wenn eine Tour über eine gewisse Straße verläuft, dann schreiben wir in der entsprechenden Koordinate eine Eins, sonst eine Null. Eine Tour wird also ausgedrückt durch eine Folge von m Nullen und Einsen, in der genau n Einsen vorkommen müssen. Das ist ein Vektor in einem m-dimensionalen Raum.

Moment bitte. Sind das nicht schrecklich viele Dimensionen? Na ja: Nehmen wir eine Tour durch 100 Städte, also n = 100. Dann ist m = 9900/2 = 4950. Dagegen ist die Anzahl aller möglichen Touren \(100! = 9{,}3326 \cdot 10^{157} \), eine Zahl, gegenüber der die Anzahl der Atome im Universum, wie üblich, absolut mickrig aussieht. An diesen Unterschied muss man sich in der theoretischen Informatik gewöhnen: Wenn die Problemgröße n in der Formel für den Aufwand „unten“ steht wie in n², n³ oder auch n⁵⁰, dann geht das. Steht das n oben wie in 2ⁿ oder auch vor dem Ausrufezeichen wie in n!, dann geht, abgesehen von den kleinsten Werten für n, eigentlich gar nichts. Insbesondere ist die 4950 zwar eine stolze Zahl, aber im Bereich des Machbaren.

Jetzt kommt der absurde Teil. Wir lassen für die Werte der Koordinaten nicht nur 0 und 1 zu, sondern auch jeden Wert dazwischen. Also kann unser Handlungsreisender nicht nur von A nach B fahren, sondern zu einem Drittel von A nach B, zu 0,4 von A nach C und so weiter – allerlei Absurdes ist erlaubt. Damit ist der Bereich, innerhalb dessen sich unser gedachter Wanderer bewegen kann, ein „massiver“ m-dimensionaler Würfel: alle Vektoren mit m reellen Komponenten zwischen 0 und 1. Und der Wanderer muss nicht mehr von einem isolierten Punkt zum anderen hüpfen, sondern kann sich frei und stetig bewegen.

Das allein hilft noch nicht. Unser Würfel hat immerhin 2^m Ecken, und nur ein verschwindender Bruchteil von ihnen gehört überhaupt zu einer Tour. Wir haben den Raum der potenziellen Lösungen viel größer gemacht als zuvor – absurd viel. Jetzt muss es darum gehen, den Würfel massiv zurechtzustutzen, damit am Ende möglichst nur die eigentlich gesuchte Lösung übrigbleibt.

Die gute Nachricht: Jetzt ist das Problem so umformuliert, dass das Zurechtstutzen sehr einfach geht, und die Berechnung der Tourlänge ebenfalls. Jede Verbindung hat ja eine gewisse Länge, also ist die Länge einer Tour gleich Länge einer Straße mal der „Belegung“ dieser Straße, das heißt dem Ausmaß (Zahl zwischen 0 und 1), in dem der Reisende sie benutzt, diese Produkte aufsummiert über alle Straßen: das, was man ein Skalarprodukt zweier Vektoren nennt. Die Zielfunktion ist linear.

Wie stutzt man jetzt zurecht? Na ja, in einer gültigen Tour nutzt der Reisende zu jeder Stadt genau zwei Straßen: eine, um hin- und eine, um wegzukommen. Das kann man als lineare Bedingung formulieren: Die Summe der Belegungen aller Straßen, die zu Stadt A führen, muss gleich 2 sein. Gleichartige Bedingungen gelten für alle Städte. Wohlgemerkt: Zielfunktion und Bedingungen sind auch für absurde Touren wohldefiniert und berechenbar.

Im vertrauten dreidimensionalen Raum sieht das so aus: Gegeben ein fester Vektor v und eine Zahl c, dann sind die Punkte x, die die Bedingung \(x \cdot v = c\) (Skalarprodukt von x und v ist gleich c) erfüllen, genau die Punkte einer Ebene. Allgemein macht eine solche Bedingung aus einem p-dimensionalen Gebilde ein (p–1)-dimensionales, das aber immer noch so etwas ist wie ein Polyeder, also ein geometrischer Körper, der von lauter – verallgemeinerten – Ebenen begrenzt wird.

Eine Bedingung, die keine Gleichung, sondern eine Ungleichung ist – Skalarprodukt von x und v soll kleiner oder gleich c sein –, schneidet aus dem Klotz nicht einen niederdimensionalen Teilklotz aus, sondern wirkt wie ein Messer, das dem Klotz einen Teil wegschneidet (denken Sie an Käse), und zwar so, dass die Schnittfläche eben ist, oder allgemeiner, dass die Menge der zulässigen Punkte ein Polyeder bleibt.

Für lineare Zielfunktionen mit linearen Nebenbedingungen gibt es ein wohlerprobtes und erfolgreiches Verfahren: die Simplex-Methode. Sie besteht im Wesentlichen darin, dass man die Ecken des verallgemeinerten Polyeders abklappert: Der Wanderer sitzt auf einer Ecke; er wandert zu einer unter den benachbarten Ecken, deren Zielfunktion kleiner ist als die der aktuellen Ecke, und so weiter.

Benachbarte Ecken kann es zwar sehr viele geben (wir sind in einem hochdimensionalen Raum), aber das stört nicht besonders; denn in diesem Fall ist Gier ein guter Ratgeber. Wer immer nur abwärts geht, kann bei der Simplex-Methode nicht in einem lokalen Minimum steckenbleiben. Und theoretisch kann der Weg wegen der großen Zahl vorhandener Ecken zwar sehr lange dauern; in der Praxis passiert das eigentlich nie.

Sind wir damit am Ziel? Noch nicht wirklich. Bisher sind nämlich noch Pseudotouren erlaubt, solche, die aus zwei völlig getrennten Teiltouren bestehen. Auch die erfüllen nämlich die Bedingung, dass pro Stadt genau zwei Straßen benutzt werden. Um derartige Pseudotouren auszuschließen, muss man fordern, dass innerhalb jeder Teilmenge von k Städten weniger als k Straßen benutzt werden. (Präzise formuliert: Zu jeder k-elementigen Teilmenge von Städten muss die Summe der Belegungen über alle Straßen, deren Anfangs- und Endpunkt beide in dieser Teilmenge liegen, kleiner als k sein. Sonst hätte man eine geschlossene Tour, die gänzlich innerhalb der Teilmenge verläuft. Diese Bedingung ist auch für absurde Touren definiert.) Das ist so eine typische lineare Ungleichungs-Nebenbedingung.

Aber o weh! Teilmengen gibt es viele. Bei n Städten sind es 2ⁿ Stück, und das ist eine von den echt großen Zahlen. Alle Teilmengen durchzugehen ist also aussichtslos – und überflüssig zugleich, denn nur allzu oft trifft das Käsemesser keinen Käse mehr, sondern schlägt in die Luft, weil ein anderes Messer dort schon alles weggeschnitten hat. Aber die richtige Auswahl unter den Teilmengen zu treffen ist wieder schwierig, und man ist zuweilen doch wieder aufs Probieren angewiesen.

Selbst wenn man mit der Simplex-Methode den optimalen Punkt des Polyeders gefunden hat – dann ist dieser Punkt im Allgemeinen absurd! Also muss man den zulässigen Punkt (mit Einsen und Nullen im Tourvektor) finden, der dem absurden Optimum am nächsten kommt, und das ist in hohen Dimensionen auch wieder mühsam.

Immerhin findet man auf diesem Wege obere und untere Schranken für die Tourlänge, also Aussagen darüber, wie lang die optimale Tour mindestens sein muss und wie lang sie höchstens sein kann. Und wenn beide Schranken zusammenfallen, hat man eine exakte Lösung des Problems gefunden.

Was ich Ihnen hier erzähle, habe ich selbst gelernt, als ich 1999 den Artikel „Die optimierte Odyssee“ von Martin Grötschel und Manfred Padberg (hier eine Version mit Abbildungen) für „Spektrum der Wissenschaft“ bearbeitete. Damals verwendeten die Autoren als durchgehendes Beispiel die Irrfahrten des Odysseus, aus der moderne Philologen eine Tour mit 16 Stationen herausinterpretiert hatten. Für n = 16 und dementsprechend m = 120 konnte nämlich damals ein Arbeitsplatzrechner gerade noch alle 653837184000 denkbaren Touren durchrechnen – was immerhin vier Tage gedauert hat. Der Weltrekord für die exakte Lösung eines Handlungsreisenden-Problems stand bei 13509 Städten (sämtliche Gemeinden der USA ohne Alaska und Hawaii).

Das sind Nachrichten aus einer fernen Vergangenheit. Immerhin hat sich nach dem Moore’schen Gesetz die Rechenleistung der Computer alle 11 Jahre um den Faktor 1000 verbessert. Was damals eine Weltrekordleistung war, ist für einen heutigen Supercomputer eine kleine Aufwärmübung. Mittlerweile wetteifern die Fachleute darum, die kürzeste Tour durch 1904711 Städte auf der ganzen Welt zu finden , und die derzeit beste Lösung ist nur noch höchstens 0,05 Prozent länger als die (bislang unbekannte) optimale.

Aber: Die Verfahren, über die ich berichtet habe, sind nach wie vor aktuell. Auch in den genannten Rekordversuchen kommt ein „linear solver“ zum Einsatz, das heißt ein Programm zur Optimierung einer linearen Zielfunktion mit linearen Nebenbedingungen. Die Neuigkeiten bestehen, neben dem gigantischen Anwachsen der Rechenleistung, vor allem in den Vor- und Nachbereitungen, die den linear solver erst richtig effizient machen – und die ich Ihnen in diesem Text erspart habe. Wer mehr wissen will, findet unter den Stichworten „branch and cut“ und „branch and bound“ reichlich Material im Internet.

The post Problem des Handlungsreisenden: Durch absurde Touren zum Ziel originally appeared on the HLFF SciLogs blog.