Branch and Bound verständlich erklärt

Wer einen Lieferwagen aus vielen Paketen beladen will, kann nicht jede Auswahl einzeln prüfen: Mit jedem weiteren Paket verdoppelt sich die Zahl der Möglichkeiten. Branch & Bound findet trotzdem die bewiesen beste Auswahl, weil eine Schranke ganze Gruppen aussichtsloser Möglichkeiten auf einmal streicht. Der Beweis gilt allerdings nur, solange die Suche zu Ende läuft; bei sehr großen Aufgaben kann das scheitern. Diese Seite erklärt das zuerst ohne Formeln und danach für Fachleute mit Modell, Formeln, Befunden und Grenzen.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Lieferwagen, viele Pakete, jedes Mal ja oder nein

Ein Lieferwagen darf nur ein bestimmtes Gewicht laden. Vor ihm liegen Pakete, jedes mit eigenem Gewicht und eigenem Wert. Gesucht ist die Auswahl mit dem größten Gesamtwert, die das Gewichtslimit einhält. Ein Paket kommt ganz mit oder bleibt ganz zurück. Dieses Standardproblem heißt Rucksackproblem; ob Rucksack, Koffer oder Lieferwagen, die Aufgabe ist dieselbe.

Man kann jede Auswahl als Weg durch lauter Entscheidungen beschreiben. Beim ersten Paket gibt es zwei Wege: mitnehmen oder nicht. Bei jedem weiteren Paket teilt sich jeder bisherige Weg noch einmal in zwei. So entsteht ein Baum, der sich nach unten immer weiter verzweigt, der Suchbaum. Jede Gabelung darin, also jeder Zwischenstand der Entscheidungen, heißt Knoten. Mit jedem zusätzlichen Paket verdoppelt sich die Zahl der Wege. Bald sind es zu viele, um sie alle einzeln zu prüfen.

Der Trick: ganze Äste auf einmal streichen

Branch and Bound geht den Baum Entscheidung für Entscheidung durch. „Branch“ heißt verzweigen: Bei jedem Paket werden beide Möglichkeiten verfolgt. Nach jeder Teil-Entscheidung stellt sich das Verfahren eine Frage: Selbst wenn ich ab hier alles Übrige so günstig dazunehme, wie es nur geht, kann das noch besser werden als die beste Auswahl, die ich schon kenne?

Lautet die Antwort Nein, wird der ganze Ast abgebrochen. Darunter liegen womöglich sehr viele Wege, und keiner davon wird einzeln angesehen. Die optimistische Obergrenze heißt Schranke (englisch Bound), das Abschneiden Stutzen (englisch Pruning, wie beim Baumschnitt).

Ein Alltagsbild: Ein Außendienstler plant seine Tagesroute und kennt schon eine, die Aufträge in einer bestimmten Höhe einbringt. An einer Gabelung rechnet er aus: Selbst wenn ich ab hier jeden weiteren Auftrag ohne Zeitverlust bekäme, käme ich nicht über den Wert meiner bekannten Route. Dann lohnt es sich nicht, hinter dieser Gabelung weiterzuplanen, denn im günstigsten Fall wird es nicht besser.

Warum daraus ein Beweis wird

Entscheidend ist, dass die Schranke ehrlich optimistisch ist. Sie darf nie niedriger sein als das, was ab dort wirklich erreichbar ist. Dann wird nie ein Ast gestrichen, in dem noch etwas Besseres steckt. Am Ende ist jeder Weg entweder zu Ende gegangen oder von einer solchen Schranke ausgeschlossen. Damit ist nicht nur eine gute Auswahl gefunden, sondern bewiesen, dass keine bessere existiert.

Wie kommt man an so eine Obergrenze? Beim Rechnen erlaubt man sich, Pakete auch in Bruchteilen zu laden, und füllt den Wagen zuerst mit den Paketen, die pro Gewichtseinheit am meisten Wert bringen. Das ist leicht auszurechnen und liegt nie unter dem Wert der besten echten Auswahl, denn die Einschränkung auf ganze Pakete fällt weg.

Der Beweis gilt allerdings nur, solange die Suche wirklich zu Ende läuft. Bei sehr vielen Paketen oder einer lockeren Schranke kann der Baum trotz Streichen so groß werden, dass die Suche nicht fertig wird. Dann bleibt nur die beste bisher gefundene Auswahl, ohne Beweis, dass keine bessere existiert.

Was eine Schranke gut macht

Nicht jede ehrliche Schranke streicht gleich viel. Eine sehr lockere Schranke addiert einfach alle noch offenen Werte auf und ignoriert das Gewichtslimit. Sie ist ehrlich, denn mehr als diese Summe geht nie, aber sie ist so großzügig, dass sie nur selten einen Ast streichen kann. Die Schranke mit Bruchteilen liegt näher an dem, was wirklich erreichbar ist, und streicht früher. Das bewiesene Ergebnis ist in beiden Fällen dasselbe, nur die Zahl der besuchten Knoten unterscheidet sich. Bei den größeren Beispielen der Demo ist dieser Unterschied groß; die Zahlen stehen im Fachteil.

Auch die Reihenfolge hilft. In der Demo wird bei jedem Paket zuerst „mitnehmen“ verfolgt, weil man so tendenziell früh eine gute Auswahl findet. Je besser die beste bekannte Auswahl, desto höher liegt die Latte, die eine Schranke noch überspringen muss, und desto mehr Äste fallen weg.

Was man mitnimmt: Hat ein Problem zu viele Möglichkeiten, um sie alle zu prüfen, aber lässt sich eine ehrliche und scharfe Obergrenze berechnen, kann man trotzdem beweisen, dass nichts Besseres existiert, sofern die Suche zu Ende läuft. In der Demo hängt bei gleicher Aufgabe die Zahl der besuchten Knoten an der gewählten Schranke.

Wie ernst ist das Modell zu nehmen?

Die Demo arbeitet mit zufällig erzeugten Paketen, deren Gewichte und Werte erfunden sind. Es ist kein echtes Lieferproblem. Das Rucksackproblem dient nur als greifbares Beispiel, weil sich die Schranke dabei einfach berechnen und erklären lässt. Bei anderen Problemen muss man eine brauchbare Schranke erst finden, und ob sie scharf genug ist, entscheidet, ob die Suche in vernünftiger Zeit fertig wird. Deshalb bricht die Demo eine Suche ab, die zu viele Knoten besucht, und kennzeichnet das offen.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Problem: 0/1-Rucksackproblem mit \(n\) Paketen, Gewichten \(w_i\), Werten \(v_i\) und Limit \(W\). Es ist NP-schwer (schwach NP-vollständig) und per dynamischer Programmierung pseudopolynomial lösbar. Die Demo zeigt bewusst Branch & Bound statt DP, weil sich der Suchbaum direkt visualisieren lässt und das Prinzip auch auf Probleme ohne pseudopolynomiale DP-Lösung übertragbar ist.
• Verfahren: Tiefensuche mit einem Paket je Ebene in Wert/Gewicht-Reihenfolge, „aufgenommen“ vor „ausgelassen“. Ein Ast wird gestutzt, wenn das Gewichtslimit schon überschritten ist oder die Schranke nicht besser ist als der bisher beste Fund. Die Knoten-IDs folgen der Besuchsreihenfolge, ein Animationsschritt entspricht genau einem besuchten Knoten.
• Instanzen: zufällig erzeugt, gesteuert über Anzahl der Pakete (Baumgröße von \(2^n\) Ja/Nein-Kombinationen), Gewichtslimit als Anteil der Gesamtmenge, Korrelation von Wert und Gewicht und Zufalls-Seed. Korrelation 0: Wert unabhängig vom Gewicht. Korrelation 1: Wert gleich Gewicht plus Rauschen (±8).
• Sicherheitsgrenzen: Die Suche bricht bei MAX_NODES_EXPLORED (200.000) Knoten ab und kennzeichnet das Ergebnis als „abgebrochen, beste bislang gefundene Lösung“. Die Grafik zeigt höchstens MAX_NODES_RENDERED (800) Knoten; die Kennzahlen bleiben davon unberührt.

Die Formeln

Das Rucksackproblem: Wähle eine Teilmenge mit größtem Gesamtwert, ohne das Limit \(W\) zu überschreiten.

\[\max \sum_{i=1}^n v_i x_i \quad \text{unter} \quad \sum_{i=1}^n w_i x_i \le W, \quad x_i \in \{0,1\}.\]

Die starke Schranke ist die LP-Relaxierung. An einem Knoten mit Teilentscheidung bis Index \(k\), verbleibendem Limit \(W'\) und bereits sicherem Wert \(v'\) löst sie dieselbe Zielfunktion mit Bruchteilen \(x_i\) zwischen null und eins für die noch unentschiedenen Pakete in Wert/Gewicht-Reihenfolge (Dantzig-Schranke). Die fraktionale Lösung ist mindestens so gut wie jede ganzzahlige Vervollständigung, weil sie eine Bedingung, die Ganzzahligkeit, fallen lässt. Deshalb ist Stutzen mit ihr sicher.

\[\text{Bound}_{\text{stark}} = v' + \max\Big\{\textstyle\sum_{i>k} v_i x_i : \sum_{i>k} w_i x_i \le W',\; x_i \in [0,1]\Big\}\]

Die schwache Vergleichsschranke ignoriert \(W'\) komplett:

\[\text{Bound}_{\text{schwach}} = v' + \sum_{i>k} v_i\]

Es gilt \(\text{Bound}_{\text{schwach}} \ge \text{Bound}_{\text{stark}}\). Beide Schranken sind gültig, unterschätzen also nie den erreichbaren Wert, sie unterscheiden sich nur in der Schärfe. Ein Knoten wird gestutzt, wenn seine Schranke den bisher besten Fund nicht übertrifft.

Befunde

Alle Zahlen stammen aus der README und den Texten der Demo. Die Faktoren zählen besuchte Knoten (Faktor = Knoten mit schwacher Schranke geteilt durch Knoten mit starker Schranke), keine Rechenzeit.

Frage	Befund
Wie viel mehr Knoten braucht die schwache Schranke?	Über 40 Seeds (20 Pakete, Gewichtslimit 50 %) liegt der Faktor im Median bei etwa 240 für Korrelation 0 und bei etwa 640 für Korrelation 0,95.
Wie groß bleibt der Suchbaum mit starker Schranke?	Bei denselben 40 Seeds braucht die starke Schranke in beiden Fällen (Korrelation 0 und 0,95) im Median rund 90 Knoten.
Schwächt hohe Korrelation die starke Schranke?	In dieser Demo nicht: Der mediane Faktor ist bei Korrelation 0,95 sogar größer als bei Korrelation 0. Einzelne Seeds zeigen einen kleineren Vorteil, etwa Seed 3 mit Faktor 591 bei Korrelation 0 gegen 159 bei Korrelation 0,95.
Ist das Ergebnis exakt?	Der Optimalwert stimmt für kleine Zufallsinstanzen (n = 10, 30 Seeds, beide Schranken) mit vollständiger Enumeration überein. Bei einer von Hand gerechneten Instanz mit 4 Paketen ist das Optimum 7.
Sind die Schranken gültig?	Für zufällige Teillösungen wird durch Enumeration aller Vervollständigungen geprüft, dass keine der beiden Schranken den wahren maximal erreichbaren Wert unterschätzt.

Grenzen

• Ein Problem, eine Schranke: Das Rucksackproblem ist der einfachste Lehrfall, weil die LP-Schranke trivial zu berechnen ist. Die gemessenen Faktoren sagen nichts über andere Probleme, deren Schranken schwerer zu finden oder weniger scharf sind.
• Stichprobe: Die Mediane stammen aus 40 Seeds bei 20 Paketen und Gewichtslimit 50 %. Andere Größen und Limits sind in der README nicht ausgewertet, und der Median sagt über eine einzelne Instanz wenig (Seed 3 weicht deutlich ab).
• Korrelation: Die Instanzen entsprechen eher den „weakly correlated“-Instanzen aus Pisingers Katalog (2005) als den „strongly correlated“ (Wert = Gewicht + Konstante), die in der Literatur als schwer für Branch & Bound gelten. Der Befund, dass Korrelation die starke Schranke hier nicht schwächt, gilt nur für diese Art der Instanzerzeugung.
• Abbruch: Nach 200.000 Knoten liefert die Suche nur die beste bislang gefundene Lösung, ohne Optimalitätsbeweis. Die Baum-Grafik zeigt höchstens 800 Knoten.
• Verifikation: Branch & Bound ist hier selbst der exakte Löser, ein Vergleich mit einem zweiten Solver ist nicht vorgesehen. Die Enumeration als Gegenprobe reicht nur für kleine Instanzen (n = 10).
• Nicht enthalten: andere Suchreihenfolgen und Verzweigungsregeln, Schnittebenen, Dynamische Programmierung und Constraint Programming. Sie sind eigene Stücke der Linie.

Quellen

• Land, A. H., Doig, A. G. (1960): An automatic method of solving discrete programming problems. Econometrica 28(3), 497–520 (Ursprung von Branch & Bound).
• Dantzig, G. B. (1957): Discrete-variable extremum problems. Operations Research 5(2), 266–277 (Schranke aus der fraktionalen Lösung).
• Pisinger, D. (2005): Where are the hard knapsack problems? Computers & Operations Research 32(9), 2271–2284 (Katalog der Rucksack-Instanzen; in der README der Demo genannt).
• Quelltext und Tests der Demo: github.com/sebastian-hanisch/branch-bound-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Nur Pisinger (2005) steht in der README der Demo; die übrigen Angaben und alle Fundstellen sind nicht gegen die Originale geprüft.