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.

Inhaltsverzeichnis

Das Prinzip

Im Optimierungsproblem f(x)\to\min! bei x\in D sei der zulässige Bereich D eine diskrete Menge, eventuell sogar endlich. Alle zugelassenen Belegungen x\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 dass der zu durchmusternde Lösungsraum klein gehalten wird. Im ungünstigsten Fall werden alle Belegungen aufgezählt (vollständige Enumeration).

Branch, die Verzweigung

Der Aufteilungsschritt (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 Aufteilungsschritts für die erhaltenen Teilprobleme entsteht eine Baumstruktur. Es gibt verschiedene Auswahlverfahren für die Wahl des nächsten zu bearbeitenden Knotens im Aufteilungsbaum, die unterschiedliche Zielsetzungen haben. Im Folgenden werden zwei 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. Diese Strategie führt auch tendenziell früh zu brauchbaren unteren Schranken.

Die Verfahren sind kombinierbar. Eine erste Lösung lässt sich zum Beispiel mit einer Tiefensuche bestimmen, um dann bei einer anschließenden Bestensuche bereits eine globale obere bzw. untere Schranke zu haben.

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\supseteq D definierte, leicht zu berechnende Funktion g mit g(x)\le
f(x) für alle x\in D. Das relaxierte Problem g(x)\to\min! bei x\in E sei leicht lösbar und besitze eine Optimallösung \bar{x}. Dann gilt offensichtlich f(x)\ge g(\bar{x}) für alle x\in D. Bei \bar{x}\in D\land f(\bar{x})=g(\bar{x}) ist \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 \hat{x}\in D und ist die untere Schranke für ein Teilproblem größer als f(\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 \tilde{x} aus einer Teilmenge T\subset D eine nicht schlechtere zulässige Lösung \bar{x}\in D\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\to\min! bei x_1,x_2\in\{2,3,4,5\} 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\ge
x_1/2-x_2 ist x1 so klein wie möglich zu wählen, einerlei wie groß x2 ist, das heißt x1 = 2. Für x2 = 5 wird z = − 3,4; bei x_2\le 4 ist z > − 3 und damit nicht optimal. Die einzige Optimallösung lautet x_1=2,\;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
  • mit
    • 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 \hat{G}:=-\infty gesetzt und die Ganzzahligkeitsbedingung weggelassen:

  • Maximiere   G = a*x
  • unter der Nebenbedingung
    Ax ≤ b
    x ≥ 0

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 durchgängig ganzzahlig. Ohne Beschränkung der Allgemeinheit betreffe dies auch x1.

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

  • P11 – Maximiere   G = a*x
  • unter der Nebenbedingung
    Ax ≤ b
    x ≥ 0
    x1 ≤ s1


  • P12 – Maximiere   G = a*x
  • unter der Nebenbedingung
    Ax ≤ b
    x ≥ 0
    x1 ≥ s1 + 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. x1 wird ganzzahlig, dafür aber ein anderes xi nicht, wobei es keine Rolle spielt, ob jenes xi vorher ganzzahlig war oder nicht.

Im Fall (1) erledigt sich das Teilproblem. In den anderen Fällen gilt das auch, wenn G\le\hat{G} ist und nur eine Optimallösung gesucht wird oder G<\hat{G} ist und alle Optimallösungen gesucht werden. Ansonsten speichert man im Fall (2) die gefundene Lösung als bisher beste und ersetzt \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 = x1 + x2
  • mit den Nebenbedingungen
    2x1 + x2 ≤ 4
    x1 + 2x2 ≤ 3
    x1, x2 ≥ 0 ganzzahlig

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

  • G = 7/3
  • x1 = 5/3 = 1 2/3
  • x2 = 2/3

Wir fahren fort mit dem Ziel, eine Lösung mit ganzzahligem x1 zu finden. Dazu bilden wir 2 weitere Optimierungsaufgaben, eine mit der zusätzlichen Nebenbedingung x1 ≤ 1, die andere mit x1 ≥ 2.

  • P11 – Maximiere   G = x1 + x2
  • mit den Nebenbedingungen
    2x1 + x2 ≤ 4
    x1 + 2x2 ≤ 3
    x1 ≤ 1
    x1, x2 ≥ 0


  • P12 – Maximiere   G = x1 + x2
  • mit den Nebenbedingungen
    2x1 + x2 ≤ 4
    x1 + 2x2 ≤ 3
    x1 ≥ 2
    x1, x2 ≥ 0


Das Problem P11 hat die Lösung

  • G = 2
  • x1 = 1
  • x2 = 1

Da 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.

Dazu lösen wir Problem P12 und erhalten:

  • G = 2
  • x1 = 2
  • x2 = 0

Auch 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 zwei 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

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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 …   Deutsch Wikipedia

  • 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 …   Deutsch Wikipedia

  • Branch and bound — (BB) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of… …   Wikipedia

  • Branch and bound — Séparation et évaluation Un algorithme par séparation et évaluation, également appelé selon le terme anglo saxon branch and bound, est une méthode générique de résolution de problèmes d optimisation, et plus particulièrement d optimisation… …   Wikipédia en Français

  • Branch-and-Bound-Verfahren — Branch and Bound Verfahren,   Entscheidungsbaumverfahren …   Universal-Lexikon

  • Branch-and-bound-Verfahren —   [ brɑːntʃənd baʊnd ; englisch], Operationsresearch: Entscheidungsbaumverfahren …   Universal-Lexikon

  • Branch-and-Bound-Verfahren — 1. Begriff: Verfahren des ⇡ Operations Research, bei dem ein zu lösendes kombinatorisches Optimierungsproblem (endliche Anzahl unabhängiger Variablen mit diskretem Wertevorrat) keiner effektiven analytischen Behandlung zugänglich ist oder… …   Lexikon der Economics

  • Branch and Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… …   Deutsch Wikipedia

  • Branch-and-Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… …   Deutsch Wikipedia

  • Branch and cut — (sometimes written as branch and cut ) is a method of combinatorial optimization for solving integer linear programs, that is, linear programming problems where some or all the unknowns are restricted to integer values. The method is a hybrid of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”