Branch-and-Bound Verfahren

Mit dem Branch-and-Bound Verfahren (Verzweigung und Schranke) kann man für ein gegebenes ganzzahliges Optimierungsproblem eine optimale Lösung finden. Das Branch & Bound Verfahren führt auf einen Entscheidungsbaum, da die zulässige Menge schrittweise zerlegt wird. Durch Schranken wird dann die Menge in der der Zielfunktionswert liegt, nach und nach eingeschränkt.

Die Idee hinter dem Branching ist das Herausnehmen einer Komponente eines Lösungsvektors, wie beispielsweise die erste die nicht ganzzahlig ist. Anschließend wird eine „Scheibe“ (in der 3-Dimension) mit Hilfe von zwei Ungleichungen aus der zulässigen Menge herausgeschnitten. Ist z.B. die x-Komponente der ersten optimalen Lösung x=15/4=3,75, dann liegt diese also zwischen den ganzen Zahlen 3 und 4. Und genau dieser Abschnitt/Scheibe zwischen 3 und 4 wird nun herausgeschnitten und kommt für die optimale Lösung nicht mehr in Frage. Denn entweder ist die x-Komponente der optimalen ganzzahligen Lösung 4 oder größer, oder aber 3 oder kleiner, dazwischen kann sie aber auf jeden Fall nicht liegen. Man fügt also zu seinem Ausgangsproblem einmal die Nebenbedingung x ≥ 4 und löst dieses. Gleichzeitig muss man aber auch das Ausgangsproblem mit der neuen Nebenbedingung x ≤ 3 lösen und schauen ob hier vielleicht die optimale Lösung liegt. Man bekommt beim Branch & Bound Verfahren also immer mehr kleinere Mengen, für die jeweils der optimaler Punkt bestimmt werden muss.

Nun könnte man auf die Idee kommen, immer wieder das Verfahren des Branching auf die neuen Teilmengen der ursprüngliche Ausgangsmenge anzuwenden. Doch bei größeren Problemen ergibt das immer weitere Verzweigen exponentielle Teilprobleme. Es kommt also zur „kombinatorischen Explosion“.

Um dies zu verhindern, wird nun nur noch ein spezielles Problem (z.B. das mit dem besten optimalen Wert) verzweigt, alle anderen Schranken der nicht-verzweigten Probleme werden sich lediglich gemerkt. Dafür schreibt man das Problem das man nicht verzweigt in eine Liste. Nach dem Verzweigen gesellt sich zu dem einen Problem in der Liste, die zwei neuen Teilprobleme des verzweigten Problems hinzu. Nun wird aus dieser Liste ein spezielles Problem ausgewählt (z.B. das mit dem größten Optimalwert / Auswahl Abhängig von gewählter Heuristik), um anschließend das gewählte Problem aus der Liste zu entfernen und nun zu verzweigen.

Gestoppt wird nun, wenn das Problem mit der größten oberen Schranke einen ganzzahligen optimalen Punkt besitzt. Darüber hinaus können gewisse Teilprobleme auch von weiteren Verzweigungen ausgeschlossen werden (ausloten). Ist z.B. die Lösungsmenge des relaxierten Problems leer, besitzt dieses ebenfalls nur Teilprobleme mit leeren zulässigen Mengen und muss deshalb nicht mehr betrachtet werden. Ebenfalls kann in einem Teilproblem kein optimaler Punkt liegen, wenn die Ungleichungen gilt, dass eine beliebige Unterschranke die beim Start des Verfahrens festgelegt wurde größer als der Optimalwert des Teilproblems ist. Damit wird die oben erwähnte Liste klein gehalten. Entscheidend ist also der Startwert der Unterschranke. Kann man mit einer Heuristik hier schon einen relativen guten Wert bestimmen, verkürzt dies enorm das Branch & Bound-Verfahren, da nicht mehr so oft verzweigt werden muss. Nicht immer hat man aber einen Anhaltspunkt für die Untergrenze. In diesem Fall muss man sie auf plus/minus (bei min/max Problem) Unendlich setzen und kann so am Anfang kein Problem ausschließen. Allerdings wird die Untergrenze jeweils pro Verzweigung angepasst werden. Wird nun also bei einem Teilproblem eine ganzzahlige Lösung berechnet und ist der berechnete Wert größer als die Unterschranke, dann wird die bestehende Unterschranke entsprechend mit dem neu berechneten Wert ersetzt.