Branch and Bound II
Im ersten Teil des Beitrags haben wir dir bereits gezeigt, wie man ein kombinatorisches ganzzahliges Problem lösen kann. In diesem Beitrag betrachten wir ein binäres kombinatorisches ganzzahliges Problem.
Inhaltsübersicht
Branch and Bound – Beispielrechnung
Stell dir vor, du willst deinen Koffer für den Urlaub packen und hast eine Auswahl an Sachen, die du gerne mitnehmen möchtest. Jeder Gegenstand hat ein bestimmtes Gewicht und einen bestimmten Nutzen für dich. Dein Koffer darf für den Flug aber nicht schwerer als 15 Kilogramm sein. Jetzt willst du den Koffer optimal packen und dabei das maximal zulässige Gewicht einhalten. Da du ja nur ganze Gegenstände und nicht nur einen Bruchteil mitnehmen kannst, musst du entscheiden, ob du den Gegenstand einpackst oder zu Hause lässt.
Erklärung der Voraussetzungen
Das Problem sieht also folgendermaßen aus: Du siehst in der Zielfunktion deine Gegenstände 
gleich 1 bis 3, die du einpacken kannst, multipliziert mit ihrem jeweiligen Nutzen für dich. Du hast zwei Nebenbedingungen. Die erste zeigt die Gewichte der jeweiligen Gegenstände in Kilogramm und soll zusammenaddiert weniger oder gleich 15 Kilogramm wiegen. Die zweite Nebenbedingung sagt, dass jeder Gegenstand nur Element der Zahlen 0 oder 1 sein kann, also eine binäre Variable ist. Null steht dafür, dass der Gegenstand nicht eingepackt wird und 1, dass er eingepackt wird. Um gleich im Branch and Bound Verfahren bestimmen zu können, nach welcher Variable verzweigt werden soll, musst du eine Priorität der Sachen festlegen. Diese bestimmt sich durch den relativen Nutzen. Dieser setzt sich zusammen aus dem Nutzen des jeweiligen Gegenstandes geteilt durch sein Gewicht. Die Prioritäten sehen damit so aus:
Branch and Bound Methode durchführen
Jetzt können wir das Branch and Bound Verfahren starten. Unsere untere Schranke ist 0. Unsere obere Schranke ist die nach Priorität hinzugefügten Gegenstände bis der Koffer voll ist. 
ist damit 1 und wir haben schon 4kg in unserem Koffer. Die zweithöchste Priorität hat Gegenstand 
und wiegt 5 kg. Zusammen mit sind das schon 9 kg. Als nächstes ist 
dran, der 10 kg wiegt. Das passt jetzt aber nicht mehr komplett in unseren Koffer, da wir dann bei 19 kg wären. Deshalb nehmen wir von nur 6/10 in x auf und haben damit genau 15 kg erreicht. Unsere Zielfunktion ist dann: 8+6+6/10*10=20. Wir haben damit unsere obere Schranke ermittelt.
Verzweigen nach der MUB-Regel
Diesmal verzweigen wir nach der Maximum Upper Bound- oder auch MUB-Regel. Das bedeutet: Anders als bei der LIFO-Regel berechnen wir direkt die Schranken aller Teilprobleme. Ausgehend von 
verzweigen wir jetzt nach abfallender Priorität – also zuerst . Links verzweigen wir nach gleich 1 und benennen das Teilproblem 
und rechts nach gleich 0 und nennen es 
. Wir starten mit und berechnen 
. Dadurch, dass in bereits 1 ist, ändert sich an sowie an der Zielfunktion nichts.
Da wir die MUB-Regel verwenden, teilen wir jetzt nicht auf, sondern berechnen erst . Hier soll gleich 0 sein. Demnach nehmen wir und auf und kommen auf genau 15 kg. Das ist unsere erste zulässige Lösung. Wir berechnen unsere Nutzenzielfunktion und kommen auf einen Nutzen von 16. Das ist jetzt unsere untere Schranke. Unser Nutzen darf also nicht weniger als 16 in den folgenden Teilproblemen betragen. Jetzt verzweigen wir weiter und zwar nach dem Gegenstand mit der nächsten Priorität nach – also . Für 
gilt gleich 1. Dabei verändert sich an den Gegenständen, die wir einpacken, und an der Zielfunktion wieder nichts.
Für 
ist das allerdings anders. ist hier 0 und es gilt die Bedingung von vorher, dass gleich 1 ist. Dadurch erhalten wir diese Kombination:
Ergebnisfindung:
Der Zielfunktionswert ist 18. Nach der MUB-Regel machen wir jetzt mit dem Teilproblem weiter, das die höhere obere Schranke hat, also 
. erhält gleich 1 und ist damit unzulässig, da die 15 Kilogramm bei dieser Option überschritten werden. Für 
muss gleich 0, gleich 1 und 
gleich 1 sein und wir erhalten einen Zielfunktionswert von 14.
Wir müssten an dieser Stelle noch weiter verzweigen. Da der Zielfunktionswert aber schon niedriger ist als unsere höchste obere Schranke, können wir an dieser Stelle abbrechen. Unser maximaler Nutzen ist demnach 18. Für dich ist es also am besten, wenn du die Uhr und deine Schuhe einpackst.
Du siehst: Es kommt immer ganz auf das Beispiel an, ob man eher die LIFO- oder die MUB-Regel verwenden sollte.