Ganzzahlige lineare Optimierung

Komplexität und Lösungsverfahren

Branch-and-Bound bzw. Branch-and-Cut

Hauptartikel: Branch-and-Bound

Hauptartikel: Branch-and-Cut

Auch Branch-and-Bound beginnt mit dem Lösen der LP-Relaxierung. Ist die erhaltene Lösung nicht ganzzahlig, wird das Problem so in zwei oder mehr Teilprobleme zerlegt, dass jede zulässige Lösung in einem dieser Teilprobleme enthalten ist. Auf diese Art wird ein Verzweigungsbaum mit der LP-Relaxierung als Wurzelknoten aufgebaut. An jeder Verzweigung (engl. Branch) wird der Wertebereich einer oder mehrerer Variablen eingeschränkt. Dies wird solange durchgeführt, bis eine beste ganzzahlige Lösung gefunden wurde.

In dieser reinen Form entspricht das Verfahren einer vollständigen Enumeration aller möglichen Lösungen. Mit Hilfe der dualen Schranken, die man durch die Lösung der Relaxierungen an jedem Knoten des Verzweigungsbaums erhält, können aber Teilbäume abgeschnitten werden (engl. Bound), wenn sich erweist, dass sie keine Optimallösung enthalten können. Als alleiniger Algorithmus reicht Branch-and-Bound meist nicht aus, weil zu wenig vom Suchbaum abgeschnitten werden kann. Gute IP-Löser kombinieren dieses Verfahren daher zur Verbesserung der dualen Schranke mit Schnittebenenverfahren. Dieser Ansatz heißt dann Branch-and-Cut.

Im nebenstehenden Beispiel werden, ausgehend von der gebrochenen LP-Lösung (1, 8;2, 8), die beiden Teilprobleme betrachtet, die durch Hinzufügen der zusätzlichen Bedingung bzw. entstehen. Jede zulässige Lösung ist in genau einem der beiden Teilpolyeder (grün umrandet) enthalten. Das Lösen der LP-Relaxierung mit den zusätzlichen Bedingungen liefert im rechten Teilproblem die gebrochene Lösung (2;8/3) mit dem Zielfunktionswert 8/3 und im linken Teilproblem die ganzzahlige Lösung (1;2) mit dem Wert 2. Dadurch verbessert sich die untere Schranke für den optimalen IP-Wert auf 2 (der Wert der besten bekannten zulässigen Lösung), während sich die obere Schranke auf 8/3 verringert (der höhere LP-Wert der beiden Teilprobleme). Der Optimalitätsgap reduziert sich damit auf (8/3 - 2)/2 = 1/3, d. h. der Optimalwert ist höchstens (1 + 1/3) mal so hoch wie der Wert der Lösung (1;2). Tatsächlich ist diese Lösung bereits optimal, da sie eine ganzzahlige Lösung einer Relaxierung des ursprünglichen Problems ist.

 

 

 

 

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