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.
 
 

Vorgehensweise

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.

Branch (Verzweigung)

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.

Bound (Abgrenzung)

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.

Beispiel-Problem

Maximiere G=axG = a\cdot x unter der Nebenbedingung Ax<=bAx <= b, x>=0 x >=0 und xx ganzzahlig, dabei sind AA: n*m -Matrix xx: nn-dimensionaler Vektor aa: nn-dimensionaler Vektor bb: mm-dimensionaler Vektor axa\cdot x: skalares Produkt, lineare Funktion mit nn Variablen, reeller Wert AxAx : mm-dimensionaler Vektor, der aus der Multiplikation der Matrix AA mit dem nn dimensionalen Vektor xx entsteht.
Verzichtet man auf die Forderung "xx 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.

Lösungsweg

Das Problem kann man mit Hilfe des Branch and Bound Verfahrens lösen.
Dazu lässt man zunächst die Ganzzahligkeitsbedingung weg:
Maximiere G=axG = a\cdot x unter der Nebenbedingung Ax<=bAx <= b und x>=0x >=0.
Das so entstandene Problem nennen wir P0P_{0}. Dieses nun lineare Optimierungsproblem löst man mit dem Simplex-Verfahren. Im Allgemeinen wird die erhaltene Lösung nicht ganzzahlig sein, d.h. x1,x2,xnx_{1},\, x_{2} \\, \, \, x_{n} sind nicht ganzzahlig.
Nun versucht man Lösungen zu finden, bei denen x1x_{1} ganzzahlig ist. Sei s1s_{1} die größte ganze Zahl kleiner als x1x_{1}. Dann formuliert man zwei neue lineare Optimierungsprobleme P11P_{11} und P12P_{12} derart, dass die vorher gefundene Lösung jeweils ausgeschlossen wird:
P11P_{11}: Maximiere G=axG = a\cdot x unter der Nebenbedingung Ax<=bAx <= b, x>=0x >=0, x1<=s1x_{1} <= s_{1}
P12P_{12}: Maximiere G=axG = a\cdot x unter der Nebenbedingung Ax<=bAx <= b, x>=0x >=0, x1>=s1+1x_{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:
  1. es gibt keine zulässige Lösung
  2. es gibt eine zulässige Lösung mit x1x_{1} ganzzahlig
  3. es gibt eine zulässige Lösung mit x1x_{1} nicht ganzzahlig
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 x1x_{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 x1=t1x_{1} = t_{1} gefunden, dann sucht man Lösungen für ein ganzzahliges x2x_{2} ausgehend von folgendem Problem P1P_{1}:
Maximiere G=axG = a\cdot x unter der Nebenbedingung Ax<=bAx <= b, x>=0x >=0, x1=t1x_{1} = t_{1}.
Dies ist das Ausgangsproblem ohne die Ganzzahligkeitsbedingung und mit der gefundenen Lösung für x1x_{1} als zusätzliche Nebenbedingung.
Analog dem beschriebenen Verfahren sucht man nun eine optimale Lösung mit ganzzahligen x2x_{2}.
Danach fährt man mit diesem Verfahren fort für x3xnx_{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.

Ein einfaches Beispiel

Anhand einer konkreten Aufgabenstellung zeigen wir das Verfahren.
Das Ausgangsproblem lautet:
Maximiere G=x1+x2G = x_{1} + x_{2} mit den Nebenbedingungen 2x1+x2<=42x_{1} + x_{2} <= 4, x1+2x2<=3x_{1} + 2x_{2} <= 3, x1,x2>=0x_{1},\, x_{2} >= 0 ganzzahlig.
Wir lassen die Ganzzahligkeitbedingung weg und finden mit dem Simplex-Verfahren die Lösung
G=7/3G = 7/3, x1=5/3=12/3x_{1} = 5/3 = 1 2/3 und x2=2/3x_{2} = 2/3. Wir fahren fort mit dem Ziel, eine Lösung mit ganzzahligem x1x_{1} zu finden. Dazu bilden wir 2 weitere Optimierungsaufgaben, eine mit der zusätzlichen Nebenbedingung x1<=1 x_{1} <= 1, die andere mit x1>=2 x_{1} >= 2.
P11P_{11}: Maximiere G=x1+x2G = x_{1} + x_{2} mit den Nebenbedingungen 2x1+x2<=42 x_{1} + x_{2} <= 4, x1+2x2<=3 x_{1} + 2 x_{2} <= 3, x1<=1 x_{1} <= 1, x1,x2>=0 x_{1},\, x_{2} >= 0.
P12P_{12}: Maximiere G=x1+x2G = x_{1} + x_{2} mit den Nebenbedingungen 2x1+x2<=42 x_{1} + x_{2} <= 4, x1+2x2<=3 x_{1} + 2 x_{2} <= 3, x1>=2 x_{1} >= 2,
x1,x2>=0 x_{1},\, x_{2} >= 0.
Das Problem P11P_{11} hat die Lösung G=2G = 2, x1=1x_{1} = 1, x2=1 x_{2} = 1.
Da x1x_{1} und x2x_{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 P12P_{12} und erhalten: G=2G = 2, x1=2 x_{1} = 2, x2=0 x_{2} = 0.
Auch dies ist wegen der Ganzzahligkeit eine zulässige Lösung. Da sowohl für P11P_{11} als auch für P12P_{12} die Zielfunktion den Wert G=2G = 2 annimmt hat das Problem 2 optimale Lösungen.

Bewertung des Verfahrens

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.

Geschichte

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.

Literatur

  • Dakin, R. J. (1965). A tree-search algorithm for mixed integer programming problems.
    In: The Computer Journal, Volume 8, S. 250-255
  • Land, A. H. und A. G. Doig (1960). An automatic method of solving discrete programming problems.
    In: Econometrica 28, S. 497-520

Wir Mathematiker sind die wahren Dichter, nur müssen wir das, was unsere Phantasie schafft, noch beweisen.

Leopold Kronecker

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Branch-and-Bound aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе