Ganzzahlige lineare Optimierung

Komplexität und Lösungsverfahren

Schnittebenenverfahren

Hauptartikel: Schnittebenenverfahren

Schnittebenenverfahren (engl. cutting plane algorithm) berechnen zunächst eine Lösung der LP-Relaxierung. Diese ist meist nicht ganzzahlig, liefert aber eine duale Schranke für den Optimalwert des IPs. 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.

Geometrisch entspricht dieses Vorgehen dem Hinzufügen einer Hyperebene, welche die optimale Ecke des LP-Polyeders P von dem (unbekannten) Polyeder abschneidet, das von den ganzzahligen Lösungen aufgespannt wird. Beim erneuten Lösen wird eine optimale Ecke des beschnittenen Polyeders bestimmt. Ist diese ganzzahlig, so hat man eine zulässige und optimale Lösung des ganzzahligen linearen Programms gefunden. Andernfalls wird wieder nach einer neuen Schnittebene gesucht.

Im nebenstehenden Bild ist die Schnittebene (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, wodurch sich beispielsweise der relative Optimalitätsgap für die Lösung (1;1) von 180% auf verringert.

In der praktischen Anwendung sind Schnittebenenverfahren ein wichtiges Hilfsmittel, reichen aber allein meist nicht aus und können bei unvorsichtiger Anwendung zu numerischen Problemen führen. Statt dessen werden sie häufig mit Branch-and-Bound kombiniert. Wie gut das funktioniert, hängt stark von der Struktur des zu lösenden Problems ab. Die besten Schnittebenen, die man finden kann, sind Facetten des IP-Polyeders. Im obigen Beispiel sind das die Ungleichungen und , die den rot gestrichelten Linien entsprechen. Um solche Ungleichungen zu identifizieren, ist meist eine genauere mathematische Untersuchung der zugrundeliegenden Polyeder notwendig.

 

 

 

 

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Ganzzahlige lineare Optimierung 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