Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Branch & Bound, exakte Lösung von IP-Problemen
Wie löst man ein NP-schweres Problem in der Praxis? Mit Branch & Bound, dem Standard-Algorithmus für ganzzahlige Programme. Klausurpflicht in 6/8 OR-Programmen.
Die Idee in einem Satz
Branch & Bound: Iteratives Aufteilen des Problems in Subprobleme (Branch) + Berechnen oberer Schranken durch LP-Relaxation (Bound) + Abschneiden hoffnungsloser Äste (Prune).
Der Algorithmus
Schritt 0, Initialisierung
- Löse LP-Relaxation des ursprünglichen IP.
- Wenn LP-Lösung ganzzahlig → fertig.
- Sonst: starte Suchbaum mit Wurzel = ursprüngliches IP.
- Setze beste bekannte ganzzahlige Lösung:
z_(LB) = -∞(bei max).
Schritt 1, Knoten-Auswahl
Wähle einen offenen Knoten aus dem Suchbaum (Strategie z.B. Best-First, Depth-First).
Schritt 2, LP-Relaxation lösen
Berechne LP-Optimum z_(LP)^* für den aktuellen Knoten.
Schritt 3, Pruning-Tests (Abschneide-Regeln)
3a. Pruning by Bound
Wenn z_(LP)^* ≤ z_(LB) (bei max):
→ Verwerfen. Selbst die LP-Lösung ist nicht besser als die beste bekannte ganzzahlige.
3b. Pruning by Infeasibility
Wenn LP unzulässig: → Verwerfen. Kein Subproblem hat eine Lösung.
3c. Pruning by Optimality
Wenn LP-Lösung bereits ganzzahlig:
→ Inkumbent updaten (z_(LB) ← z_(LP)^*), Knoten schließen.
Schritt 4, Branch (Verzweigung)
Wähle fraktionale Variable x_j^* = f (mit f nicht ganzzahlig).
Erstelle 2 Kind-Knoten:
- Linker Kind: Zusätzliche Restriktion
x_j ≤ lfloor f rfloor - Rechter Kind: Zusätzliche Restriktion
x_j ≥ lceil f rceil
Zurück zu Schritt 1.
Schritt 5, Terminierung
Wenn keine offenen Knoten mehr → fertig. z_(LB) ist das Optimum.
Beispiel: Detail-Durchlauf
Problem: max 3x₁ + 4x₂ s.t. 2x₁ + x₂ ≤ 9, x₁ + 2x₂ ≤ 8, x₁, x₂ ∈ ℤ₊
Root: LP-Lösung = (3.75, 2.25), z = 19.5. Nicht ganzzahlig → Branch auf x₁.
Linker Kind (x₁ ≤ 3): LP = (3, 2.5), z = 18.5. Nicht ganzzahlig → Branch auf x₂.
Knoten (x₁ ≤ 3, x₂ ≤ 2): LP = (3, 2), z = 17. Ganzzahlig! z_(LB) = 17.
Rechter Kind (x₁ ≥ 4): LP = (4, 1.6), z = 18.4. Nicht ganzzahlig → Branch auf x₂.
Knoten (x₁ ≥ 4, x₂ ≤ 1): LP = (4, 1), z = 17. Ganzzahlig, gleich Inkumbent.
Knoten (x₁ ≥ 4, x₂ ≥ 2): LP unzulässig (Restriktionen verletzt) → Prune.
Knoten (x₁ ≤ 3, x₂ ≥ 3): LP = (1.5, 3), z = 16.5. z < 17 → Prune by Bound.
Optimum: z* = 17 mit zwei Lösungen (3, 2) oder (4, 1).
Knoten-Auswahl-Strategien
| Strategie | Beschreibung | Trade-off |
|---|---|---|
| Best-First | Knoten mit höchster oberer Schranke (max) | Wenig Knoten, viel Speicher |
| Depth-First | Tiefe vor Breite | Wenig Speicher, evtl. viele Knoten |
| Best-First + Restart | Hybrid | Praxis-Standard |
Variable-Auswahl-Strategien
Welche fraktionale Variable für Branching wählen?
- Most Fractional:
x_jmitf_jnächst zu 0.5 - Strong Branching: Probiere mehrere Variablen, wähle beste
- Pseudo-Cost Branching: Lerne aus früheren Branches
Branch & Cut, die Pro-Variante
Branch & Cut kombiniert Branch & Bound mit Schnittebenen (Cutting Planes):
- Nach LP-Lösung: füge gültige Ungleichungen ein, die LP-Lösung abschneiden.
- Iterativ neue Schranken ohne zu branchen.
- Erst wenn keine Schnitte mehr → branch.
Berühmte Schnittebenen:
- Gomory-Cuts (Gomory 1958): allgemein einsetzbar
- Cover-Cuts für Knapsack-Probleme
- Clique-Cuts für Set-Packing
Moderne MIP-Solver (Gurobi, CPLEX) sind Branch-and-Cut + Heuristiken.
Vorteile + Limits
| Vorteil | Limit |
|---|---|
| EXAKTE Lösung garantiert | Worst-Case exponentielle Laufzeit |
| Pruning erspart viele Knoten | Bei großen Problemen unpraktikabel |
| Liefert obere/untere Schranken | Lösung kann lange dauern |
| Industrie-Standard | Speicher-intensiv |
Wann Branch & Bound vs. Heuristiken?
| Problemgröße | Empfehlung |
|---|---|
| < 100 Variablen | Branch & Bound (exakt) |
| 100–10.000 Variablen | Branch & Bound mit MIP-Solver |
| > 10.000 Variablen | Heuristiken (Greedy, Genetic, Lokale Suche) |
| Echtzeit-Anwendungen | Heuristiken (Approximation) |
Klausur-Faustregeln
1. LP-Relaxation gibt obere Schranke (bei max). Bei min ist es eine untere Schranke.
2. 3 Pruning-Regeln: Bound / Infeasibility / Integer.
3. Branch auf fraktionaler Variable: x_j ≤ lfloor f rfloor und x_j ≥ lceil f rceil.
4. Inkumbent ist die beste bekannte ganzzahlige Lösung. Wird bei jeder neuen Integer-Lösung aktualisiert.
5. Algorithmus terminiert immer (endlicher Suchbaum), aber Worst-Case exponentiell.
6. Branch & Cut = Branch & Bound + Schnittebenen. Praxis-Standard moderner Solver.
Häufige Stolpersteine
1. LP-Lösung als IP-Lösung interpretieren. Falsch. LP gibt nur Schranke, nicht zwingend zulässige IP-Lösung.
2. Pruning by Bound bei Gleichheit anwenden. z_(LP)^* = z_(LB): Knoten kann genauso gut pruning oder weiter explorieren. Konvention: prune.
3. Inkumbent bei min mit -∞ initialisieren. Falsch, bei min mit +∞ initialisieren. z_(LB) ist UNTERE Schranke bei max, OBERE bei min.
4. Branch auf ganzzahliger Variable. Sinnlos, nur fraktionale Variablen branchen.
5. Suchbaum-Größe ignorieren. Worst-Case 2ⁿ Knoten bei n binären Variablen. Bei großen Problemen Heuristiken erwägen.
6. Branch & Bound nur für IP. Branch & Bound ist allgemeines Schema, auch für MIP, TSP, Constraint Programming einsetzbar.
Interaktiv verstehen
Branch & Bound, Suchbaum interaktiv
Klick auf einen Knoten zeigt LP-Lösung, Pruning-Grund und Branch-Restriktion. Komplettes Beispiel-Problem durchgerechnet.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Lösen Sie das IP mit Branch & Bound" IMMER Suchbaum mit klarer Notation zeichnen: pro Knoten LP-Wert + Branching-Restriktion + Pruning-Grund vermerken. Inkumbent z_LB über den Baum mitführen. Zeige alle 3 Pruning-Regeln im Durchlauf, um maximale Punkte zu sichern.
Praxis-Übung
Branch & Bound, Praxis-Übung
6 Aufgaben zu Algorithmus, Pruning-Regeln und Strategien.
Klausurfragen mit Lösungen (6)
- F1.Was bedeutet 'Bound' in Branch & Bound?
Antwort: Obere/untere Schranke aus LP-Relaxation
Erklärung: Bound = Schranke aus LP-Relaxation. Bei max-IP gibt LP-Lösung eine OBERE Schranke (LP ist lockerer als IP, also LP-Wert ≥ IP-Wert). Bei min-IP eine UNTERE Schranke. Die Bound dient zum Pruning: wenn LP-Bound ≤ aktuelle beste ganzzahlige Lösung (bei max), kann der Ast verworfen werden.
- F2.Welche 3 Regeln führen zum Pruning eines Knotens?
Antwort: Bound, Infeasibility, Integer-Solution
Erklärung: 3 Pruning-Regeln: 1) Pruning by Bound (LP-Schranke schlechter als Inkumbent), 2) Pruning by Infeasibility (LP unzulässig), 3) Pruning by Optimality (LP-Lösung bereits ganzzahlig → Inkumbent aktualisieren + Knoten schließen). Diese 3 Regeln musst du in der Klausur kennen.
- F3.Ordne Strategie der Beschreibung zu.
Zuordnungen:
- Best-First Search → Knoten mit höchster Bound zuerst, wenig Knoten, viel Speicher
- Depth-First Search → Tiefe vor Breite, wenig Speicher, evtl. viele Knoten
- Most Fractional → Branche auf Variable mit f nahe 0.5
- Strong Branching → Probiere mehrere Variablen, wähle beste Bound-Verbesserung
Erklärung: Knoten-Auswahl-Strategien: Best-First (wenig Knoten, hoher Speicher) vs. Depth-First (wenig Speicher, evtl. viele Knoten). Variable-Auswahl: Most Fractional (einfach), Strong Branching (gründlich aber aufwendig), Pseudo-Cost Branching (lernend). Moderne Solver kombinieren mehrere Strategien.
Typ: Zuordnung
- F4.LP-Lösung gibt x_1 = 3.7. Welche zwei Subprobleme erzeugt das Branching?
Antwort: x_1 ≤ 3 und x_1 ≥ 4
Erklärung: Standard-Branching: bei fraktionaler Variable x_j = f mit f ∉ ℤ erstelle 2 Subprobleme: links x_j ≤ ⌊f⌋, rechts x_j ≥ ⌈f⌉. Hier: ⌊3.7⌋ = 3 und ⌈3.7⌉ = 4. Dadurch wird die LP-Lösung x_j = 3.7 ausgeschlossen. Wichtig: fixieren (Antwort A) ist falsch, die Variable bleibt frei innerhalb des neuen Bereichs.
- F5.Pruning by Bound (bei max): Wenn LP-Lösung des Knotens kleiner oder gleich der aktuell besten bekannten ganzzahligen Lösung ist, kann der Knoten verworfen werden.
Antwort: Wahr
Erklärung: RICHTIG. Bei Maximierung: LP-Optimum ist OBERE Schranke für IP-Optimum dieses Subproblems. Wenn diese Schranke z_LP* ≤ z_LB (beste bekannte ganzzahlige Lösung) ist, kann das Subproblem höchstens gleich gut sein wie die schon bekannte Lösung, also Verwerfen sinnvoll. Achtung: bei Gleichheit (z_LP* = z_LB) auch pruning (es entstehen keine STRICT besseren Lösungen).
Typ: Wahr/Falsch
- F6.Branch & Cut ist eine Erweiterung von Branch & Bound. Was wird hinzugefügt?
Antwort: Schnittebenen (Cutting Planes) wie Gomory-Cuts
Erklärung: Branch & Cut = Branch & Bound + Schnittebenen. Nach LP-Lösung werden gültige Ungleichungen ('Cuts') hinzugefügt, die die fraktionale LP-Lösung abschneiden ohne ganzzahlige Lösungen zu eliminieren. Berühmt: Gomory-Cuts (1958, allgemein). Moderne MIP-Solver (Gurobi, CPLEX) sind Branch-and-Cut-Implementierungen + Heuristiken + Pre-Processing.
Klausur-Quiz
Branch & Bound, Klausur-Quiz
6 typische Klausurfragen zu Algorithmus, Pruning und Strategien.
Klausurfragen mit Lösungen (6)
- F1.Wer entwickelte das Branch-and-Bound-Verfahren?
Antwort: Land & Doig (1960)
Erklärung: Branch-and-Bound: Ailsa Land & Alison Doig, 1960 ('An Automatic Method of Solving Discrete Programming Problems'). Dantzig = Simplex (LP). Bellman = Dynamic Programming. Gomory = Schnittebenen (gemeinsame Erfindung der frühen 1960er für IP-Lösung).
- F2.Beim min-IP: wie initialisiert man die Inkumbent?
Antwort: z_UB = +∞
Erklärung: Bei min: Inkumbent z_UB ist obere Schranke der besten bekannten ganzzahligen Lösung. Initialisierung: +∞ (noch keine ganzzahlige Lösung gefunden, also schlimmster Fall = unendlich groß). Wird mit jeder neuen Integer-Lösung kleiner. Pruning by Bound bei min: wenn LP-Lösung ≥ z_UB → Verwerfen. Bei max umgekehrt: z_LB = -∞ initialisieren.
- F3.Bei einem max-IP gibt die LP-Relaxation eine {{1}} Schranke. Wenn die LP-Lösung bereits ganzzahlig ist, wird der Knoten durch {{2}} 'gepruned' und die {{3}} (beste bekannte ganzzahlige Lösung) aktualisiert. Wenn die LP-Lösung schlechter ist als die Inkumbent, wird der Knoten durch {{4}} verworfen.
Lösungen pro Lücke:
- {{1}}: obere
- {{2}}: Optimality / Integer-Solution / ganzzahliger Lösung
- {{3}}: Inkumbent / untere Schranke / z_LB
- {{4}}: Bound / Schranke / Pruning by Bound
Erklärung: Branch-and-Bound Pruning-Regeln zusammengefasst: 1) LP gibt obere Schranke (bei max). 2) Integer-Lösung gefunden → Knoten geschlossen, Inkumbent z_LB aktualisiert. 3) LP-Schranke ≤ Inkumbent → Pruning by Bound. 4) LP unzulässig → Pruning by Infeasibility. Klausur-Standard-Fragen drehen sich um diese 3 Regeln.
Typ: Lückentext
- F4.Bringe die Schritte des Branch-and-Bound-Algorithmus für einen Knoten in die richtige Reihenfolge.
Richtige Reihenfolge:
- Knoten auswählen aus offenen Knoten
- LP-Relaxation des Knotens lösen
- Pruning-Tests: Bound / Infeasible / Integer?
- Branch: 2 Subprobleme erzeugen (x ≤ ⌊f⌋ und x ≥ ⌈f⌉)
Erklärung: Pro Iteration: 1) Knoten auswählen (Best-First / Depth-First). 2) LP-Relaxation lösen → Wert z_LP* + Lösung x*. 3) Pruning-Tests durchführen, falls verworfen, weiter zu nächstem Knoten. 4) Sonst: Branch auf fraktionaler Variable, 2 Kind-Knoten in offene Liste. Wiederhole bis keine offenen Knoten mehr.
Typ: Reihenfolge
- F5.Wann terminiert Branch-and-Bound mit dem Optimum?
Antwort: Wenn alle offenen Knoten durchgegangen sind (Liste leer)
Erklärung: B&B terminiert genau dann, wenn keine offenen Knoten mehr im Suchbaum sind. Die letzte gefundene Inkumbent z_LB ist garantiert das Optimum. Der erste Integer-Knoten muss NICHT das Optimum sein, andere Äste könnten noch bessere ganzzahlige Lösungen liefern. Suchbaum ist endlich, also Terminierung garantiert (auch wenn Worst-Case exponentiell).
- F6.Branch-and-Bound liefert immer eine exakte (optimale) Lösung, im Gegensatz zu Heuristiken, die nur Näherungen finden.
Antwort: Wahr
Erklärung: RICHTIG. B&B ist ein EXAKTER Algorithmus, terminiert mit garantiertem Optimum. Trade-off: Worst-Case exponentielle Laufzeit. Heuristiken (Greedy, Lokale Suche, Genetic) liefern schnelle Approximationen, ohne Optimalitäts-Garantie. Bei realen Problemen: kleine Instanzen B&B, große Instanzen Heuristiken + B&B Hybrid (Matheuristiken).
Typ: Wahr/Falsch
