Inhalt
Schnittebenenverfahren| Grundidee des Algorithmus am Beispiel | |
Schnittebenenverfahren
Grundidee des Algorithmus am Beispiel
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 
(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
, 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 und
, die den rot gestrichelten Linien entsprechen.
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