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 \(\displaystyle G = a\cdot x\) unter der Nebenbedingung \(\displaystyle Ax <= b\), \(\displaystyle x >=0 \) und \(\displaystyle x\) ganzzahlig, dabei sind \(\displaystyle A\): n*m -Matrix\(\displaystyle x\): \(\displaystyle n\)-dimensionaler Vektor\(\displaystyle a\): \(\displaystyle n\)-dimensionaler Vektor\(\displaystyle b\): \(\displaystyle m\)-dimensionaler Vektor\(\displaystyle a\cdot x\): skalares Produkt, lineare Funktion mit \(\displaystyle n\) Variablen, reeller Wert\(\displaystyle Ax\) : \(\displaystyle m\)-dimensionaler Vektor, der aus der Multiplikation der Matrix \(\displaystyle A\) mit dem \(\displaystyle n\) dimensionalen Vektor \(\displaystyle x\) entsteht.
Verzichtet man auf die Forderung "\(\displaystyle 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.

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 \(\displaystyle G = a\cdot x\) unter der Nebenbedingung \(\displaystyle Ax <= b\) und \(\displaystyle x >=0\).
Das so entstandene Problem nennen wir \(\displaystyle 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. \(\displaystyle x_{1},\, x_{2} \\, \, \, x_{n}\) sind nicht ganzzahlig.
Nun versucht man Lösungen zu finden, bei denen \(\displaystyle x_{1}\) ganzzahlig ist. Sei \(\displaystyle s_{1}\) die größte ganze Zahl kleiner als \(\displaystyle x_{1}\). Dann formuliert man zwei neue lineare Optimierungsprobleme \(\displaystyle P_{11}\) und \(\displaystyle P_{12}\) derart, dass die vorher gefundene Lösung jeweils ausgeschlossen wird:
\(\displaystyle P_{11}\): Maximiere \(\displaystyle G = a\cdot x\) unter der Nebenbedingung \(\displaystyle Ax <= b\), \(\displaystyle x >=0\), \(\displaystyle x_{1} <= s_{1}\)
\(\displaystyle P_{12}\): Maximiere \(\displaystyle G = a\cdot x\) unter der Nebenbedingung \(\displaystyle Ax <= b\), \(\displaystyle x >=0\), \(\displaystyle 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:
  1. es gibt keine zulässige Lösung
  2. es gibt eine zulässige Lösung mit \(\displaystyle x_{1}\) ganzzahlig
  3. es gibt eine zulässige Lösung mit \(\displaystyle x_{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 \(\displaystyle 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 \(\displaystyle x_{1} = t_{1}\) gefunden, dann sucht man Lösungen für ein ganzzahliges \(\displaystyle x_{2}\) ausgehend von folgendem Problem \(\displaystyle P_{1}\):
Maximiere \(\displaystyle G = a\cdot x\) unter der Nebenbedingung \(\displaystyle Ax <= b\), \(\displaystyle x >=0\), \(\displaystyle x_{1} = t_{1}\).
Dies ist das Ausgangsproblem ohne die Ganzzahligkeitsbedingung und mit der gefundenen Lösung für \(\displaystyle x_{1}\) als zusätzliche Nebenbedingung.
Analog dem beschriebenen Verfahren sucht man nun eine optimale Lösung mit ganzzahligen \(\displaystyle x_{2}\).
Danach fährt man mit diesem Verfahren fort für \(\displaystyle 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.

Ein einfaches Beispiel

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

Es gibt Dinge, die den meisten Menschen unglaublich erscheinen, die nicht Mathematik studiert haben.

Archimedes

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е