Branch and Bound: Verzweigen und Beschränken für exakte Optimierung

Branch and Bound (deutsch: Verzweigen und Beschränken) ist ein systematisches, exaktes Suchverfahren für kombinatorische Optimierungsprobleme. Es zerlegt das Problem in kleinere Teilprobleme (Verzweigen) und schneidet hoffnungslose Äste mithilfe von Schranken ab (Beschränken). Am Ende steht ein beweisbar optimales Ergebnis — mit Optimalitätsnachweis, nicht nur einer guten Näherung.

Die zwei Grundideen

  • Verzweigen (Branching): Ein Teilproblem wird in Kinder zerlegt, indem eine Entscheidung fixiert wird — etwa „Artikel kommt in den Rucksack (x = 1)“ und „Artikel bleibt draußen (x = 0)“. So entsteht ein Entscheidungsbaum.
  • Beschränken (Bounding): Für jedes Kind wird eine Schranke berechnet. Kann die Schranke die aktuell beste bekannte Lösung, den Incumbent, nicht mehr übertreffen, wird der gesamte Teilbaum abgeschnitten (pruned).
  • Bei Minimierungsproblemen braucht man untere Schranken, bei Maximierungsproblemen obere — der Incumbent liefert jeweils die Gegenschranke.

Ablauf im Überblick

incumbent = gute Startlösung (z. B. per Greedy oder Heuristik)
offen = { Wurzelproblem }
while offen nicht leer:
    wähle Teilproblem P aus offen   # z. B. Tiefensuche oder beste Schranke
    verzweige P in Kinder           # Entscheidung fixieren (x = 0 und x = 1)
    for jedes Kind K:
        schranke = berechneSchranke(K)   # z. B. LP-Relaxation
        if schranke nicht besser als incumbent:
            schneide K ab
        elif K ist vollständige, zulässige Lösung:
            aktualisiere incumbent
        else:
            füge K zu offen hinzu

Schranken — das Herzstück

Eine Schranke entsteht meist über eine Relaxation: Das schwere Problem wird vereinfacht, und die optimale Lösung der Vereinfachung grenzt das Original ein. Das bekannteste Beispiel ist die LP-Relaxation: In der ganzzahligen Optimierung lässt man die Ganzzahligkeit los, sodass die lineare Optimierung schnell eine untere Schranke liefert. Beim Rucksackproblem erlaubt die klassische Relaxation, das letzte Teil anteilig einzupacken — die daraus resultierende obere Schranke ist das Standard-Schulbeispiel. Mit einem Greedy-Algorithmus oder einer Heuristik gewonnene Startlösungen verbessern den Incumbent und machen das Abschneiden früher wirksam.

Suchstrategien

  • Tiefensuche: wenig Speicher, schnell zu einer ersten vollständigen Lösung; eng verwandt mit Backtracking.
  • Best-First: immer der Knoten mit der vielversprechendsten Schranke zuerst — oft deutlich weniger bearbeitete Knoten, dafür mehr Speicher.
  • Breitensuche: vollständig, aber speicherintensiv; in der Praxis selten.

Eigenschaften und Grenzen

  • Exakt: Branch and Bound findet das Optimum und beweist es — kein Kandidat geht durch die Abschneideregeln verloren.
  • Worst Case exponentiell: Bei NP-vollständigen Problemen kann der Baum exponentiell wachsen; in der Praxis ist das Verfahren dennoch oft sehr effizient.
  • Abgrenzung zu Backtracking: Backtracking prüft nur Zulässigkeit (Constraints), Branch and Bound nutzt zusätzlich Zielfunktionsschranken zum Abschneiden.
  • Abgrenzung zu Approximationsalgorithmen und Heuristiken: Diese liefern schnell gute, aber nicht garantiert optimale Lösungen — Branch and Bound liefert die beweisbar optimale Lösung, braucht dafür aber Zeit.

Erweiterungen

  • Branch-and-Cut: Zusätzlich werden pro Knoten Schnittebenen (Cutting Planes) hinzugefügt, um die Schranken zu verschärfen.
  • Branch-and-Price: Spaltengenerierung für sehr große Modelle.
  • Industrielle ILP-Löser wie CPLEX, Gurobi oder SCIP kombinieren einen Branch-and-Bound-Kern mit Schnittebenen, Heuristiken und Preprocessing.

Anwendungen

Wer schnelle gute Startwerte braucht, kombiniert Branch and Bound mit dynamischer Programmierung oder Heuristiken — die Schrankenqualität entscheidet über die Größe des Suchbaums.