Branch-and-Bound

Anwendung auf Probleme der ganzzahligen linearen Optimierung

Lösungsweg

Das Problem kann man mit Hilfe des Branch-and-Bound-Verfahrens lösen. Zuerst wird alsbisher bester Zielfunktionswert gesetzt und die Ganzzahligkeitsbedingung weggelassen:

• Maximiere   G = a*x
• unter der Nebenbedingung
  Ax ≤ b
  x ≥ 0

Das so entstandene Problem nennen wir P₀. Dieses nun lineare Optimierungsproblem löst man mit dem Simplex-Verfahren. Im Allgemeinen wird die erhaltene Lösung nicht ganzzahlig sein, d. h. x₁, x₂ … x_n sind nicht durchgängig ganzzahlig. Ohne Beschränkung der Allgemeinheit betreffe dies auch x₁.

Nun versucht man, Lösungen mit ganzzahligem x₁ zu finden. Sei s₁ die größte ganze Zahl kleiner als x₁. Dann formuliert man zwei neue lineare Optimierungsprobleme P₁₁ und P₁₂ derart, dass die vorher gefundene Lösung jeweils ausgeschlossen wird:

• P₁₁ – Maximiere   G = a*x
• unter der Nebenbedingung

Ax ≤ b

x ≥ 0

x₁ ≤ s₁

• P₁₂ – Maximiere   G = a*x
• unter der Nebenbedingung

Ax ≤ b

x ≥ 0

x₁ ≥ s₁ + 1

Eine solche Aufteilung in Unterprobleme nennt man branch (engl. Verzweigung).

Beide Teilprobleme werden mit dem dualen Simplexverfahren gelöst. Folgende Fälle könnenauftreten:

1. Der zulässige Bereich wird leer.
2. Man findet eine ganzzahlige Optimallösung für das Teilproblem.
3. x₁ wird ganzzahlig, dafür aber ein anderes x_i nicht, wobei es keine Rolle spielt, ob jenes x_i vorher ganzzahlig war oder nicht.

Im Fall (1) erledigt sich das Teilproblem. In den anderen Fällen gilt das auch, wenn ist und nur eine Optimallösung gesucht wird oder ist und alle Optimallösungen gesucht werden.Ansonsten speichert man im Fall (2) die gefundene Lösung als bisher beste und ersetzt durch G, während im Fall (3) das Teilproblem weiter aufzuspalten ist.

Auf diese Weise wird der gesamte Lösungsraum durchsucht und eine Optimallösung gefunden, wenn es eine gibt und das Verfahren nicht vorzeitig abgebrochen wurde. Es ist durchaus möglich, dass man trotz erschöpfender Suche keine Lösung findet. Dann besitzt das Ausgangsproblem keine zulässigen Lösungen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Branch-and-Bound 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