Eine allgemeine Optimierungstechnik, die den Suchraum systematisch erkundet, indem sie in Teilprobleme verzweigt und berechnete Schranken für beste mögliche Lösungen in jedem Zweig verwendet, um Regionen zu beschneiden, die kein optimales Ergebnis enthalten können.

Prinzip

Kombiniere Verzweigung (Zerlegung des Suchraums) mit Bounding (Berechnung optimistischer/pessimistischer Grenzen) und einer Suchstrategie, um Zweige zu eliminieren, deren Schranken zeigen, dass sie das aktuelle Beste nicht übertreffen können.

Demonstration

Lösen eines ganzzahligen linearen Programms durch Verzweigung an fractionalen Variablen: Jeder Knoten steht für ein Teilproblem mit zusätzlichen Ganzzahligkeitsbedingungen, und eine Relaxation (lineares Programm) liefert eine obere Schranke; Knoten, deren Relaxations-Schranke schlechter ist als der Inzumbent, werden geschnitten. Beim TSP verästelt man über Subtour-Auswahlen und nutzt untere Schranken zum frühen Beschneiden unversprechender Zweige.

Fehlanwendung

Verwendung schlechter oder loser Schranken, schlechte Verzweigungsentscheidungen oder ungeeignete Knotenordnung, die zu kaum vorhandener Beschneidung führen, sodass der Algorithmus in eine nahezu exhaustive Suche übergeht und Rechenleistung verschwendet.

Konsequenz

Sind Schranken und Heuristiken effektiv, kann die Methode den erkundeten Raum erheblich reduzieren und bei Abschluss die Optimalität garantieren; sie liefert außerdem gültige Schranken und beste bisher gefundene Lösungen während der Laufzeit.

Umkehrung

Unbeschränkte exhaustive Enumeration (Brute-Force-Suche), die alle Kandidaten ohne Schranken prüft, oder rein heuristische Suche, die nie Optimalität garantiert.

Abgrenzung

Hauptsächlich geeignet für diskrete und kombinatorische Optimierungsprobleme, bei denen Schranken berechnet werden können (z. B. Ganzzahlige Programmierung, kombinatorische Terminplanung). Weniger direkt anwendbar auf Probleme ohne effizient berechenbare Relaxationen oder auf kontinuierliche Probleme ohne Diskretisierung/Relaxation.

Semantische Spannung

Spannung zwischen der Strenge der Schranken und den Kosten ihrer Berechnung: Strengere Schranken beschneiden mehr, können aber teuer zu berechnen sein; im Gegensatz zu Cut-Plane- oder heuristischen Methoden, die die Schranken anders verbessern oder die Optimalität gegen Geschwindigkeit eintauschen.

Synthese

Branch-and-Bound organisiert eine vollständige Suche durch Aufteilung in Teilprobleme und Verwendung von Schranken zum Verwerfen unprominenter Regionen; die praktische Leistung hängt von der Qualität der Schranken, Verzweigungsregeln und Knotenauswahlheuristiken ab und liefert exakte Lösungen bei vollständiger Ausführung sowie nützliche Inzumbents vorher.