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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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.
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
Branch & Bound: Iteratives Aufteilen des Problems in Subprobleme (Branch) + Berechnen oberer Schranken durch LP-Relaxation (Bound) + Abschneiden hoffnungsloser Äste (Prune).
z_(LB) = -∞ (bei max).Wähle einen offenen Knoten aus dem Suchbaum (Strategie z.B. Best-First, Depth-First).
Berechne LP-Optimum z_(LP)^* für den aktuellen Knoten.
Wenn z_(LP)^* ≤ z_(LB) (bei max):
→ Verwerfen. Selbst die LP-Lösung ist nicht besser als die beste bekannte ganzzahlige.
Wenn LP unzulässig: → Verwerfen. Kein Subproblem hat eine Lösung.
Wenn LP-Lösung bereits ganzzahlig:
→ Inkumbent updaten (z_(LB) ← z_(LP)^*), Knoten schließen.
Wähle fraktionale Variable x_j^* = f (mit f nicht ganzzahlig).
Erstelle 2 Kind-Knoten:
x_j ≤ lfloor f rfloorx_j ≥ lceil f rceilZurück zu Schritt 1.
Wenn keine offenen Knoten mehr → fertig. z_(LB) ist das Optimum.
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).
| 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 |
Welche fraktionale Variable für Branching wählen?
x_j mit f_j nächst zu 0.5Branch & Cut kombiniert Branch & Bound mit Schnittebenen (Cutting Planes):
Berühmte Schnittebenen:
Moderne MIP-Solver (Gurobi, CPLEX) sind Branch-and-Cut + Heuristiken.
| 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 |
| 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) |
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.
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.
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.
6 Aufgaben zu Algorithmus, Pruning-Regeln und Strategien.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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.
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
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.
6 typische Klausurfragen zu Algorithmus, Pruning und Strategien.
Klausurfragen mit Lösungen (6)
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).
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.
Lösungen pro Lücke:
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
Richtige Reihenfolge:
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
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).
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