Odysseus, der sagenhafte König von der griechischen Insel Ithaka, hatte eine lange Reise hinter sich, als er nach 20 Jahren seine Penelope endlich wieder in die Arme schließen konnte – Stoff für ein ganzes Epos, die "Odyssee" des antiken Dichters Homer. Moderne Interpreten haben aus ihr 16 Orte im Mittelmeerraum herausgelesen, die er besucht haben soll (kleines Bild unten).

Er hätte es zweifellos kürzer haben können, wären da nicht das Schicksal, die Launen des Meeres, die Mißgunst der Götter und vor allem der mangelnde Überblick über die Geographie gewesen. Versetzen wir Odysseus in die moderne Zeit: Stellen wir uns einen Topmanager oder – prosaischer – Handelsvertreter (travelling salesman) vor. Er will alle 16 Städte in beliebiger Reihenfolge besuchen, und zwar auf dem kürzestmöglichen Wege – Zeit ist Geld. Das ist das berühmte travelling salesman problem (TSP): schnell formuliert, höchst praxisrelevant, scheinbar harmlos, in Wirklichkeit aber – für große Städteanzahlen – so schwer, daß die Mathematiker sich auch nach Jahrzehnten harter Arbeit die Zähne daran ausbeißen.

Mehr noch: Das TSP ist nur das einleuchtendste Beispiel aus einer ganzen Klasse von Problemen. Sie finden sich überall da, wo es gilt, unter Kombinationen von sehr vielen Möglichkeiten die günstigste zu finden. Beispielhaft für die unübersehbar vielen Anwendungen seien genannt:

• Zuweisung von Ladung und Personal an Lastwagen oder Frachtflugzeuge,

• Maschinenbelegung,

• Fahrplangestaltung,

• Entwurf von Mikrochips,

• Kapitalanlageplanung und

• die Gestaltung von Kommunikations-

netzen.

Für das Problem des Odysseus ergibt sich als kürzeste Rundreise eine Tour von 6859 Kilometern Länge (Kasten Seite 84 rechts unten). Die Entfernungen zwischen je zwei Städten haben wir in Luftlinie gemessen (und auf ganze Kilometer gerundet); aber selbst mit dem Flugzeug hätte Odysseus in der von ihm gewählten Reihenfolge 9913 Kilometer zurücklegen müssen. Optimierung kann also erhebliche Einsparungen bringen!

Wie haben wir nun die kürzeste Rundreise für Odysseus gefunden? Irgendwelche Touren zu finden ist nicht schwer: Es stehen 653837184000 Möglichkeiten zur Auswahl. Wir haben alle diese Touren durchprobiert und ihre Längen berechnet (Kasten auf Seite 78). Das hat auf einem üblichen Arbeitsplatzrechner immerhin 92 Stunden – fast vier Tage – gedauert.

Diese Enumeration ist der klassische Ansatz zur Lösung von kombinatorischen Optimierungsproblemen, das heißt solchen mit endlich vielen Auswahlmöglichkeiten. Es steckt nichts dahinter als die gedankenlose Anwendung roher Gewalt; aber diese Methode lebt immer noch in einigen (etwas angestaubten) Köpfen fort. Nur scheitert sie bereits an Problemen, die geringfügig größer sind als die Reiseplanung des Odysseus. Wir haben dieses Beispiel unter anderem deswegen gewählt, weil es mit heutzutage vorhandenen Computern gerade noch mittels Enumeration lösbar ist. Bereits 25 Städte würden die größten Supercomputer mit den ausgefeiltesten Enumerationstechniken hoffnungslos überfordern.

Praktische Probleme sind jedoch deutlich größer – und werden trotzdem gelöst. Erst im vergangenen Sommer haben David Applegate, Robert Bixby und William Cook von der Rice-Universität in Houston (Texas) sowie Vasek Chvatal von der Rutgers-Universität in New Brunswick (New Jersey) mit den hier beschriebenen Methoden die kürzeste Rundreise durch mehr als 13000 Städte gefunden (Bild oben) und damit ihren bisherigen Rekord von 7397 Städten weit hinter sich gelassen. Solche und noch weit größere Probleme treten täglich in der Produktion von Leiterplatten (Kasten Seite 79), beim Entwurf höchstintegrierter Schaltkreise, in der Röntgenkristallographie und in vielen anderen Gebieten auf.

Am Anfang der Analyse steht eine mathematische Formalisierung. Beim TSP ersetzt man jede Stadt durch einen Punkt, einen sogenannten Knoten, und jede direkte Verbindung zwischen zwei Städten durch eine Linie (Mathematiker sagen: Kante) zwischen den entsprechenden Knoten. Ein Gebilde aus Knoten mitsamt Kanten dazwischen heißt ein Graph. Wenn, wie beim Problem des Odysseus, jeder Knoten mit jedem anderen durch eine Kante verbunden ist – man kann von jeder Stadt direkt zu jeder anderen fliegen –, sprechen die Fachleute von einem vollständigen Graphen. Der vollständige Graph mit 16 Knoten hat genau 120 Kanten.



Mathematische Modellierung: Aus einer Rundreise wird ein Graph


An jede Kante wird nun die Streckenlänge zwischen den zugehörigen Knoten angeschrieben – allgemeiner formuliert: die "Kosten" (Zeit, Geld, Material, oder was einem sonst lieb und teuer ist), die das Durchlaufen dieser Kante verursacht. Jede Reise entspricht einer Teilmenge der Kanten. Wenn eine solche Teilmenge eine komplette Rundreise durch alle Knoten bildet, wird sie Tour oder Hamilton-Kreis genannt, nach dem irischen Mathematiker Sir William Hamilton (1805 bis 1865). Die Länge einer Tour ist die Summe der einzelnen Kantenlängen. Das TSP ist also, graphentheoretisch formuliert, die Aufgabe, die kürzeste Tour in einem vollständigen Graphen zu finden; genauer: eine kürzeste Tour, denn es kann verschiedene Touren mit der gleichen minimalen Länge geben.

Warum ist nun das TSP so schwierig? Liegt es daran, daß die Zahl der Touren für große Städtezahlen so ungeheuer groß ist? Erstaunlicherweise nein. Die Anzahl möglicher Lösungen ist kein brauchbares Maß für die Schwierigkeit eines kombinatorischen Problems.

Betrachten wir als Gegenbeispiel folgendes Problem. Zwischen den 16 Städten soll ein Kommunikationsnetzwerk errichtet werden, das jede Stadt mit jeder anderen verbindet, möglicherweise auf dem Umweg über weitere Städte. Wieder gehören zu einer Direktverbindung (Kante) zwischen zwei Städten gewisse – entfernungsabhängige – Kosten, etwa für die Verlegung eines Glasfaserkabels. Die teuerste Lösung besteht im vollständigen Graphen: Jede Stadt ist auf direktem Wege mit jeder anderen verbunden.

Für dieses Problem gibt es ein sehr einfaches Verfahren zur Kostensenkung: Wir entfernen aus dem jeweiligen Graphen die teuerste Kante, die wir überhaupt entfernen können, ohne daß das Netz in zwei unzusammenhängende Teile zerfällt, und das immer wieder, bis nichts mehr geht. Für die 16 Städte des Odysseus ergibt sich nach diesem Verfahren ein Netzwerk mit einer Gesamtlänge von 4540 Kilometern (siehe Karte unten).

Der beschriebene Algorithmus wählt also in jedem Moment unter den verfügbaren Möglichkeiten die günstigste, in diesem Falle die mit der größten Kostensenkung, ohne Rücksicht darauf, ob er sich damit nicht eine insgesamt gesehen viel bessere Lösung verbaut. Ein solches Verhalten – nehmen, was man kriegen kann, ohne auf die Spätfolgen zu sehen – nennt man gierig (greedy). Normalerweise ist es sinnvoll, auf der Suche nach dem größten Vorteil vorübergehend einen Nachteil in Kauf zu nehmen. Aber in diesem Fall ist blinde Gier genau das Richtige! Man kann beweisen, daß dieser Algorithmus stets eine optimale, das heißt kostenminimale Lösung des Problems liefert.

Wie viele mögliche Lösungen gibt es für dieses Problem? Bei n Städten ist jeder Graph mit genau n-1 Kanten, der keinen geschlossenen Rundweg durch einen Teil der Knoten enthält, eine mögliche Lösung. Solche Graphen heißen aufspannende Bäume (spanning trees) oder Gerüste (vergleiche Spektrum der Wissenschaft, April 1995, Seite 10). Arthur Cayley (1821 bis 1895) bewies bereits 1889, daß es für n Städte genau nn-2 verschiedene aufspannende Bäume gibt. Für 16 Städte beträgt diese Zahl 72057594037927936. Das ist beträchtlich mehr als die Anzahl der möglichen Rundreisen im Problem des Odysseus; und das gilt allgemein für beliebige (große) Städtezahlen. Trotzdem läßt sich unter diesen vielen Lösungen eine optimale auf einem PC innerhalb weniger Millisekunden errechnen.

Wenn es also nicht die Anzahl der möglichen Lösungen ist: Was macht das TSP zu einem so schwierigen Problem? Um ehrlich zu sein, wir kennen die Antwort selber nicht. Immerhin gibt es die Komplexitätstheorie, die zwischen "leichten" Problemen wie dem des aufspannenden Baumes und "schwierigen" wie dem TSP zu unterscheiden hilft. Die Theorie liefert ein unangenehmes Ergebnis: Sehr viele praktisch relevante kombinatorische Probleme sind als "schwierig" zu klassifizieren.

Schon durch eine geringfügige Veränderung kann aus einem leichten Problem ein schwieriges werden. Nehmen wir an, wir legten bei unserem Kommunikationsnetzwerk Wert auf eine gewisse Ausfallsicherheit: Es soll auch dann noch funktionieren, wenn ein Feuer, ein Erdbeben oder auch nur der Fehlgriff eines Baggers eine Leitung zerstört. Ein aufspannender Baum bietet solche Sicherheit ja gerade nicht: Durch eine Unterbrechung an irgendeiner Stelle zerfällt das Netz in zwei Teile, die nicht mehr miteinander reden können.

Solch naheliegende Aspekte werden in der Realität nicht immer berücksichtigt. Als in den regionalen Telephonnetzen der USA die Kupferdrähte durch Glasfaserkabel ersetzt wurden, begnügte man sich wegen der hohen Kosten mit Minimallösungen – und hatte hinterher katastrophale Ausfälle zu beklagen, so den völligen Zusammenbruch des Chicagoer Telephonnetzes im Jahre 1988. Daraufhin waren sehr kostspielige Nachbesserungen vorzunehmen.

Je mehr zusätzliche Leitungen es gibt, desto größer ist die Ausfallsicherheit. Das Optimale unter diesem Aspekt ist der vollständige Graph; aber der ist zu teuer. Man muß also die Ausfallsicherheit gegenüber den Kosten der Konstruktion und Wartung abwägen. In aller Regel gibt es dabei wichtige und weniger wichtige Verbindungen beziehungsweise Städte; man wird Prioritäten vergeben. Solche Zusatzbedingungen sind mühelos in die mathematische Formulierung des Problems einzubringen; das ist das Schöne an den kombinatorischen Ansätzen. Leider wird dabei aus einem leichten Problem ein schwieriges – ebenso schwierig wie das TSP im allgemeinen Fall.

Eine mögliche (und übliche) Formulierung des Problems ist folgende. Wir vergeben Wichtigkeitswerte für die einzelnen Städte: 0 für die unbedeutenden, 1 für die wichtigeren, 2 für die großen Städte und so weiter, und fordern, daß eine Stadt der Wichtigkeit j mit jeder Stadt gleicher oder größerer Wichtigkeit verbunden bleiben soll, selbst wenn j beliebige Direktverbindungen ausfallen. Unter allen Netzen, die diese Bedingung erfüllen, ist dasjenige mit den geringsten Kosten gesucht. In ähnlicher Form kann man Forderungen nach Sicherheit gegenüber dem Ausfall von Knoten oder von Knoten und Kanten zugleich in das Problem einbringen (Kasten Seite 80).

Probleme der Praxis enthalten häufig noch eine Fülle weiterer Nebenbedingungen; zum Beispiel kann eine Leitung oder ein Verbindungsrechner nur eine gewisse Anzahl von Gesprächen zugleich bewältigen. Durch sie wird die Anzahl der zulässigen Lösungen noch kleiner, aber das Problem nicht einfacher – im Gegenteil.

Soweit die Probleme. Wie findet man nun gute oder gar optimale Lösungen, und wie erfährt man, wie gut eine bestimmte Lösung ist, die der Computer ausspuckt? Bei allen – wichtigen – Unterschieden zwischen den Problemklassen gibt es einige Grundprinzipien.



Obere und untere Schranken


Gehen wir zunächst davon aus, daß eine gewisse Zielfunktion – Reiseweg, Kosten und so weiter – zu minimieren ist. (Maximierungsprobleme unterscheiden sich von Minimierungsproblemen nur durch das Vorzeichen.) Wir tragen in Gedanken den Wert jeder überhaupt zulässigen Lösung auf der reellen Zahlengeraden ein. Daß es eine optimale Lösung geben muß, ist klar: Es gibt ja nur endlich viele Lösungen, und unter endlich vielen reellen Zahlen gibt es stets eine kleinste. Wir wissen nur nicht, wo auf der Zahlengeraden sie liegt. Nun gilt es diesen unbekannten Wert irgendwie einzugrenzen, obere und untere Schranken auf der Zahlengeraden zu finden. Ohne die optimale Lösung zu kennen, wüßte man dann immerhin, daß sie nicht schlechter ist als die obere Schranke, aber auch nicht besser als die untere.

Obere Schranken zu finden ist nicht schwer. Jede zulässige Lösung ist eine, denn eine optimale Lösung ist per definitionem nicht schlechter als diese beliebige Lösung. Interessant sind natürlich Lösungen, die dem Optimum möglichst nahekommen. Algorithmen, die (möglichst gute) zulässige Lösungen und somit obere Schranken für den Optimalwert liefern, heißen im Fachjargon Heuristiken.

Auch die Auskunft, daß keine Lösung besser sein kann als ein gewisser Wert, eben eine untere Schranke, ist hilfreich: Treffen die obere und die untere Schranke zusammen, ist damit bewiesen, daß die zur oberen Schranke gehörige Lösung optimal ist. Wenn das – wie meistens – nicht der Fall ist, weiß man immerhin, wie weit man höchstens noch vom Optimum entfernt ist. Wenn diese Abweichung hinreichend klein ist, liefert das einen guten Grund, die Arbeit einzustellen: Selbst im Erfolgsfall würde die weitere Suche nicht viel einbringen.

Für die Suche nach einer unteren Schranke ist ebenfalls eine geeignete mathematische Formulierung zu finden. Besonders geschickt ist es, abwechselnd nach oberen und nach unteren Schranken zu suchen und bei jedem Suchschritt die Informationen aus den vorangegangenen Schritten mitzuverwerten. Dieser Kombinationsstrategie sind die enormen Fortschritte der letzten Jahre zu verdanken.

Techniken zur Ermittlung von beiderlei Schranken wollen wir nun wieder am Beispiel des Odysseus diskutieren. Für andere schwierige Probleme hört sich die Geschichte nur geringfügig anders an; allerdings kann durch diese kleinen technischen Details das Problem abermals erheblich schwerer werden.

Für die Suche nach einer brauchbaren oberen Schranke ist zunächst abermals Gier – genauer: kurzsichtiges Streben nach Kostenminimierung – ein guter Ratgeber. Von jeder Stadt aus fahre man in die nächstgelegene noch nicht besuchte Stadt (Nearest-Neighbour-Heuristik). Wenn keine Stadt mehr übrig ist, kehre man zum Ausgangspunkt zurück.

Wer dieses Verfahren mit Papier und Bleistift an beliebigen Ansammlungen von Städten durchspielt, bemerkt sehr schnell zweierlei. Erstens: Das Resultat einer Heuristik hängt stark vom Ausgangspunkt ab. Zweitens: Eine solche Lösung ist leicht zu verbessern. Wenn sich etwa zwei Kanten überschneiden, ist es günstiger, in dem Viereck aus den vier beteiligten Städten nicht die Diagonalen entlang zu reisen, sondern zwei gegenüberliegende Seiten. Möglicherweise gewinnt man auch etwas, wenn man zwei solche Seiten eines Vierecks durch die beiden anderen ersetzt. Es gibt weitere Verbesserungsschritte dieser Art.

Um aus solchen Ideen eine brauchbare Methode zu machen, muß man etwas gegen die ungünstigen Folgen der Gier tun. Wer immer nur darauf besteht, eine Lösung zu verbessern, läuft Gefahr, in einem schlechten "lokalen Optimum" steckenzubleiben: einer Lösung, die nicht besonders gut ist, aber durch keine einzelne der verfügbaren Änderungen besser wird. Man muß also – vorübergehend, mit einer gewissen Wahrscheinlichkeit, bis zu einem gewissen Ausmaß oder unter anderen Einschränkungen – zulassen, daß ein solcher Austauschschritt eine Lösung verschlechtert, oder ab und zu per Zufall eine völlig neue heuristische Lösung erzeugen. Derartige Methoden haben meist unterhaltsame Namen wie Monte-Carlo-Methoden, Simulated Annealing, Evolutionsverfahren oder Sintflut-Algorithmus (Spektrum der Wissenschaft, Juli 1987, Seite 104, und März 1993, Seite 42).

Der Programmieraufwand ist bei diesen Methoden für Probleme mittlerer Größe in der Regel relativ gering. Aus diesem Grunde sind sie zu einem beliebten Tummelplatz für Amateure geworden, was – unglücklicherweise – zu völlig überzogenen Erwartungen an ihre Güte und Durchführbarkeit geführt hat. Für TSPs mit Zehntausenden oder Hunderttausenden von Knoten (solche Größenordnungen sind nicht ungewöhnlich) müssen dann doch komplizierte Datenstrukturen und raffinierte Tricks der Informatik hinzukommen, damit man brauchbare Lösungen in akzeptabler Zeit findet. Andererseits sind heuristische Algorithmen, die in einem längeren Experimentierprozeß dem speziellen Problemtyp angepaßt wurden, aufgrund gegenwärtiger technologischer Grenzen zum Arbeitspferd für die Lösung praktischer Probleme geworden und auch für die exakten Optimierungsmethoden in mancherlei Hinsicht hilfreich.

Wie findet man nun eine untere Schranke zum Optimalwert? Die – nur scheinbar paradoxe – Grundidee ist, das Problem größer zu machen, damit es einfacher wird. Das bedeutet: Zu unserem Problem konstruieren wir ein weiteres, das mehr Lösungen hat: Jede Lösung des alten Problems ist auch eine des neuen (aber nicht notwendig umgekehrt). Zum Beispiel könnte man Nebenbedingungen des ursprünglichen Problems lockern oder außer Kraft setzen. Die Lösungsmenge des ursprünglichen Problems ist also in der des neuen Problems enthalten ("eingebettet"); die Fachleute sprechen von embedding techniques.

Eine minimale Lösung des großen Problems hat per definitionem geringere Kosten als jede andere Lösung, also auch geringere als – oder höchstens gleich große wie – jede Lösung des ursprünglichen, eingebetteten Problems. Also ist sie das, was wir suchen: eine untere Schranke für den Optimalwert des ursprünglichen Problems.

Damit diese Idee etwas einbringt, sollte das einbettende Problem einerseits einfach sein, damit seine minimale Lösung leicht zu finden ist, andererseits dem ursprünglichen möglichst ähnlich. Nur dann kann man hoffen, daß auch die Minimallösung des großen Problems derjenigen des eingebetteten Problems nahe kommt. Es ist keine Kunst, ein TSP in irgendein größeres Problem einzubetten. Man könnte Odysseus die Freiheit geben, sich überhaupt nicht zu bewegen. Nur ist die untere Schranke, die man daraus gewinnt – jede Tour ist länger als null Kilometer –, nicht besonders aufschlußreich.



Untere Schranken aus der linearen Programmierung


Unter den verschiedenen Einbettungstechniken wollen wir hier lediglich die erfolgreichste diskutieren. Sie basiert auf der linearen Programmierung, einer der bedeutsamsten Techniken, welche die angewandte Mathematik seit dem Zweiten Weltkrieg hervorgebracht hat (siehe "Wirtschaftsfaktor lineare Programmierung" von Robert G. Bland, Spektrum der Wissenschaft, August 1981, Seite 118).

Der – überkommene – Name ist irreführend; es geht nicht in erster Linie ums Programmieren. Eine zutreffende Bezeichnung wäre "Optimierung linearer Probleme". Häufig wird sie interpretiert als die Kunst, knappe Ressourcen in optimaler Weise wirtschaftlichen Aktivitäten zuzuordnen. Sie ist heute Standardwerkzeug zur Lösung von Planungsproblemen bei Fluggesellschaften, Ölraffinerien, Banken, Autoherstellern und vielen anderen Firmen.

Um nun das Problem des Odysseus in ein lineares Optimierungsproblem einzubetten, notieren wir zunächst sämtliche 120 Direktverbindungen zwischen den 16 Städten – in einer beliebigen Reihenfolge – und schreiben neben jede dieser Verbindungen eine Eins, wenn Odysseus sie auf seiner Rundreise benutzt, eine Null sonst. Jede Tour wird also beschrieben durch 120 Zahlen. Wir sprechen von einem Vektor der Dimension 120, denn wir wollen nun jede Folge von 120 Zahlen als einen Punkt (oder eben einen Vektor) in einem Raum der Dimension 120 auffassen, ebenso wie jede Folge dreier Zahlen (x,y,z) einen Punkt im gewöhnlichen dreidimensionalen Raum beschreibt.

Jede Tour entspricht also einem Punkt in diesem 120-dimensionalen Raum – aber nicht umgekehrt! Damit ein Punkt einer Tour entspricht, müssen genau 16 der Komponenten gleich eins und die übrigen 104 gleich null sein. Weitere Bedingungen sind zu erfüllen (siehe Kasten Seite 82).

Wir erinnern uns, daß es genau 653837184000 mögliche Rundreisen für Odysseus gibt. Aus so vielen Punkten im 120-dimensionalen Raum möchten wir einen auswählen, bei dem die Summe der Kilometerzahlen, die zu den Komponenten mit dem Wert 1 gehören, möglichst gering ist. Wir multiplizieren also jede Komponente unseres Vektors – 1 oder 0 – mit der zugehörigen Kilometerzahl, addieren alle Produkte auf und erhalten die Gesamtlänge der Tour.

Jetzt kommt der entscheidende Schritt. Wir fassen die Komponenten unseres Vektors als Variable auf, die außer 0 und 1 auch jeden beliebigen Wert dazwischen annehmen dürfen. Das ist vom ursprünglichen Problem her gesehen ziemlich albern: Was soll das heißen, daß Odysseus ein halbes Mal von Ithaka nach Troja fliegt oder 0,17 mal von Messina nach Gibraltar? Es ist aber für unsere Zwecke sinnvoll, denn wir erweitern zwar gewaltig die Menge der zulässigen Lösungen, bringen aber zugleich das Problem in die Reichweite der linearen Programmierung. Die Zielfunktion – die Gesamt-Tourlänge – ist nämlich eine lineare Funktion der 120 Variablen: Jede Änderung in einer der Variablen wirkt sich mit einem Proportionalitätsfaktor – nämlich der Länge der entsprechenden Teilstrecke – auf den Wert der Zielfunktion aus. Die Nebenbedingungen sind ebenfalls linear (siehe Kasten oben).

Für die Suche nach dem Minimum einer linearen Funktion mit linearen (Gleichungs- oder Ungleichungs-)Nebenbedingungen gibt es ein effizientes Verfahren, den Simplex-Algorithmus. (Die seit etwa zehn Jahren intensiv erforschten Innere-Punkte-Verfahren bringen für unsere Zwecke noch keine Vorteile ein.)

Ein wenig Geometrie ist hilfreich, auch wenn unser Vorstellungsvermögen nur drei statt 120 Dimensionen erfaßt. Nehmen wir alle Punkte (Vektoren) mit Koordinaten zwischen 0 und 1. Sie bilden einen Würfel der Kantenlänge 1 mit einer Ecke im Nullpunkt. Die Ecken dieses Einheitswürfels sind die Vektoren, deren Komponenten sämtlich gleich 0 oder 1 sind. Das gilt auch in 120 Dimensionen, nur hat der Einheitswürfel jetzt 2120 Ecken; die kann man unmöglich eine nach der anderen absuchen. Eine lineare Ungleichungs-Nebenbedingung ist wie ein Messer, das von dem Würfel (denken wir ihn uns aus Käse) ein Stück abschneidet. Es entsteht ein von ebenen Flächen begrenzter Körper.

Im 120-dimensionalen Raum ist die Menge der zulässigen Punkte, das heißt derjenigen, die sämtliche (linearen) Nebenbedingungen erfüllen, die Verallgemeinerung eines solchen Körpers: ein (konvexes) Polytop. Das Minimum einer linearen Zielfunktion auf einem Polytop wird stets in einer Ecke angenommen (oder allenfalls in mehreren Ecken und allem, was dazwischen ist, zugleich). Der Simplex-Algorithmus sucht systematisch (auch hier einem Gier-Prinzip folgend) die Ecken des Polytops ab, bis er nicht mehr weiterkommt; die Ecke, an der er stehenbleibt, ist dann das gesuchte Minimum (oder eines von mehreren gleichberechtigten).

Leider handelt es sich nur um das Minimum des erweiterten Problems, nicht um das des ursprünglichen. Im allgemeinen hat also der Lösungsvektor, den der Simplex-Algorithmus liefert, keine ganzzahligen Koordinaten. Man muß demnach das Käsemesser nochmals ansetzen, um aus dem Polytop des linearen Problems das "echte" Polytop des ursprünglichen Problems zu machen; das ist das kleinste Polytop, das sämtliche Inzidenzvektoren von Touren enthält (Kasten Seite 84).

Das gelingt jedoch nicht mit einem Schnitt. Schlimmer noch: Wir wissen nicht einmal genau, wie wir schneiden müßten. Explizite lineare Programme für Rundreiseprobleme sind bislang für höchstens 9 Städte bekannt. Genauer gesagt: Das mit dem 9-Städte-TSP assoziierte Polytop hat 9 Gleichungen und 42104442 Ungleichungen mit 36 Variablen, entsprechend den 36 möglichen direkten Verbindungen zwischen 9 Punkten. Für Polytope mit 8 (7 und 6) Städten gibt es entsprechend 194187 (3437 beziehungsweise 100) Ungleichungen mit 28 (21 beziehungsweise 15) Variablen. Für zehn Städte sind es wahrscheinlich 51043900866 Ungleichungen, mit Sicherheit nicht weniger; der Beweis für diese Vermutung steht noch aus. Für größere Rundreiseprobleme ist noch nicht einmal theoretisch ein vollständiges Sortiment von Ungleichungen bekannt, welches das echte Polytop beschreibt. Und selbst wenn es bekannt wäre, würde es, da zu groß, nicht viel helfen. Für allgemeine, größere Städtezahlen wird es möglicherweise nie gefunden werden, und das wäre ein weiterer Beweis der enormen Schwierigkeit des travelling salesman problem.

Für das 16-Städte-Problem des Odysseus ist die Anzahl der Ungleichungen auf jeden Fall astronomisch hoch. Immerhin kann man stets eine lineare Ungleichung (entsprechend der Verallgemeinerung eines ebenen Schnittes) finden, die den bisher ermittelten Minimalpunkt vom echten Polytop trennt. Diese Ungleichung fügt man dem System der bisherigen Ungleichungen hinzu, optimiert aufs neue und findet einen neuen Minimalpunkt, der dem echten Polytop näher liegt.

Wenn man Glück hat, liegt er sogar auf dem echten Polytop; dann hat man eine minimale Lösung des ursprünglichen Problems erzielt. In der Regel aber hat er wieder keine ganzzahligen Koordinaten, und man muß das Verfahren wiederholen.

Ein weiteres Problem kommt hinzu. Man kann im allgemeinen noch nicht einmal mit dem Polytop der zulässigen Punkte des linearen Optimierungsproblems anfangen. Dazu müßte man nämlich sämtliche Nebenbedingungen berücksichtigen, und das sind für große Städtezahlen ebenfalls astronomisch viele. Gleichwohl gelingt es, weitaus größere Probleme mit Methoden der linearen Programmierung optimal zu lösen. Wie ist das möglich?

Wir ersetzen abermals das Problem durch ein größeres, einfacheres: Von den astronomisch vielen Nebenbedingungen verwenden wir nur eine sehr kleine Teilmenge (wir beschneiden den Käsewürfel nur sehr grob), finden einen Lösungsvektor, das heißt eine optimale Ecke des zu großen Polytops, und bessern dann erst nach: Wir führen eine Nebenbedingung ein, die mit der bisher gefundenen Ecke gleich ein möglichst großes Stück Käse abschneidet.

Beim Problem des Odysseus können wir uns zunächst auf die (Gleichungs-) Nebenbedingungen beschränken, daß jede Stadt nur mit zwei Wegen an der Tour beteiligt sein darf: dem Weg in die Stadt hinein und dem aus ihr heraus. (Eine Gleichungs-Nebenbedingung reduziert im Gegensatz zu einer Ungleichung die Dimension des Polytops, was sich leider mit Käse nicht mehr veranschaulichen läßt.)

Die Lösung des entsprechenden linearen Programms liefert einen Minimalwert von 6113 Kilometern für die Zielfunktion. Das ist immerhin schon eine brauchbare untere Schranke. Allerdings besteht diese Lösung (Kasten Seite 82) aus mehreren Teiltouren. Da sie noch keine zulässige Lösung des ursprünglichen Problems ist, muß man durch Hinzunahme einer Nebenbedingung den entsprechenden Punkt von dem bisher gewonnenen Polytop abschneiden.

Es steht eine große Anzahl solcher Schnitte zur Auswahl; darunter sind "bestmögliche", das heißt solche, die mit den Facetten des echten Polytops möglichst viel gemeinsam haben. (Facetten sind die vieldimensionalen Verallgemeinerungen der Grenzflächen eines dreidimensionalen Polytops.) Ein Großteil der theoretischen Arbeit der letzten 20 Jahre hat sich auf die Identifizierung solcher Schnitte konzentriert.

In unserem Fall fügen wir als abschneidende Nebenbedingungen gerade diejenigen hinzu, welche die vier Teiltouren der bisher gefundenen Lö-sung ausschließen. Nun ist das um diese Ungleichungen erweiterte lineare Programm zu lösen; moderne Softwarepakete erledigen das schnell und effizient, weil sie die in der bisherigen Lösung enthaltene Information geschickt ausnutzen.

Es ergibt sich ein Lösungsvektor mit dem Zielfunktionswert 6228 Kilometer, der noch immer nicht eine passende Komplett-Rundreise für Odysseus ist (Kasten Seite 84, f). Die algorithmische Idee ist jetzt jedoch klar: Weiter so. Wir müssen nur noch iterieren. Wir aktivieren eine weitere kleine Teilmenge der astronomisch vielen Ungleichungen, die wir bislang ignoriert haben. Dadurch und durch die Lösung eines dritten linearen Programms erhalten wir eine Zielfunktion mit dem Optimalwert 6813,5 Kilometer und einen Lösungsvektor, der wiederum keine Rundreise für Odysseus ist (Kasten Seite 84, g). Er enthält nämlich für einige der 120 Variablen den Wert 1/2 – was für das erweiterte Problem ja zulässig ist. Eine weitere Iteration liefert den Zielfunktionswert von 6859 Kilometer und den Lösungsvektor, welcher der optimalen Rundreise entspricht (h). Damit sind wir am Ziel.

Das oben erläuterte iterative Verfahren heißt Schnittebenenalgorithmus (cutting plane algorithm). Sind die Ungleichungen, die das echte Polytop beschreiben, vollständig bekannt, muß der Schnittebenenalgorithmus nach einer endlichen Anzahl von Schritten beendet sein. Daß in unserem Fall vier Schritte bereits genügen, geht aus so allgemeinen Überlegungen allerdings nicht hervor.

Wir kennen gegenwärtig all diese Ungleichungen aber weder für das Travelling Salesman Problem noch für die meisten anderen kombinatorischen Optimierungsprobleme von praktischer Bedeutung. Ein Großteil der Forschung konzentriert sich darauf, dieses Wissen für immer mehr kombinatorische Probleme zu vergrößern. Dadurch sind die Grenzen mathematischer Berechenbarkeit weit über das hinaus getrieben worden, was sich Wissenschaftler noch vor wenigen Jahren vorstellen konnten.

Andererseits ist es möglich, daß die Schwierigkeit des TSP oder anderer kombinatorischer Optimierungsprobleme eine vollständige Kenntnis der erforderlichen Ungleichungen ausschließt. Wir wissen es einfach nicht; und gegenwärtig kennen wir mit Sicherheit nicht alle Ungleichungen. Anders als beim Problem des Odysseus kann also das iterative Schnittebenenverfahren beendet sein, bevor eine optimale Rundreise gefunden wurde.

Was sind unsere Wahlmöglichkeiten in einem solchen Fall? Wir könnten aufhören und uns mit der Kenntnis einer guten unteren Schranke begnügen. Wir könnten auch wie folgt ein Enumerationsverfahren anwenden: Wenn der Schnittebenenalgorithmus unschlüssig (also ohne eine zulässige Lösung für unser eigentliches Problem) endet, gibt es Kanten, die weder mit 0 noch mit 1 belegt sind. Wir greifen eine solche Kante heraus, setzen ihren Wert willkürlich auf 1 ("die Tour muß diesen Weg verwenden") und versuchen das derart eingeschränkte – und deshalb einfachere – Problem zu lösen. Dasselbe versuchen wir mit der Festlegung auf 0 statt 1 ("die Tour darf diesen Weg nicht verwenden"). Von den beiden Lösungen, die sich dabei ergeben, nehmen wir die bessere. Eins von beiden – den Weg nehmen oder nicht – muß die Tour ja tun.

Natürlich kann der Lösungsversuch für diese Teilprobleme abermals unschlüssig enden. Wieder verzweigt der Lösungsprozeß in zwei Alternativen (branching), und es entsteht ein ganzer Baum von Lösungsmöglichkeiten. Den müssen wir auf möglichst geschickte Weise absuchen.

Das entsprechende Baumsuchverfahren ist unter dem Namen Branch and Cut bekannt. Es baut auf das in den sechziger Jahren entwickelte Verfahren Branch and Bound auf, ist jedoch wesent- lich effizienter. Auf ihm basieren die gegenwärtig erfolgreichsten Algorithmen für große kombinatorische Optimierungsprobleme sowie die Algorithmen mit den besten Gütegarantien. Diverse heuristische und enumerative Techniken kommen hinzu. In ein erfolgreiches Verfahren gehen gründliche mathematische Analyse, Wissen auf vielen der Optimierung und Informatik zugehörigen Gebieten, Kenntnis über effiziente Datenstrukturen, Datenverarbeitung und Computerprogrammierung ein. Denn der Wert eines Verfahrens erweist sich erst in der Durchführung auf realen Rechen-anlagen.

Die hier erläuterten Beispiele für TSPs wurden mit einem Code berechnet, den Manfred Padberg und Giovanni Rinaldi vom italienischen Forschungszentrum IASI (Istituto di Analisi dei Sistemi ed Informatica) in Rom entwickelt haben. Es gibt weit mehr erfolgreiche Anwendungen von Branch and Cut durch uns und andere, als in diesem Artikel beschrieben werden können. Die Lösungszeiten für die verschiedenen Fragestellungen eines 16-Städte-Problems betragen nur wenige Millisekunden auf einer modernen Workstation. Man vergleiche diese Zeit mit den 92 Stunden für die stumpfsinnige Enumeration! Dazu der rasante Leistungs-zuwachs der Rechner-Hardware, solide angewandte Mathematik und intelligente Software-Entwicklung: Damit kann eine exakte Lösung von weitaus größeren Problemen, als wir uns jetzt vorstellen können, leicht zur Realität werden.

Zum Schluß noch einmal die Frage: Warum ist das Travelling Salesman Problem so schwer? Beim beschriebenen Lösungsverfahren ist die astronomisch hohe Zahl von Ungleichungen, die zu berücksichtigen sind, zweifellos die größte Hürde. Liegt darin die prinzipielle Schwierigkeit des Problems begründet? Dies ist sicherlich teilweise der Fall. Erstaunlicherweise ist dies aber keine vollständige Erklärung. Es gibt Probleme in der kombinatorischen Optimierung, die sowohl in der Theorie als auch in der Praxis leicht zu lösen sind, deren Polytope aber bei gleicher Dimension weit mehr Ungleichungen als das zum TSP gehörige Polytop benötigen.

Wenn es also weder die Anzahl möglicher Lösungen noch die Anzahl der erforderlichen Ungleichungen ist, was ist es dann, was ein Problem "schwierig" macht? Gegenwärtig kennt niemand eine Antwort auf diese Fragen; gleichwohl liefern die hier vorgestellten Algorithmen gute Ergebnisse.


Aus: Spektrum der Wissenschaft 4 / 1999, Seite 76
© Spektrum der Wissenschaft Verlagsgesellschaft mbH