Branch-and-Bound

Branch-and-Bound (Verzweigung und Schranke) ist ein mathematisches Verfahren aus dem Bereich Operations Research, dessen Ziel es ist, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch-and-Bound gehört zu den Entscheidungsbaum-Verfahren.

Der Branch-and-Bound-Algorithmus besteht aus zwei Teilen: dem Branch (Verzweigung) und dem Bound (Abgrenzung). Im ungünstigsten Fall müssen alle möglichen Belegungen aufgezählt werden. Es wird versucht, den zu untersuchenden Lösungsraum möglichst klein zu halten, indem Zweige im aufgespannten Entscheidungsbaum als suboptimal identifiziert werden und aus der weiteren Betrachtung herausfallen.

Der Branch-Schritt dient dazu, das vorliegende Problem in zwei oder mehr Teilprobleme aufzuteilen, die eine Vereinfachung des ursprünglichen Problems darstellen. Durch rekursives Ausführen des Branching-Schritts für die erhaltenen Teilprobleme entsteht eine Baum-Struktur. Es gibt verschiedene Auswahlverfahren für die Wahl des nächsten zu bearbeitenden Knotens im Branching-Baum, die unterschiedliche Zielsetzungen haben. Im Folgenden werden drei häufig verwendete Verfahren beschrieben:

Tiefensuche: Von den noch nicht bearbeiteten Teilproblemen wird das gewählt, welches als letztes eingefügt wurde (Last In - First Out). Mit dieser Auswahlregel arbeitet sich das Verfahren im Baum möglichst schnell in die Tiefe, so dass sehr schnell eine zulässige Lösung erlangt wird, über deren Qualität jedoch nichts ausgesagt werden kann.

Breitensuche: Von den noch nicht bearbeiteten Teilproblemen wird das gewählt, welches als erstes in den Baum eingefügt wurde (First In - First Out). Bei Verwendung dieser Auswahlregel werden die Knoten im Baum pro Ebene abgearbeitet, bevor tiefer gelegene Knoten betrachtet werden. Eine zulässige Lösung wird in der Regel erst relativ spät erhalten, hat aber tendenziell einen guten Lösungswert.

Bestensuche: Von den noch nicht bearbeiteten Teilproblemen wird das gewählt, welches die beste untere Schranke vorweist. Durch diese qualitativ arbeitende Auswahlregel wird versucht, direkt einen sehr guten Lösungswert als erste Lösung zu erhalten.

Der Bound-Schritt hat die Aufgabe, bestimmte Zweige des Baumes "abzuschneiden", d.h. in der weiteren Berechnung nicht mehr zu betrachten, um so den Rechenaufwand zu begrenzen. Dies erreicht der Algorithmus durch Berechnung und Vergleich zweier Schranken. Der Weg von der Wurzel des Baumes zu einem Teilproblem bildet die untere Schranke ("lower bound") dieses Teilproblems - auf welche Weise sich auch der weitere Weg durch den Baum gestaltet, der Weg zum Teilproblem ist festgelegt. Als obere Schranke dient eine vorerst optimale zulässige Lösung. Diese erhält man durch Berechnung eines kompletten Zweiges (von der Wurzel zu einem Blatt des Entscheidungsbaumes) - ebenso ist es aber auch möglich, eine Heuristik vor dem eigentlichen Branch-and-Bound Verfahren zu berechnen und die erhaltene Lösung als obere Schranke zu verwenden.

Übersteigt nun die untere Schranke in einem Teilproblem die obere Schranke, so kann der aktuell betrachtete Teilbaum "abgeschnitten" werden, da es mindestens eine bessere zulässige Lösung gibt, die nicht mehr erreicht werden kann. Sollte hingegen eine Komplettlösung berechnet werden, die besser als die obere Schranke ist, so wird diese ersetzt und als neue optimale Lösung vorgehalten.

Maximiere $G = a\cdot x$ unter der Nebenbedingung $Ax <= b$, $x >=0$ und $x$ ganzzahlig, dabei sind $A$: n*m -Matrix $x$: $n$-dimensionaler Vektor $a$: $n$-dimensionaler Vektor $b$: $m$-dimensionaler Vektor $a\cdot x$: skalares Produkt, lineare Funktion mit $n$ Variablen, reeller Wert $Ax$ : $m$-dimensionaler Vektor, der aus der Multiplikation der Matrix $A$ mit dem $n$ dimensionalen Vektor $x$ entsteht.

Verzichtet man auf die Forderung "$x$ ganzzahlig", dann handelt es sich um ein lineares Optimierungsproblem, das man mit Hilfe des Simplex-Verfahrens lösen kann. Wegen der Ganzzahligkeitsbedingung ist das Ausgangsproblem aber nicht linear.

Das Problem kann man mit Hilfe des Branch and Bound Verfahrens lösen.

Dazu lässt man zunächst die Ganzzahligkeitsbedingung weg:

Maximiere $G = a\cdot x$ unter der Nebenbedingung $Ax <= b$ und $x >=0$.

Das so entstandene Problem nennen wir $P_{0}$. Dieses nun lineare Optimierungsproblem löst man mit dem Simplex-Verfahren. Im Allgemeinen wird die erhaltene Lösung nicht ganzzahlig sein, d.h. $x_{1},\, x_{2} \\, \, \, x_{n}$ sind nicht ganzzahlig.

Nun versucht man Lösungen zu finden, bei denen $x_{1}$ ganzzahlig ist. Sei $s_{1}$ die größte ganze Zahl kleiner als $x_{1}$. Dann formuliert man zwei neue lineare Optimierungsprobleme $P_{11}$ und $P_{12}$ derart, dass die vorher gefundene Lösung jeweils ausgeschlossen wird:

$P_{11}$: Maximiere $G = a\cdot x$ unter der Nebenbedingung $Ax <= b$, $x >=0$, $x_{1} <= s_{1}$

$P_{12}$: Maximiere $G = a\cdot x$ unter der Nebenbedingung $Ax <= b$, $x >=0$, $x_{1}>= s_{1}+1$.

Eine solche Aufteilung in Unterprobleme nennt man branch (engl. Verzweigung).

Diese beiden Probleme löst man wiederum mit dem Simplex-Verfahren. Dabei können folgende Fälle auftreten:

Bei Fall (3) bildet man - analog oben - wieder 2 neue Probleme, indem man die gefundene Lösung durch geeignete zusätzliche Nebenbedingungen wieder ausschließt.

Bei Fall (1) und (2) versucht man mit den verbleibenden Problemen noch eine bessere Lösung mit ganzzahligem $x_{1}$ zu finden.

Die Aufteilung in 2 neue Probleme entfällt, wenn man vorher bereits eine bessere ganzzahlige Lösung (bound; engl. Schranke) gefunden hat.

Hat man schließlich die optimale Lösung mit einem ganzzahligen $x_{1} = t_{1}$ gefunden, dann sucht man Lösungen für ein ganzzahliges $x_{2}$ ausgehend von folgendem Problem $P_{1}$:

Maximiere $G = a\cdot x$ unter der Nebenbedingung $Ax <= b$, $x >=0$, $x_{1} = t_{1}$.

Dies ist das Ausgangsproblem ohne die Ganzzahligkeitsbedingung und mit der gefundenen Lösung für $x_{1}$ als zusätzliche Nebenbedingung.

Analog dem beschriebenen Verfahren sucht man nun eine optimale Lösung mit ganzzahligen $x_{2}$.

Danach fährt man mit diesem Verfahren fort für $x_{3} \dots x_{n}$.

Es ist durchaus möglich, dass man keine Lösung findet. D.h. das Ausgangsproblem hat keine zulässigen Lösungen.

Anhand einer konkreten Aufgabenstellung zeigen wir das Verfahren.

Das Ausgangsproblem lautet:

Maximiere $G = x_{1} + x_{2}$ mit den Nebenbedingungen $2x_{1} + x_{2} <= 4$, $x_{1} + 2x_{2} <= 3$, $x_{1},\, x_{2} >= 0$ ganzzahlig.

Wir lassen die Ganzzahligkeitbedingung weg und finden mit dem Simplex-Verfahren die Lösung

$G = 7/3$, $x_{1} = 5/3 = 1 2/3$ und $x_{2} = 2/3$. Wir fahren fort mit dem Ziel, eine Lösung mit ganzzahligem $x_{1}$ zu finden. Dazu bilden wir 2 weitere Optimierungsaufgaben, eine mit der zusätzlichen Nebenbedingung $x_{1} <= 1$, die andere mit $x_{1} >= 2$.

$P_{11}$: Maximiere $G = x_{1} + x_{2}$ mit den Nebenbedingungen $2 x_{1} + x_{2} <= 4$, $x_{1} + 2 x_{2} <= 3$, $x_{1} <= 1$, $x_{1},\, x_{2} >= 0$.

$P_{12}$: Maximiere $G = x_{1} + x_{2}$ mit den Nebenbedingungen $2 x_{1} + x_{2} <= 4$, $x_{1} + 2 x_{2} <= 3$, $x_{1} >= 2$,

$x_{1},\, x_{2} >= 0$.

Das Problem $P_{11}$ hat die Lösung $G = 2$, $x_{1} = 1$, $x_{2} = 1$.

Da $x_{1}$ und $x_{2}$ ganzzahlig sind ist dies eine zulässige Lösung des Ausgangsproblems. Wir wissen aber noch nicht, ob es eine bessere Lösung gibt.

Dazu lösen wir Problem $P_{12}$ und erhalten: $G = 2$, $x_{1} = 2$, $x_{2} = 0$.

Auch dies ist wegen der Ganzzahligkeit eine zulässige Lösung. Da sowohl für $P_{11}$ als auch für $P_{12}$ die Zielfunktion den Wert $G = 2$ annimmt hat das Problem 2 optimale Lösungen.

Beim Branch-and-Bound-Verfahren müssen mehrere - in ungünstigen Fällen sehr viele - Optimierungsprobleme gespeichert, verwaltet und mit Hilfe des Simplex-Verfahrens gelöst werden. Insbesondere bei großen Problemen, die mehrere hunderttausend Variablen und Nebenbedingungen haben können, führt dies zu hohem Rechen- und Speicheraufwand. Dafür vermeidet man den Nachteil des Schnittebenenverfahrens von Gomory, bei dem numerische Probleme durch mangelnde Genauigkeit der Zahlendarstellung im Computer die Lösungssuche erschweren. In der Praxis werden bei der Lösung ganzzahliger Optimierungsprobleme oft beide Verfahren zu Branch-and-Cut kombiniert. Dabei werden im Wurzelknoten und manchmal auch in weiteren Knoten des Branch-and-Bound-Baumes Schnittebenen separiert, um die lineare Relaxierung zu verschärfen.

Die Idee von Branch-and-Bound wurde erstmals 1960 von A.H. Land und A.G. Doig im Bereich des Operations Research formuliert. R.J. Dakin gab 1965 einen einfach zu implementierenden Algorithmus an.