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*
ck*,i               - { ck,i - [ck,i]| }
rk*                 - { rk - [rk]| }

mit [ck,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 P0 bezeichnet.
Der Index i wird auf 0 gesetzt.

[1] Löse das Problem Pi 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 Pi.
(Füge das Problem der Liste der noch nicht abgearbeiteten Probleme hinzu.)
Suche das nächste (noch nicht abgearbeitete) Problem Pk, das die "beste" Lösung verspricht, d.h. das Problem mit der "besten" Schranke. Setze i = k.
Wurde für das Problem Pi 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 Pi.
Zerlege das Problem Pi in zwei Teilprobleme Pi1 und Pi2
(jeweils mit obiger Schranke S).
Sei dabei k der erste Index mit einer nichtganzzahligen Lösung xk* .
Setze uk = int(xk) und ok = uk + 1.
Das Problem Pi1 entspricht dem Problem Pi mit der zusätzlichen Nebenbedingung xk < uk .
Das Problem Pi2 entspricht dem Problem Pi mit der zusätzlichen Nebenbedingung xk > ok.
(Füge die beiden Probleme der Liste der noch nicht abgearbeiteten Probleme hinzu.)
Suche das nächste Problem Pk, das die "beste" Lösung verspricht, d.h. das Problem mit der "besten" Schranke. Setze i = k.
Ist Pi bereits gelöst, so gehe zu [3a] sonst gehe zu [1].

Das Verfahren wird an folgendem Beispiel verdeutlicht.


Tips und Anregungen an: emiel@informatik.fh-augsburg.de
Stand: 21.03.2003