Branch-and-Bound-Verfahren

From Systems analysis Wiki
Jump to navigation Jump to search

Branch-and-Bound-Verfahren (englisch Branch and Bound, abgekürzt B&B oder BnB) ist ein allgemeines Paradigma für den Entwurf exakter Algorithmen zur Lösung von Problemen der diskreten und kombinatorischen Optimierung, insbesondere für NP-schwere Probleme[1]. Das Verfahren stellt eine Strategie der gesteuerten Suche dar, bei der die gesamte Menge zulässiger Lösungen sukzessive in Teilmengen aufgeteilt wird (Verzweigung), und für jede dieser Teilmengen Schranken (Grenzen) für den Wert der Zielfunktion berechnet werden. Diese Schranken ermöglichen es, jene Teilmengen zu verwerfen (abzuschneiden), die garantiert keine optimalen Lösungen enthalten, was den Suchraum erheblich reduziert[2].

Das Verfahren wurde erstmals 1960 von A. H. Land und A. G. Doig zur Lösung von Problemen der ganzzahligen Programmierung vorgeschlagen[3]. Seitdem hat es sich zu einem der fundamentalsten Ansätze im Operations Research und in der Informatik entwickelt. Ein Hauptmerkmal des Verfahrens ist seine Flexibilität: Es handelt sich nicht um einen spezifischen Algorithmus, sondern um ein übergeordnetes strategisches Schema (Framework), das an die Struktur des zu lösenden Problems angepasst werden kann.

Schlüsselkomponenten des Verfahrens

Das Verfahren basiert auf drei fundamentalen Operationen, die auf Teilmengen des Lösungsraums angewendet werden, welche als Suchbaum organisiert sind.

  • Verzweigung (englisch Branching) — ist der Prozess der rekursiven Aufteilung der aktuellen Menge zulässiger Lösungen Si in mehrere kleinere, in der Regel disjunkte Teilmengen Si1,Si2,…,Sik. Jede solche Teilmenge entspricht einem neuen Teilproblem und wird als Kindknoten im Suchbaum dargestellt. Beispielsweise wird bei Problemen der ganzzahligen Programmierung die Verzweigung oft anhand einer Variable durchgeführt, die in der Lösung der LP-Relaxation einen nicht-ganzzahligen Wert hat.
  • Bestimmung der Schranken (englisch Bounding) — für jeden Knoten des Suchbaums (d. h. für jedes Teilproblem) wird eine Schranke für den Wert der Zielfunktion berechnet. Bei einem Minimierungsproblem ist dies eine untere Schranke (lower bound), die eine garantierte untere Grenze für jede Lösung in dieser Teilmenge darstellt. Meistens wird diese Schranke durch die Lösung einer Relaxation des ursprünglichen Teilproblems ermittelt – einer vereinfachten Version, in der einige komplexe Nebenbedingungen (z. B. Ganzzahligkeit) vorübergehend ignoriert werden. Die gebräuchlichste ist die LP-Relaxation.
  • Abschneiden (englisch Pruning) — ist der Prozess, bei dem Knoten (und die ihnen entsprechenden vollständigen Teilbäume) aus der weiteren Betrachtung ausgeschlossen werden, wenn sie garantiert keine optimale Lösung enthalten können. Ein Knoten wird in einem der folgenden Fälle abgeschnitten:
  1. Abschneiden durch Schrankenvergleich: Die untere Schranke für den aktuellen Knoten ist nicht besser (d. h. bei einem Minimierungsproblem größer oder gleich) als der Wert der bisher besten gefundenen zulässigen Lösung, die als Incumbent bezeichnet wird.
  2. Abschneiden durch Zulässigkeit: Die Lösung der Relaxation eines Knotens ist für das ursprüngliche Problem zulässig (z. B. sind alle Variablen ganzzahlig). Diese Lösung wird mit dem aktuellen Incumbent verglichen, und wenn sie besser ist, wird der Incumbent aktualisiert. Eine weitere Verzweigung von diesem Knoten aus ist nicht erforderlich.
  3. Abschneiden durch Unlösbarkeit: Das dem Knoten entsprechende Teilproblem hat keine zulässigen Lösungen.

Allgemeiner Algorithmus

Ein verallgemeinerter Algorithmus des Branch-and-Bound-Verfahrens für ein Minimierungsproblem lässt sich durch die folgenden Schritte beschreiben:

  1. Initialisierung: Eine erste zulässige Lösung finden (z. B. mithilfe einer Heuristik) und deren Wert als anfängliche obere Schranke (Incumbent) U festlegen. Eine Warteschlange Q mit aktiven Knoten erstellen, die den Wurzelknoten (das ursprüngliche Problem) enthält.
  2. Hauptschleife: Solange die Warteschlange Q nicht leer ist:
    • Einen Knoten aus Q gemäß einer Suchstrategie auswählen (z. B. Tiefensuche oder Best-First-Suche).
    • Die Relaxation für diesen Knoten lösen, um eine untere Schranke L zu erhalten.
    • Den Knoten abschneiden, falls L≥U.
    • Wenn die Lösung der Relaxation für das ursprüngliche Problem zulässig ist, den Incumbent aktualisieren: U←L.
    • Wenn der Knoten nicht abgeschnitten wurde und die Lösung nicht zulässig ist, eine Verzweigung durchführen, indem der Knoten in Kindknoten aufgeteilt wird und diese zur Warteschlange Q hinzugefügt werden.
  3. Terminierung: Wenn die Warteschlange Q leer ist, endet der Algorithmus. Die gefundene Lösung, die dem Incumbent U entspricht, ist global optimal.

Schlüsseleigenschaften und Theoreme

  • Korrektheit und Konvergenz: Der Algorithmus findet garantiert eine global optimale Lösung in einer endlichen Anzahl von Schritten, sofern die Menge der zulässigen Lösungen endlich ist und das Verzweigungsverfahren konvergent ist (d. h., die Teilmengen bei rekursiver Aufteilung gegen einzelne Punkte konvergieren)[4].
  • Suchstrategie: Die Effizienz des Algorithmus hängt stark von der Strategie zur Auswahl des nächsten zu verzweigenden Knotens ab (z. B. Tiefensuche, Breitensuche, Best-First-Suche) sowie von der Wahl der Verzweigungsvariable. Moderne Löser verwenden oft hybride Strategien[5].

Beispiele

  • Problem der ganzzahligen Programmierung: Eine klassische Anwendung des Verfahrens. Als Relaxation wird die lineare Programmierung verwendet. Die Verzweigung erfolgt anhand einer nicht-ganzzahligen Variable xj, wodurch zwei Teilprobleme mit den zusätzlichen Nebenbedingungen xj≤⌊xj∗⌋ und xj≥⌈xj∗⌉ entstehen.
  • Problem des Handlungsreisenden: Der Lösungsraum besteht aus allen möglichen Hamiltonkreisen in einem Graphen. Die Verzweigung kann über Kanten erfolgen (eine Kante in die Route aufnehmen oder ausschließen). Als untere Schranken können Lösungen einfacherer Probleme dienen, wie das Zuordnungsproblem oder die Erstellung eines minimalen Spannbaums[6].

Verwandte Konzepte und Anwendungen

  • Branch-and-Cut-Verfahren (Branch-and-Cut): Ein hybrides Verfahren, das B&B mit der Schnittebenenmethode kombiniert. An jedem Knoten des Suchbaums werden zusätzlich zur Lösung der Relaxation weitere Ungleichungen (Schnitte) generiert, die die untere Schranke verschärfen, was zu einem effizienteren Abschneiden von Zweigen führt.
  • Backtracking (Backtracking): Das Branch-and-Bound-Verfahren kann als eine Verallgemeinerung dieses Algorithmus für Optimierungsprobleme betrachtet werden.
  • Alpha-Beta-Suche: Eine konzeptionelle Analogie, die in Spielbäumen verwendet wird, um nachweislich unterlegene Zweige abzuschneiden.

Einzelnachweise

  1. ↑ Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
  2. ↑ Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
  4. ↑ Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
  5. ↑ Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
  6. ↑ Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf
Retrieved from "https://systems-analysis.info/int/index.php?title=Branch-and-Bound-Verfahren&oldid=807"