Branch and Bound
- Eingeführt von
- Ailsa Land & Alison Doig
- Jahr
- 1960
- Typ
- Exact combinatorial optimization algorithm
- Familie
- Mathematical programming
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Branch and Bound ist ein systematischer exakter Algorithmus für kombinatorische und ganzzahlige Optimierungsprobleme, der 1960 von Ailsa Land und Alison Doig eingeführt wurde.
Er organisiert den Suchraum als Baum von Teilproblemen, nutzt aus Relaxationen abgeleitete obere Schranken, um Äste zu beschneiden, die die beste bekannte Lösung nicht verbessern können, und garantiert das Auffinden einer global optimalen ganzzahligen Lösung. Er ist das Rückgrat moderner Mixed-Integer-Programming-Solver, die in der Operations Research, Logistik, Zeitplanung und im Ingenieurwesen eingesetzt werden.
Die Intuition hinter der Methode
Stellen Sie sich vor, Sie suchen nach dem wertvollsten Gegenstand, der in einem riesigen Labyrinth von Räumen versteckt ist. Anstatt jeden Raum zu überprüfen, schätzen Sie den maximal möglichen Wert, der von jedem Korridor aus erreichbar ist, bevor Sie ihn betreten. Wenn diese Obergrenze niedriger ist als der beste Gegenstand, den Sie bereits besitzen, überspringen Sie den gesamten Korridor, ohne hineinzuschauen. Branch and Bound funktioniert auf die gleiche Weise: Es zerlegt das Problem in kleinere Teile, berechnet optimistische obere Schranken für jeden Teil und verwirft sofort jeden Teil, der nachweislich die aktuelle beste Lösung nicht übertreffen kann.
Geschichte
Land und Doig veröffentlichten 1960 die grundlegende Branch-and-Bound-Arbeit in Econometrica und beschrieben sie als automatische Methode für die diskrete Programmierung. Little et al. (1963) wandten die Technik auf das Problem des Handlungsreisenden an und festigten damit ihre Rolle in der kombinatorischen Optimierung. Dakin (1965) führte die LP-Relaxationsverzweigung ein, die heute am häufigsten verwendete Form. In den folgenden Jahrzehnten wurden Schnittebenen (Branch-and-Cut) und Spaltengenerierung (Branch-and-Price) integriert, wodurch Branch and Bound zum Motor aller großen kommerziellen Integer-Programming-Solver wurde.
Wann wird sie eingesetzt?
Verwenden Sie Branch and Bound, wenn Sie die nachweislich optimale Lösung für ein gemischt-ganzzahliges oder rein ganzzahliges lineares Programm finden müssen und keine annähernde Antwort akzeptieren können. Es setzt voraus, dass das Problem mit linearen (oder konvexen) Relaxationen formuliert werden kann, die nützliche Schranken liefern. Es ist weniger geeignet für sehr große Instanzen, bei denen der Enumerationsbaum explodiert, für nichtlineare ganzzahlige Programme ohne enge Relaxationen oder für Echtzeitszenarien, in denen die Rechenzeit streng begrenzt ist. In solchen Fällen können Heuristiken oder Metaheuristiken bevorzugt werden.
Grenzen und Hinweise
- Die Worst-Case-Komplexität ist exponentiell; bei schlecht strukturierten Instanzen kann der Baum unerschwinglich groß werden.
- Die Leistung ist stark abhängig von der Wahl der Verzweigungsvariablen und der Knotenauswahlstrategie.
- Erfordert eine handhabbare Relaxation, die aussagekräftige obere Schranken liefert; schwache Schranken führen zu minimalem Beschneiden.
- Der Speicherbedarf kann erheblich sein, wenn viele offene Knoten gleichzeitig gespeichert werden müssen.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Garantiert globale Optimalität für ganzzahlige und kombinatorische Programme.
- Reduziert die Suche durch schrankenbasiertes Beschneiden drastisch – oft wird nur ein winziger Bruchteil des vollständigen Enumerationsbaums untersucht.
- Flexibel: Kann Schnittebenen (Branch-and-Cut) oder heuristische Schranken (Branch-and-Price) für weitere Effizienz integrieren.
- Weit verbreitet in ausgereiften kommerziellen Solvern (CPLEX, Gurobi) und Open-Source-Tools (GLPK, CBC) implementiert.
Anwendungen
- Flugpersonalplanung und Flottenzuweisung in der Operations Research.
- Design von Lieferkettennetzwerken und Standortprobleme.
- VLSI-Schaltkreislayout und Registerzuweisung in der Computertechnik.
- Proteinstrukturvorhersage und Genomassemblierung in der Computerbiologie.
- Finanzportfoliooptimierung mit Kardinalitätsbeschränkungen.
So funktioniert es
So funktioniert es
Der Algorithmus beginnt mit der Lösung einer relaxierten Version des Problems – typischerweise der LP-Relaxation –, die die Ganzzahligkeitsbedingungen ignoriert. Diese Relaxation liefert eine obere Schranke für den wahren optimalen Wert, da jede zulässige ganzzahlige Lösung auch in der Relaxation zulässig ist. Wenn die relaxierte Lösung ganzzahlig ist, ist das Problem sofort gelöst.
Formel
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}Wenn die relaxierte Lösung eine gebrochene Variable enthält, partitioniert der Algorithmus den zulässigen Bereich, indem er komplementäre Bedingungen hinzufügt, die die Variable entweder auf ihren Boden- oder ihren Deckenwert zwingen. Jede Partition erzeugt einen neuen Kindknoten im Suchbaum, wodurch ein Teilproblem effektiv in zwei kleinere Teilprobleme mit engeren Domänen aufgeteilt wird.
Formel
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilJeder aktive Knoten erhält seine eigene LP-Relaxationsschranke. Ein Knoten, dessen Schranke die bisher beste gefundene ganzzahlige Lösung – den sogenannten Inhaber (incumbent) – nicht übersteigt, kann keine bessere Lösung enthalten und wird daher beschnitten. Enge Schranken sind entscheidend: Je enger die Schranke, desto weniger Knoten müssen untersucht werden.
Formel
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}Ein Knoten wird unter drei Bedingungen geschlossen (fathomed): seine Relaxation ist unzulässig, seine Schranke ist nicht besser als die des Inhabers, oder seine relaxierte Lösung ist bereits ganzzahlig-zulässig. Im letzteren Fall wird der Inhaber aktualisiert, wenn die neue Lösung ihn verbessert. Der Algorithmus terminiert, wenn alle Knoten geschlossen sind; zu diesem Zeitpunkt ist der Inhaber das globale Optimum.
Formel
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)Häufige Fallstricke
- Eine schlechte Wahl der Verzweigungsvariablen (z. B. immer die erste gebrochene Variable) führt oft zu tiefen, unausgewogenen Bäumen und langsamer Konvergenz.
- Das Ignorieren gültiger Ungleichungen (Schnittebenen) bedeutet, die Möglichkeit zu verpassen, Relaxationsschranken erheblich zu verschärfen.
- Ein vorzeitiger Abbruch mit einer Suboptimalitätslücke, die nicht als solche gemeldet wird, kann Praktiker dazu verleiten, eine nahezu optimale Lösung als exakt zu behandeln.
- Die Anwendung von Branch and Bound auf nichtlineare oder nicht-konvexe Relaxationen ohne spezialisierte Konvexifizierung kann zu ungültigen Schranken und falschen Ergebnissen führen.
Häufig gestellte Fragen
Wie unterscheidet sich Branch and Bound von der vollständigen Enumeration?
Die vollständige Enumeration bewertet jede zulässige ganzzahlige Lösung explizit, was für große Probleme rechnerisch undurchführbar ist. Branch and Bound vermeidet dies, indem es an jedem Knoten des Suchbaums relaxationsbasierte obere Schranken berechnet und ganze Teilbäume beschneidet, wenn die Schranke die bereits gefundene beste Lösung nicht übertreffen kann. In der Praxis wird nur ein kleiner Bruchteil des Baumes jemals untersucht.
Welche Rolle spielt die LP-Relaxation bei Branch and Bound?
Die LP-Relaxation lässt Ganzzahligkeitsbedingungen fallen, wodurch das Problem in polynomialer Zeit mittels Simplex- oder Innere-Punkte-Methode lösbar wird. Ihr Optimalwert dient als obere Schranke für das entsprechende ganzzahlige Teilproblem. Wenn diese Schranke eng ist – nahe am wahren ganzzahligen Optimum –, müssen weniger Äste untersucht werden. Engere Relaxationen, oft durch Hinzufügen gültiger Ungleichungen erreicht, beschleunigen den Gesamtalgorithmus dramatisch.
Wann sollte ich Branch and Bound gegenüber einer Metaheuristik wie genetischen Algorithmen verwenden?
Wählen Sie Branch and Bound, wenn Sie ein Optimalitätszertifikat benötigen und die Rechenzeit aufbringen können. Es ist ideal für mittelgroße Probleme mit gut strukturierten LP-Relaxationen. Metaheuristiken sind vorzuziehen, wenn das Problem extrem groß ist, eine nützliche Relaxation fehlt oder innerhalb eines engen Zeitbudgets gelöst werden muss, wobei eine nahezu optimale Lösung akzeptabel ist. Viele Praktiker kombinieren beides: Branch and Bound mit einer Toleranz für die vorzeitige Beendigung der Lücke.
Verwandte Methoden
Quellen
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
DOI-Referenz öffnenKopiert.