Branch-and-Bound: Knapsack-Problem (Alternative)

In diesem Abschnitt soll eine alternative Vorgehensweise für das Branch-and-Bound Verfahren anhand eines Knapsack-Problems dargestellt werden. 

Gegeben sei das folgende Knapsack-Problem:

\rightarrow x_41x_4 = 0x_4 = 1x_4$ konstant gehalten und die anderen Variablen variiert. Dabei wird die Prioritätenreihenfolge beachtet.

Für die oberste Ebene wird der Zielfunktionswert so gebildet, dass alle anderen Variablen den Wert annehmen und mit dem verzweigten Wert eingeht. Dies zeigt den für die nachfolgenden Verzweigungen höchtsmöglich erzielbaren Zielfunktionswert an. Es muss nun mittels der Verzweigungen geprüft werden, ob dieser unter Berücksichtigung der Restriktion auch erreicht werden kann. Die Restriktion für die oberste Ebene wird so bestimmt, dass alle Variablen mit dem Wert eingehen und mit dem verzweigten Wert. Dies zeigt die momentan tatsächlich in Anspruch genommene Restriktion an. 

Der Entscheidungsbaum wird rechtsorientiert erstellt. Das bedeutet, dass zunächst die rechten Verzweigungen solange abgearbeitet werden, bis diese ausgeschlossen werden können. Danach wird weiter von unten nach oben gearbeitet. Es ergibt sich der folgende Entscheidungsbaum nach dem Branch-and-Bound Verfahren:

Das Ergebnis ist äquivalent zum Ergebnis aus dem vorherigen Abschnitt, allerdings sind hier mehr Verzweigungen zu untersuchen und damit der Rechenaufwand erheblich höher als mit dem Branch-and-Bound-Verfahren aus dem vorherigen Abschnitt.