Branch and Bound
Branch and Bound 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.
| Table of contents |
|
2 Beispiel-Problem 3 Lösungsweg 4 Ein einfaches Beispiel 5 Bewertung des Verfahrens 6 Geschichte 7 Literatur |
Der Branch-and-Bound Algorithmus besteht aus zwei Teilen: dem Branching ("Verzweigen") und dem Bounding ("Beschränken"). Im ungünstigsten Fall müssen alle möglichen Belegungen enumeriert 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 Branching-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 ("tree structure"). 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 ("depth first search"): Von den noch nicht bearbeiteten Teilproblemen wird das gewählt, welches als letztes eingefügt wurde. 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 ("breadth first search"): Von den noch nicht bearbeiteten Teilproblemen wird das gewählt, welches als erstes in den Baum eingefügt wurde. 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 ("best first search"): 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.
Ü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.
unter der Nebenbedingung Ax <= b
x >=0 und x ganzzahlig
A: n*m -Matrix
x: n-dimensionaler Vektor
a: n-dimensionaler Vektor
b: m-dimensionaler Vektor
a*x: skalares Produkt, lineare Funktion mit n Variablen, reeler Wert
Ax : m-dimensionaler Vektor, der aus der Multiplikation der Matrix A
mit dem n dimensionalen Vektor x entsteht.
Das Problem kann man mit Hilfe des Branch and Bound Verfahrens lösen.
Dazu läßt man zunächst die Ganzzahligkeitsbedingung weg:
unter der Nebenbedingung Ax <= b
x >=0
Nun versucht man Lösungen zu finden, bei denen x1 ganzzahlig ist. Sei s1 die größte ganze Zahl kleiner als x1. Dann formuliert man 2 neue lineare Optimierungsprobleme P11 und P12 derart, dass die vorher gefundene Lösung jeweils ausgeschlossen wird:
unter der Nebenbedingung Ax <= b
x >=0
x1 <= s1
unter der Nebenbedingung Ax <= b
x >=0
x1 >= s1 +1
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
Bei Fall (3) bildet man - analog oben - wieder 2 neue Probleme, indem man die gefundene Lösung durch geeignete zusätzliche Nebenbedingungen wieder ausschliesst.
Bei Fall (1) und (2) versucht man mit den verbleibenden Problemen noch eine bessere Lösung mit ganzzahligem x1 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 = t1 gefunden, dann sucht man Lösungen für ein ganzzahliges x2 ausgehend von folgendem Problem P1:
unter der Nebenbedingung Ax <= b
x >=0
x1 <= t1
Analog dem beschriebenen Verfahren sucht man nun eine optimale Lösung mit ganzzahligen x2.
Danach fährt man mit diesem Verfahren fort für x3 ... xn.
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:
mit den Nebenbedingungen 2x1 + x2 <= 4
x1 + 2x2 <= 3
x1, x2 >= 0 ganzzahlig
mit den Nebenbedingungen 2x1 + x2 <= 4
x1 + 2x2 <= 3
x1 <= 1
x1, x2 >= 0
mit den Nebenbedingungen 2x1 + x2 <= 4
x1 + 2x2 <= 3
x1 >= 2
x1, x2 >= 0
Dazu lösen wir Problem P12 und erhalten:
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 10.000 Variablen und Nebenbedingungen haben können, führt dies zu zu hohem Rechen- und Speicheraufwand.
Dafür vermeidet man den Nachteil des Cutting-Plane-Verfahrens von Gomory, bei dem Rundungsprobleme die Lösungssuche erschweren.Vorgehensweise
Branching
Bounding
Der Bounding-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 ("upper bound") 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.Beispiel-Problem
Maximiere G = a*x
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'\'.Lösungsweg
Maximiere G = a*x
Das so entstandene Problem nennen wir P0. 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 ... xn sind nicht ganzzahlig.P11 Maximiere G = a*x
P12 Maximiere G = a*x
Eine solche Aufteilung in Unterprobleme nennt man branch (engl. Verzweigung).
(2) es gibt eine zulässige Lösung mit x1 ganzzahlig
(3) es gibt eine zulässige Lösung mit x1 nicht ganzzahlig Maximiere G = a*x
Dies ist das Ausgangsproblem ohne die Ganzzahligkeitsbedingung und mit der gefundenen Lösung für x1 als zusätzliche Nebenbedingung.Ein einfaches Beispiel
Maximiere G = x1 + x2
Wir lassen die Ganzzahligkeitbedingung weg und finden mit dem Simplex-Verfahren die Lösung G = 7/3
x1 = 5/3 = 1 2/3
x2 = 2/3Wir fahren fort mit dem Ziel, eine Lösung mit ganzzahligem x1 zu finden. Dazu bilden wir 2 weitere Optimierungsaugaben, eine mit der zusätzlichen Nebenbedingung x1 <= 1, die andere mit x1 >= 2.P11 Maximiere G = x1 + x2
P12 Maximiere G = x1 + x2
Das Problem P11 hat die Lösung G = 2
x1 = 1
x2 = 1Da x1 und x2 ganzzahlig sind ist dies eine zulässige Lösung des Ausgangsproblems. Wir wissen aber noch nicht, ob es eine bessere Lösung gibt. G = 2
x1 = 2
x2 = 0Auch dies ist wegen der Ganzzahligkeit eine zulässige Lösung. Da sowohl für P11 als auch für P12 die Zielfunktion den Wert G = 2 annimmt hat das Problem 2 optimale Lösungen.Bewertung des Verfahrens