Schnittebenenverfahren
Ein
Schnittebenenverfahren (engl.
cutting plane algorithm) ist in der angewandten
Mathematik ein
Algorithmus zur Lösung
ganzzahliger linearer Optimierungsprobleme. Die Grundidee besteht darin, statt eines
ganzzahligen linearen Programms seine LP-Relaxierung (also ohne Ganzzahligkeitsbedingungen) zu betrachten und diese durch Hinzufügung weiterer
Ungleichungen schrittweise zu verschärfen, bis (im Idealfall) eine
ganzzahlige Lösung gefunden wird.
Das in den 1950er Jahren u. a. von Delbert Ray Fulkerson, George Dantzig und Ralph Gomory entwickelte Verfahren ist mit seinen Weiterentwicklungen heute eine der Standardmethoden in der
ganzzahligen Optimierung und weiterhin Gegenstand aktueller Forschung. Als alleiniges Lösungsverfahren ist es meist nicht ausreichend, liefert aber gute duale Schranken für die zu lösenden Optimierungsprobleme. Daher wird es oft mit
Branch-and-Bound zum sogenannten
Branch-and-Cut-Verfahren kombiniert.
Problemdefinition
- max{cTx∣Ax≤b,x≥0,x∈Zn}
Dabei ist
A eine reelle
Matrix und
b und
c sind Vektoren passender
Dimension. Die Bedingung
Ax≤b ist komponentenweise zu verstehen, also als
- ai⋅x=j=1∑naijxj≤bi
für alle Zeilen
i der
Matrix A. Genauso bedeutet die Bedingung
x≥0, dass alle Einträge des Vektors
x nichtnegativ sein müssen.
Dies kann wie folgt geometrisch interpretiert werden: die
Menge
- P:={x∣Ax≤b,x≥0},
die durch Weglassen der Ganzzahligkeitsbedingungen entsteht, bildet ein konvexes Polyeder im
n-dimensionalen Raum, dessen beschränkende Hyperebenen den Zeilen des Ungleichungssystems entsprechen.
P enthält u. a. alle zulässigen
Punkte des Ausgangssystems, also alle
ganzzahligen Punkte, die die Bedingungen
Ax≤b erfüllen, aber im Unterschied zur
linearen Optimierung sind nicht alle
Punkte in
P zulässig. Das
lineare Programm
- max{cTx∣x∈P}
wird als
LP-Relaxierung des
ganzzahligen Problems bezeichnet.
- max−x3x2xx,y∈Z+y+y+2y+3y≤1≤12≤12
dargestellt. Die zulässigen
ganzzahligen Punkte sind rot eingezeichnet, und die rot gestrichelten Linien kennzeichnen ihre
konvexe Hülle, also das kleinste Polyeder, das alle diese
Punkte enthält. Über diesem Polyeder soll eigentlich optimiert werden, aber es ist meist nicht genau bekannt. Die blauen Linien zusammen mit den Koordinatenachsen begrenzen das Polyeder
P der LP-Relaxierung, das durch das Ungleichungssystem ohne Ganzzahligkeitsbedingungen gegeben ist. Ziel der
Optimierung ist es, die schwarz gestrichelte Linie so weit
parallel nach oben (in Richtung des Vektors
c=(0;1)) zu verschieben, dass sie das jeweilige Polyeder gerade noch berührt. Die Optimallösungen des
ganzzahligen Problems sind also die
Punkte (1;2) und
(2;2) mit dem Zielfunktionswert
cTx=(0;1)T(1;2)=2. Die - in diesem Fall eindeutige - optimale Lösung der LP-Relaxierung mit dem Zielfunktionswert 2,8 ist der blau markierte
Punkt LPopt=(1,8;2,8), der nicht
ganzzahlig und damit auch nicht zulässig für das IP ist.
Grundidee des Algorithmus am Beispiel
Hinzufügen einer Schnittebene (grün)
Schnittebenenverfahren berechnen zunächst eine Lösung der LP-Relaxierung. Diese ist meist nicht
ganzzahlig (wie der
Punkt LPopt=(1,8;2,8)), liefert aber eine obere (allgemein:
duale) Schranke für den Optimalwert des IPs, da jede Lösung des
ganzzahligen Programms auch eine Lösung der LP-Relaxierung ist und deshalb der Optimalwert des
ganzzahligen Programms (im Beispiel 2) höchstens so hoch sein kann wie der Optimalwert der LP-Relaxierung (im Beispiel 2,8). Dies kann zur Abschätzung der Qualität einer Lösung des IPs genutzt werden.
Diese duale Schranke wird anschließend durch schrittweises Hinzufügen sogenannter
Schnittebenen verschärft. Eine Schnittebene ist eine zusätzliche
Ungleichung, die von allen zulässigen
Punkten des IPs erfüllt wird, aber nicht von der aktuellen LP-Lösung. Wird die
Ungleichung dem LP hinzugefügt, muss daher beim erneuten Lösen eine andere Lösung herauskommen. Dies wird solange fortgeführt, bis eine
ganzzahlige Lösung gefunden wird (die dann automatisch auch optimal für das
ganzzahlige Programm ist) oder keine geeigneten
Ungleichungen mehr gefunden werden.
Im nebenstehenden Bild ist die Schnittebene
x+2y≤6 (grün) dargestellt, die das bisherige LP-Optimum (blau) vom IP-Polyeder trennt (
separiert). Alle zulässigen
Punkte liegen auf einer Seite der Hyperebene, die LP-Lösung auf der anderen Seite. Erneutes Lösen des LPs mit dieser zusätzlichen
Ungleichung liefert den grün markierten
Punkt (4/3;7/3). Dieser
Punkt ist immer noch nicht zulässig, hat aber den kleineren Zielfunktionswert
7/3≈2,333, was die
obere Schranke auf diesen Wert verbessert.
Die besten Schnittebenen, die man finden kann, sind
Facetten des IP-Polyeders, also
(n−1)-dimensionale Seitenflächen bei
n Variablen. Im obigen Beispiel sind das die
Ungleichungen y≤2 und
x+y≤4, die den rot gestrichelten Linien entsprechen.
Einsatz in der Praxis
Für eine ganze Reihe von Planungsproblemen, vor allem solchen mit praktischen Anwendungshintergrund (z. B. Routingprobleme oder Zuordnungsprobleme), sind mehrere
Klassen von
Ungleichungen bekannt, die von allen
ganzzahligen Punkten des Polyeders erfüllt werden (also für dieses Polyeder
gültig sind). Dies können problemunabhängige IP-Schnittebenen wie
Gomory-Cuts sein, die auch ohne Kenntnis des praktischen Hintergrunds von Standardlösern gefunden werden können, oder problemspezifische Schnittebenen, die die spezielle Struktur der
Matrix A ausnutzen. Beispiele für letztere sind die
Kurzzyklusungleichungen beim
Problem des Handlungsreisenden. Da es im Verhältnis zur Anzahl der
Knoten des Graphen exponentiell viele Kurzzyklusungleichungen gibt, kann man sie zunächst weglassen und statt dessen nach und nach separieren.
Solche
Klassen gültiger
Ungleichungen für bestimmte Arten oder Teilstrukturen von
ganzzahligen Programmen zu finden und Aussagen über die Qualität dieser Schnittebenen zu treffen, ist ein nicht triviales Problem. Insbesondere die Information, unter welchen Bedingungen eine Schnittebene eine Facette des zugrundeliegenden Polyeders definiert, erfordert in der Regel eine genauere mathematische Untersuchung. Dies ist ein wichtiger Gegenstand aktueller Forschung in der
ganzzahligen linearen Optimierung.
- Löse die LP-Relaxierung; sei x∗ die Optimallösung des LPs.
- Wenn x∗ ganzzahlig ist, ist es auch optimal. STOP.
- Teste für alle bekannten Klassen von Ungleichungen, ob sie eine oder mehrere von x∗ verletzte Schnittebenen enthält.
- Falls ja, füge sie zum LP hinzu und gehe zu 1. Sonst STOP.
Wird am Ende keine verletzte Schnittebene mehr gefunden, ohne dass die LP-Lösung
ganzzahlig ist, kann man versuchen, heuristisch eine
ganzzahlige Lösung zu bestimmen oder
Branch-and-Bound zu starten (diese
Kombination heißt dann
Branch-and-Cut). Dies funktioniert in der Praxis je nach Problem und verwendetem Modell mal mehr und mal weniger gut.
Wie man in Schritt (3) die
Ungleichungen auf Verletzung testet, hängt von den
Ungleichungen ab. In einigen Fällen kann man die Schnittebenen
exakt separieren, d. h. wenn man keine verletzte
Ungleichung dieser
Klasse findet, gibt es auch keine. Dies ist zum Beispiel dann der Fall, wenn eine
Klasse so wenige
Ungleichungen enthält, dass man sie einfach alle durchtesten kann. Aber auch die exponentiell vielen Kurzzyklusungleichungen im Falle des TSP können durch Berechnung eines minimalen Schnittes im zugrundeliegenden Graphen in Polynomialzeit auf Verletzung getestet werden. In anderen Fällen, wo die Separierung in annehmbarer Zeit nur heuristisch möglich ist (beispielsweise bei allgemeinen
Mixed-Integer Rounding Cuts), ist am Ende nicht klar, ob es keine verletzten Unleichungen mehr gibt oder ob man sie nur nicht gefunden hat.
Geschichte
Die ersten Schnittebenen wurden Mitte der 1950er Jahre von D.R. Fulkerson, G. Dantzig und S. Johnson für das
Problem des Handlungsreisenden entwickelt. Ohne Kenntnis dieser Arbeiten und motiviert durch ehemalige Kollegen der US Navy, die an
ganzzahligen Lösungen interessiert waren, entwickelte R. Gomory im Jahre 1958 während seines Aufenthaltes in Princeton das erste allgemein einsetzbare
Schnittebenenverfahren. Er zeigte, dass theoretisch allein mit diesem Verfahren beliebige
ganzzahlige Programme gelöst werden können. In der Praxis hat dieser Ansatz allerdings zwei Probleme: einerseits führen viele Schnittebenen irgendwann zu sehr großen linearen Programmen und entsprechend langen Lösungszeiten in jeder Iteration, und andererseits enthalten die von Gomory vorgeschlagenen Schnittungleichungen (
Gomory fractional cuts) oft sehr viele Nicht-Null-Koeffizienten, was zu numerischen Instabilitäten bei der Lösung der
linearen Programme führt. Trotzdem stellte dieses Verfahren einen entscheidenden algorithmischen Fortschritt dar.
In den 1980er Jahren arbeiteten M. Padberg und andere an Schnittebenen für oft auftauchende Teilstrukturen wie Rucksackprobleme, die oft auch in allgemeinerem Kontext eingesetzt werden können. In den letzten zehn Jahren wurden viele Schnittebenen für spezielle Anwendungsprobleme entdeckt, etwa für Routingprobleme, die im Zusammenhang mit der Planung öffentlicher Nahverkehrsnetze oder beim Design von Telekommunikationsnetzen auftreten.
Literatur
- George Nemhauser und Laurence Wolsey: Integer and Combinatorial Optimization. Wiley Interscience, 1988, ISBN 0-471-35943-2.
- Ralph Gomory: Early Integer Programming. In: Operations Research, Volume 50, Nummer 1, S. 78-81, 2002.
Alle Pädagogen sind sich darin einig: man muß vor allem tüchtig Mathematik treiben, weil ihre Kenntnis fürs Leben größten direkten Nutzen gewährt.
Felix Klein
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld
• Dοrfplatz 25 • 17237 Blankеnsее
• Tel.: 01734332309 (Vodafone/D2) •
Email: cο@maτhepedιa.dе