Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Branch and bound aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Branch-and-Bound

Branch-and-Bound (Verzweigung und Schranke) ist eine im Bereich
Operations Research häufig verwendete mathematische Methode, deren Ziel
darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste
Lösung zu finden. Branch-and-Bound führt auf einen Entscheidungsbaum, ist
selbst aber kein spezielles Verfahren, sondern eine Behandlungsmethode, ein
Meta-Verfahren. Für konkrete kombinatorische Optimierungsprobleme ergeben
sich dementsprechend angepasste Branch-and-Bound-Algorithmen.

Das Prinzip

Im Optimierungsproblem $f(x)\backslash to\backslash min!$ bei $x\backslash in\; D$ sei
der zulässige Bereich $D$ eine diskrete Menge, eventuell sogar
endlich. Alle zugelassenen Belegungen $x\backslash in\; D$ durchzuprobieren,
scheitert meist an inakzeptabel langen Rechenzeiten. Deshalb wird
$D$ nach und nach in mehrere Teilmengen aufgespalten (Branch).
Mittels geeigneter Schranken (Bound) sollen viele suboptimale Belegungen
frühzeitig erkannt und ausgesondert werden, so daß der zu durchmusternde
Lösungsraum klein gehalten wird. Im ungünstigsten Fall werden alle Belegungen
aufgezählt (vollständige Enumeration).

Branch, die 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 im allgemeinen 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, die Schranke

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. Obere Schranken ergeben sich aus jeder zulässigen Lösung. Dafür kann gegebenenfalls zuvor eine Heuristik benutzt werden.

Um gute untere Schranken (Bound) zu finden, wird oft eine Relaxation
zugrunde gelegt. Das ist eine auf einer Menge $E\backslash supseteq\; D$
definierte, leicht zu berechnende Funktion $g$ mit $g(x)\backslash le$
f(x) für alle $x\backslash in\; D$. Das relaxierte Problem
$g(x)\backslash to\backslash min!$ bei $x\backslash in\; E$ sei leicht lösbar und
besitze eine Optimallösung $\backslash bar\{x\}$. Dann gilt offensichtlich
$f(x)\backslash ge\; g(\backslash bar\{x\})$ für alle $x\backslash in\; D$. Bei
$\backslash bar\{x\}\backslash in\; D\backslash land\; f(\backslash bar\{x\})=g(\backslash bar\{x\})$ ist $\backslash bar\{x\}$
auch Optimallösung des nicht relaxierten Problems.

Diese Überlegungen sind auch auf Teilprobleme anwendbar, wo also die Menge
$D$ bereits aufgespalten wurde. Kennt man bereits eine zulässige
Lösung $\backslash hat\{x\}\backslash in\; D$ und ist die untere Schranke für ein
Teilproblem größer als $f(\backslash hat\{x\})$, dann braucht man jenes
Teilproblem nicht weiter zu untersuchen, weil es keine Optimallösung ergibt.

Dominanz

Von Dominanz spricht man, wenn für jede Belegung $\backslash tilde\{x\}$
aus einer Teilmenge $T\backslash subset\; D$ eine nicht schlechtere zulässige
Lösung $\backslash bar\{x\}\backslash in\; D\backslash setminus\; T$ konstruiert werden kann. Werden
nicht alle Optimallösungen gesucht, sondern nur eine, dann erübrigt sich die
Suche in $T$, selbst wenn die Schranken alleine nicht ausreichen,
$T$ von der weiteren Durchmusterung auszuschließen. Dies steigert
mitunter die Effizienz des Verfahrens erheblich, beispielsweise im mehrdimensionalen Zuschnittsproblem, obwohl Dominanztests nicht zur ursprünglichen Methode Branch-and-Bound gehören.

Beispiel: $z=x\_1-x\_2-x\_1/x\_2\backslash to\backslash min!$ bei
$x\_1,x\_2\backslash in\backslash \{2,3,4,5\backslash \}$ sei zu lösen. Eine untere Schranke ergibt
sich sofort, indem alle Summanden nach unten abgeschätzt werden, also
$2-5-5/2=-5\{,\}5$. Branch-and-Bound ohne Dominanzüberlegungen anzuwenden,
erweist sich hier als unnötig aufwändig. Wegen $z=x\_1*(1-1/x\_2)-x\_2\backslash ge$
x_1/2-x_2 ist $x\_1$ so klein wie möglich zu wählen, einerlei wie groß
$x\_2$ ist, das heißt $x\_1=2$. Für $x\_2=5$ wird $z=-3\{,\}4$; bei
$x\_2\backslash le\; 4$ ist $z>-3$ und damit nicht optimal. Die einzige Optimallösung
lautet $x\_1=2,\backslash ;x\_2=5$.

Anwendung auf Probleme der ganzzahligen linearen Optimierung

Das allgemeine ganzzahlige lineare Optimierungsproblem hat die Gestalt

Maximiere G = a*x

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, reeller Wert
Ax : m-dimensionaler Vektor, der aus der Multiplikation der Matrix A
mit dem n dimensionalen Vektor x entsteht.

Durch Vernachlässigung der Ganzzahligkeitsbedingungen erhält man die stetige
Relaxation, die mit dem Simplexverfahren gelöst werden kann. Wegen
der geforderten Ganzzahligkeit gehört das Ausgangsproblem aber nicht zu den
linearen Optimierungsproblemen.

Lösungsweg

Das Problem kann man mit Hilfe des Branch-and-Bound-Verfahrens lösen. Zuerst wird als
bisher bester Zielfunktionswert $\backslash hat\{G\}:=-\backslash infty$ gesetzt und die Ganzzahligkeitsbedingung weggelassen:

Maximiere G = a*x

unter der Nebenbedingung Ax <= b
x >= 0

Das so entstandene Problem nennen wir P₀. Dieses nun lineare Optimierungsproblem löst man mit dem Simplex-Verfahren. Im Allgemeinen wird die erhaltene Lösung nicht ganzzahlig sein, d.h. x₁, x₂ ... x_n sind nicht durchgängig ganzzahlig. Ohne Beschränkung der Allgemeinheit betreffe dies auch x₁.

Nun versucht man, Lösungen mit ganzzahligem x₁ zu finden. Sei s₁ die größte ganze Zahl kleiner als x₁. Dann formuliert man zwei neue lineare Optimierungsprobleme P₁₁ und P₁₂ derart, dass die vorher gefundene Lösung jeweils ausgeschlossen wird:

P₁₁ Maximiere G = a*x

unter der Nebenbedingung Ax <= b
x >= 0
x₁ <= s₁ P₁₂ Maximiere G = a*x

unter der Nebenbedingung Ax <= b
x >= 0
x₁ >= s₁ + 1

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

Beide Teilprobleme werden mit dem dualen Simplexverfahren gelöst. Folgende Fälle können
auftreten:

(1) Der zulässige Bereich wird leer.

(2) Man findet eine ganzzahlige Optimallösung für das Teilproblem.

(3) x₁ wird ganzzahlig, dafür aber ein anderes x_i nicht, wobei es keine
Rolle spielt, ob jenes x_i vorher ganzzahlig war oder nicht.

Im Fall (1) erledigt sich das Teilproblem. In den anderen Fällen gilt das
auch, wenn $G\backslash le\backslash hat\{G\}$ ist und nur eine Optimallösung gesucht
wird oder ist und alle Optimallösungen gesucht werden.
Ansonsten speichert man im Fall (2) die gefundene Lösung als bisher beste und
ersetzt $\backslash hat\{G\}$ durch $G$, während im Fall (3) das
Teilproblem weiter aufzuspalten ist.

Auf diese Weise wird der gesamte Lösungsraum durchsucht und eine Optimallösung gefunden, wenn es eine gibt und das Verfahren nicht vorzeitig abgebrochen wurde. Es ist durchaus möglich, dass man trotz erschöpfender Suche keine Lösung findet. Dann besitzt das Ausgangsproblem keine zulässigen Lösungen.

Ein einfaches Beispiel

Anhand einer konkreten Aufgabenstellung zeigen wir das Verfahren.

Das Ausgangsproblem lautet:

Maximiere G = x₁ + x₂

mit den Nebenbedingungen 2x₁ + x₂ <= 4
x₁ + 2x₂ <= 3
x₁, x₂ >= 0 ganzzahligWir lassen die Ganzzahligkeitbedingung weg und finden mit dem Simplex-Verfahren die Lösung

G = 7/3
x₁ = 5/3 = 1 2/3
x₂ = 2/3

Wir fahren fort mit dem Ziel, eine Lösung mit ganzzahligem x₁ zu finden. Dazu bilden wir 2 weitere Optimierungsaufgaben, eine mit der zusätzlichen Nebenbedingung x₁ <= 1, die andere mit x₁ >= 2.

P₁₁ Maximiere G = x₁ + x₂

mit den Nebenbedingungen 2x₁ + x₂ <= 4
x₁ + 2x₂ <= 3
x₁ <= 1
x₁, x₂ >= 0 P₁₂ Maximiere G = x₁ + x₂

mit den Nebenbedingungen 2x₁ + x₂ <= 4
x₁ + 2x₂ <= 3
x₁ >= 2
x₁, x₂ >= 0Das Problem P₁₁ hat die Lösung

G = 2
x₁ = 1
x₂ = 1

Da x₁ und x₂ 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₁₂ und erhalten:

G = 2
x₁ = 2
x₂ = 0

Auch dies ist wegen der Ganzzahligkeit eine zulässige Lösung. Da sowohl für P₁₁ als auch für P₁₂ die Zielfunktion den Wert 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.

Zur 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

       VIDEO-NEWS UND ANGEBOTE