Forschungsbericht 2003 - Max-Planck-Institut für Informatik

Kombinatorische Optimierung

Combinatorical optimization

Autoren
Friedrich Eisenbrand; Markus Behle
Abteilungen

Kombinatorische Optimierung (Dr. habil. Martin Skutella)
MPI für Informatik, Saarbrücken

Zusammenfassung
Kombinatorische Optimierung beschäftigt sich mit der Auswahl optimaler Entscheidungen aus einer großen Menge von möglichen Alternativen. Dieses Gebiet hat viele wichtige Anwendungen in Bereichen wie Planung, Schichtplanerstellung, Portfoliomanagement und vieles mehr. In diesem Artikel führen wir anhand des Handlungsreisendenproblems in das Gebiet ein und beschreiben einen wichtigen Ansatz zum Lösen von ganzzahligen Programmen, die so genannte ganzzahlige Optimierung. Zusätzlich beschreiben wir zwei unserer Beiträge in diesem Gebiet, einen effizienten Algorithmus für ganzzahlige Programmierung in fester Dimension und einen Beitrag zur Komplexität von Schnittebenen.
Summary
Combinatorial Optimization deals with the identification of optimal choices in a large set of alternatives. This topic is of great importance in many fields of applications, such as planning, crew scheduling portfolio management and many more. In this report we give an introduction to combinatorial optimization with the help of a famous example, the traveling salesman problem. Then we describe the integer programming approach to combinatorial optimization and describe two of our results in this area. One concerns the generation of cutting planes and one concerns the complexity of integer programming in fixed dimension.

Kombinatorische Optimierung

In diesem faszinierenden Forschungsgebiet aus dem Grenzbereich zwischen Informatik und Mathematik geht es kurz gesagt darum, optimale Entscheidungen unter sehr vielen Alternativen zu treffen. Beleben wir diese kurze Beschreibung anhand eines populären Beispiels, dem so genannten Problem des Handlungsreisenden. Ein Handlungsreisender muss 50 Kunden besuchen und plant nun die Reihenfolge, in der er dies tun will. Ihm sind die Distanzen zwischen all seinen Kunden bekannt, das heißt, für jeden Kunden A und jeden Kunden B kennt der Handlungsreisende die Distanz, die er mit seinem Fahrzeug zurücklegen muss, um von A nach B zu gelangen. Der Handlungsreisende möchte eine Reihenfolge seiner Kundenbesuche bestimmen, die die Länge seiner Tour minimiert. Abbildung 1 zeigt ein Beispiel für 12 Kunden.

Eine Instanz des Handlungsreisendenproblems lässt sich als Graph darstellen. Die Zahlen an den Kanten des Graphen geben die Entfernung zwischen zwei Punkten an.

Was sind in diesem Szenario die "Alternativen", was sind die "optimalen Entscheidungen"? Die Alternativen sind alle möglichen Reihenfolgen der Kunden und die optimalen Entscheidungen sind die Reihenfolgen, die die kürzeste Gesamtdistanz mitsichbringen. Wie viele Alternativen gibt es hier?
Man kann sich leicht überlegen, dass für 50 Kunden die Anzahl aller Reihenfolgen 50! ist. Diese Zahl 50! als Dezimalzahl ausgeschrieben ergibt eine 65-stellige Zahl. Wenn ein heutiger Hochleistungsrechner jetzt damit beginnt, allein bis 50! zu zählen, wird er diese Aufgabe zum Zeitpunkt des Erlischens der Sonne noch nicht abgeschlossen haben. Unser Handlungsreisender wäre also schlecht beraten, wenn er alle möglichen Reihenfolgen miteinander vergleichen würde, um seine optimale Tour zu bestimmen. Stattdessen wendet er sich besser
an Experten aus dem Bereich der kombinatorischen Optimierung. In diesem Forschungsgebiet benutzt man mathematische Methoden, um sehr große Bereiche der "Alternativen" von vorne herein als suboptimal zu erkennen. Somit wird vermieden, alle Alternativen explizit zu erwägen.

Kombinatorische Optimierungsprobleme, wie das oben beschrieben Problem des Handlungsreisenden, lassen sich sehr oft als so genannte ganzzahlige lineare Optimierungsprobleme beschreiben. Gültige Lösungen entsprechen dann genau den ganzzahligen Punkten eines Vektorraumes, die gewisse lineare Nebenbedingungen erfüllen. Die Zielfunktion ist dann eine lineare Funktion und optimale Lösungen sind gültige ganzzahlige Lösungen, deren Zielfunktionswert maximal ist (Abb. 2).

Ein ganzzahliges lineares Optimierungsproblemmit zwei Variablen. Der rote Vektor ist die Zielfunktionsrichtung, der rote ganzzahlige Punkt ist eine optimale Lösung. Der grüne Punkt ist eine optimale Lösung der Relaxation.

Die Ganzzahligkeitsbedingung an die Variablen, d.h., die Forderung, dass die Variablen nur ganzzahlige Werte annehmen können, macht die ganzzahlige lineare Optimierung zu einem schwierigen Problem. Lässt man diese Bedingung fallen, dann erhält man ein einfaches lineares Optimierungsproblem. Hier sucht man einen rationalen, also nicht unbedingt ganzzahligen Punkt, der alle Nebenbedingungen erfüllt und maximalen Zielfunktionswert hat. In Abbildung 2 ist dies der grüne Eckpunkt. Da man die ganzzahligkeitsbedingung des Problems fallen lässt, also manche Bedingungen relaxiert, spricht man von der linearen Relaxierung eines ganzzahligen linearen Optimierungsproblems. Da jeder ganzzahlige Punkt, der alle Nebenbedingungen erfüllt, auch ein rationaler Punkt ist, der alle Nebenbedingungen erfüllt, gilt folgende wichtige Eigenschaft:
Das Optimum der Relaxierung ist eine obere Schranke des Optimums des ganzzahligen linearen Optimierungsproblems.
Diese Eigenschaft ist sehr hilfreich bei der Identifizierung großer Bereiche unter den suboptimalen "Alternativen". In unserer Arbeitsgruppe arbeiten wir an der automatischen Verbesserung der Relaxation mithilfe so genannter Schnittebenen. Schnittebenen sind neue Nebenbedingungen, die keinen ganzzahligen gültigen Punkt verletzen, aber rationale Punkte der Relaxation abschneiden. Schauen wir uns dieses Prinzip in Abbildung 3 an. Die neue Nebenbedingungwird durch ein Liniensegment repräsentiert. Die Nebenbedingung lautet:
"Alle gültigen Punkte liegen links von der durch das Liniensegment definierten Geraden". Das bisherige Optimum der Relaxation (grüner Punkt) liegt rechts davon, wird also "abgeschnitten".
Das Optimum der neuen Relaxierung ist der blaue Punkt. Sein Zielfunktionswert ist näher
am ganzzahligen Optimum.

Eine Schnittebene wird in das Problem aus Abbildung 2 eingefügt. Das Optimum der neuen Relaxation, hier blau eingefärbt, liefert eine bessere obere Schranke.

In unserer Nachwuchsgruppe (NWG2, Diskrete Optimierung) am Max-Planck-Institut für Informatik in Saarbrücken, beschäftigen wir uns mit dem automatischen Erzeugen von Schnittebenen, die möglichst "stark" sein sollen, d.h., bei der Suche nach dem ganzzahligen Optimum helfen, sehr große Bereiche der Alternativen schnell zu verwerfen. Besonderen Schwerpunkt legen wir zur Zeit auf eine Kombination von Methoden aus der algorithmischen Logik und geometrischen Algorithmen. Im Rahmen des Sonderforschungsbereich/Transregio 14 AVACS entwickeln wir einen Löser für schwierige ganzzahlige Probleme in Kooperation mit dem Lehrstuhl für Rechnerarchitektur der Albert-Ludwigs-Universität Freiburg.

Zur Redakteursansicht