Schnittebenenverfahren

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.

Sind einige Klassen gültiger Ungleichungen bekannt, wird meist folgender Algorithmus angewendet:

1. Löse die LP-Relaxierung; sei x^* die Optimallösung des LPs.
2. Wenn x^* ganzzahlig ist, ist es auch optimal. STOP.
3. Teste für alle bekannten Klassen von Ungleichungen, ob sie eine oder mehrere von x^* verletzte Schnittebenen enthält.
4. 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.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Schnittebenenverfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung