Kurzbeschreibung der Verfahren Gomory und Branch and Bound

Ein Verfahren von Gomory

Besitzt eine ganzzahlige Basisvariable k noch einen nichtganzzahligen Wert (nach Durchführung des Simplex-Verfahrens), so führe für diese Variable eine neue Zeile ins Simplex-Tableau ein und führe weitere Austauschschritte durch (in der Regel mit dualen Schritten beginnend); die neue Zeile erhält folgende Werte:

BV:                 k*
c_k*,i               - { c_k,i - [c_k,i]| }
r_k*                 - { r_k - [r_k]| }

mit [c_k,i]| = nächst kleinere ganze Zahl

Besitzen mehrere ganzzahlige BV noch nichtganzzahlige Werte, so beginne mit den erwähnten Schritten jeweils in der höchsten Zeile.

Das Verfahren wird an folgendem Beispiel verdeutlicht.

Ein Branch- and Bound-Verfahren

Allgemeine Form des Verfahrens

Das lineare Optimierungsproblem wird mit P₀ bezeichnet.
Der Index i wird auf 0 gesetzt.

[1] Löse das Problem P_i mit dem Simplex-Algorithmus.

[2] Ist die Lösung ganzzahlig und i = 0, so beende das Verfahren.
Gib die berechnete (letzte) Lösung aus.

[3a] Ist die Lösung ganzzahlig und besser als alle Schranken bzw. gleich der besten Schranke, so beende das Verfahren.
Gib die berechnete (letzte ganzzahlige) Lösung aus.

[3b] Ist die Lösung ganzzahlig und schlechter als die "beste" Schranke, so berechne als Schranke des Problems den Zielfunktionswert der Lösung des Problems P_i.
(Füge das Problem der Liste der noch nicht abgearbeiteten Probleme hinzu.)
Suche das nächste (noch nicht abgearbeitete) Problem P_k, das die "beste" Lösung verspricht, d.h. das Problem mit der "besten" Schranke. Setze i = k.
Wurde für das Problem P_i bereits eine ganzzahlige Lösung ermittelt, so gib diese Lösung aus und beende das Verfahren.
Im anderen Fall gehe zu [1].

[3c] Ist die Lösung nicht ganzzahlig, so berechne als Schranke S den Zielfunktionswert der Lösung des Problems P_i.
Zerlege das Problem P_i in zwei Teilprobleme P_i1 und P_i2
(jeweils mit obiger Schranke S).
Sei dabei k der erste Index mit einer nichtganzzahligen Lösung x_k* .
Setze u_k = int(x_k) und o_k = u_k + 1.
Das Problem P_i1 entspricht dem Problem P_i mit der zusätzlichen Nebenbedingung x_k < u_k .
Das Problem P_i2 entspricht dem Problem P_i mit der zusätzlichen Nebenbedingung x_k > o_k.
(Füge die beiden Probleme der Liste der noch nicht abgearbeiteten Probleme hinzu.)
Suche das nächste Problem P_k, das die "beste" Lösung verspricht, d.h. das Problem mit der "besten" Schranke. Setze i = k.
Ist P_i bereits gelöst, so gehe zu [3a] sonst gehe zu [1].

Das Verfahren wird an folgendem Beispiel verdeutlicht.