Branch-and-Bound: Knapsack-Problem

Bei einem Knapsack-Problem (auch: Rucksack-Problem) soll ein knappes Gut optimal verteilt werden. Knappsack-Probleme haben häufig nur eine einzige -Nebenbedingung gegeben, in welcher sich alle Entscheidungsvariablen befinden. Die Anzahl der Entscheidungsvariablen ist häufig sehr hoch. 

Ein Knapsack-Problem lässt sich auf ein binäres Problem zurückführen. In diesem Abschnitt soll gezeigt werden, wie man ein solches Problem mittels Branch-and-Bound-Verfahren lösen kann. 

Es sei das folgende ganzzahlige Maximierungsproblem gegeben:

 max!

u.d.N.

Das Ausgangsproblem wird in Teilprobleme zerlegt. Dafür wird für jedes Teilproblem eine obere und eine untere Schranke bestimmt. 

Bestimmung der oberen Schranke

Die obere Schranke wird bestimmt, indem die Quotienten aus Koeffizient der Zielfunktion durch Koeffizient der Nebenbedingung in absteigender Reihenfolge sortiert werden:

Danach wird für jede Variable nach dieser Reihenfolge der Wert gewählt, solange die Restriktion nicht überschritten wird. Die erste Variable, die nicht mehr voll aufgenommen werden kann, wird anteilig mit eingeplant. 

Die Variablenwerte werden dann in die Zielfunktion eingesetzt und damit die obere Schranke des Teilproblems bestimmt.

Für das hier angegebene Beispiel werden zunächst die Quotienten gebildet und in absteigender Reihenfolge sortiert:

1.  für

2.   für

2.   für

2.   für

Danach wird die obere Schranke festgelegt. Zunächst wird mit in der Restriktion berücksichtigt:

Danach hinzugefügt:

Danach :

Die Variable muss demnach anteilig berücksichtigt werden.

Wenn eingeplant werden, dann ist:

Es ist aber eine Kapazität vorhanden von . Demnach gibt es eine Differenz von . Die Variable besitzt aber :

.

Die letzte Variable geht mit dem Wert ein, da keine Kapazität mehr vorhanden ist.

Es ergibt sich also der Punkt:

Die obere Schranke ist demnach:

Da es sich um eine nichtganzzahlige Lösung handelt, ist die Lösung nicht zulässig. Damit muss das Problem verzweigt werden.

Bestimmung der unteren Schranke

Die untere Schranke wird bestimmt, indem die nicht ganzzahlige Variable mit dem Wert in der Zielfunktion berücksichtigt wird. 

Für dieses Beispiel ist die untere Schranke demnach:

Ein Teilproblem braucht nicht weiter betrachtet werden, wenn gilt:

Es wird immer diejenige Variable verzweigt, welche nichtganzzahlige Werte aufweist. In diesem Beispiel wird also mit der Variable begonnen und diese verzweigt in und .

Für das Teilproblem wird gesetzt und wieder die obere Schranke bestimmt. Hierbei muss wieder die obige Reihenfolge eingehalten werden.

Zunächst wird mit in der Restriktion berücksichtigt:

Danach hinzugefügt:

Danach :

Danach :

Die Variable muss demnach anteilig berücksichtigt werden:

Die obere Schranke für das Teilproblem ist demnach:

Da es sich um eine nichtganzzahlige Lösung handelt, ist die Lösung nicht zulässig. Damit muss das Problem verzweigt werden.

Für das Teilproblem wird gesetzt und wieder die obere Schranke bestimmt. Hierbei muss wieder die obige Reihenfolge eingehalten werden.

Zunächst wird mit in der Restriktion berücksichtigt:

Danach hinzugefügt:

Danach :

Die Kapazität ist nicht ausreichend. Die Variable über (in der Reihenfolge hier) muss demnach zunächst unberücksichtigt bleiben. Es gilt :

Da die Kapazität voll ausgeschöpft ist, wird gesetzt.

Die obere Schranke ergibt also:

Es handelt sich hierbei um eine zulässige Lösung, weil die Lösung ganzzahlig ist. Da diese ermittelte zulässige Lösung größer ist als die untere Schranke liegt eine neue untere Schranke vor (Fall b):

.

Das Problem muss nicht weiter verzweigt werden.