Auf einen Blick
- ILP = Integer Linear Program: Wie ein LP, aber die Variablen müssen ganzzahlig sein – dadurch wird das Problem deutlich schwerer.
- Vier Lösungsverfahren: Vollständige Enumeration, Branch and Bound, Schnittebenenverfahren (Gomory), Dynamische Programmierung.
- Branch and Bound nutzt das relaxierte LP als obere Schranke (bei Maximierung) und die beste bekannte ganzzahlige Lösung als untere Schranke – Äste werden bei 3 Bedingungen abgeschnitten.
- Rucksackproblem ist der Klassiker: binäre Variablen \(x_i \in \{0,1\}\), Kapazitätsrestriktion, Nutzen maximieren.
- Greedy-Heuristik nach Rentabilität ist schnell, aber nicht immer optimal – ein Beispiel muss man geben können.
Kernkonzepte
3.1 Was ist ein ILP?
Ein Integer Linear Program (ILP) hat die gleiche Struktur wie ein LP, jedoch mit der zusätzlichen Forderung, dass (einige oder alle) Entscheidungsvariablen ganzzahlig sind:
u.d.N. A x ≤ b, x ≥ 0, xi ∈ ℤ
Sind alle Variablen binär (\(x_i \in \{0,1\}\)), spricht man von einem 0/1-Problem (z.B. Rucksackproblem). Die Simplex-Lösung des LP liefert im Allgemeinen keine ganzzahlige Lösung – einfaches Runden ist meist nicht zulässig und selten optimal.
3.2 Vollständige Enumeration
Das brutalste Verfahren: alle ganzzahligen Punkte im zulässigen Bereich aufzählen und den mit dem besten Zielfunktionswert wählen.
Beispiel: max \(17 x_1 + 12 x_2\) unter \(10 x_1 + 7 x_2 \le 40\), \(x_1 + x_2 \le 5\), \(x_1, x_2 \in \mathbb{N}_0\).
Man testet systematisch alle Kombinationen \((x_1, x_2)\), die beide Restriktionen erfüllen, und wählt die mit maximalem Zielfunktionswert.
3.3 Branch and Bound (Verzweigen und Abschätzen)
Der Standardansatz für ILP. Grundidee: Das Problem wird schrittweise in kleinere Teilprobleme zerlegt, für die man Schranken berechnen kann. Uninteressante Teile werden abgeschnitten.
Ablauf
- Relaxation: Ganzzahligkeit weglassen, das entstehende LP lösen. Bei Maximierung: Ergebnis ist obere Schranke.
- Verzweigen (Branch): Ist die LP-Lösung nicht ganzzahlig (z.B. \(x_1 = 1{,}67\)), teile das Problem: einmal mit \(x_1 \le 1\), einmal mit \(x_1 \ge 2\).
- Abschätzen (Bound): Für jedes Teilproblem wieder das LP relaxieren, obere Schranke bestimmen und mit der besten bisher gefundenen ganzzahligen Lösung (= untere Schranke) vergleichen.
- Wiederholen bis der Baum vollständig abgearbeitet ist.
3 Abschneide-Kriterien (unbedingt merken!)
- das relaxierte LP keine zulässige Lösung hat (leerer zulässiger Bereich),
- die obere Schranke ≤ aktuell beste bekannte ganzzahlige Lösung ist (dieser Ast kann nichts besseres liefern),
- die Lösung des relaxierten LP bereits ganzzahlig zulässig ist (Kandidat für Optimum, muss aber nicht weiter verzweigt werden).
Enumerationsbaum – Beispiel
Startknoten P0: LP-Relaxation liefert \(x_1 = 1{,}67, x_2 = 3{,}33\) mit \(Z = 68{,}33\). Wegen Nicht-Ganzzahligkeit wird verzweigt:
3.4 Schnittebenenverfahren (Gomory)
Idee: Statt zu verzweigen, wird der Lösungspolyeder Schritt für Schritt durch neue Nebenbedingungen so beschnitten, dass die aktuelle nicht-ganzzahlige LP-Ecke wegfällt, aber alle ganzzahligen Punkte erhalten bleiben.
- Löse das relaxierte LP mit Simplex.
- Ist die Lösung ganzzahlig → fertig.
- Sonst: Aus dem Endtableau eine Gomory-Schnittrestriktion ableiten.
- Diese als zusätzliche Zeile ins Tableau einfügen und mit dualem Simplex weiterlösen.
- Wiederhole bis ganzzahlig.
Geometrisch: Man legt einen "Schnitt" durch den zulässigen Bereich, der die aktuelle Bruchecke abtrennt.
3.5 Rucksackproblem (Knapsack)
Ein klassisches 0/1-Problem: Gegeben \(n\) Objekte mit Gewicht \(g_i\) und Nutzen \(w_i\), Rucksackkapazität \(K\).
u.d.N. Σ gi · xi ≤ K, xi ∈ {0, 1}
Beispiel (Budget 7000 €, 4 Projekte)
| Projekt i | Gewicht gi | Nutzen wi | Rentabilität ri = wi/gi |
|---|---|---|---|
| 1 | 4000 | 16000 | 4,00 |
| 2 | 3000 | 6000 | 2,00 |
| 3 | 3000 | 13000 | 4,33 |
| 4 | 2000 | 7000 | 3,50 |
Greedy-Heuristik nach Rentabilität
Sortiere absteigend nach \(r_i\): Projekt 3 (4,33) > Projekt 1 (4,00) > Projekt 4 (3,50) > Projekt 2 (2,00). Nimm der Reihe nach, sofern noch Kapazität übrig ist. Im Skript-Beispiel liefert Greedy die Projekte 1 & 2 mit Gewinn 22.000 € (je nach Reihenfolge / Aufgabenstellung), aber das Optimum ist die Kombination Projekte 1 & 3 mit Wert 29.000 €.
3.6 Branch and Bound am Rucksack
Am Rucksackbaum wird jeder Knoten mit drei Werten annotiert:
- Obere Schranke (aus LP-Relaxation bzw. Rentabilitäts-Trick),
- Restkapazität (noch verfügbares Budget),
- Aktueller Nutzen (Summe der bereits gewählten Objekte).
An jedem Verzweigungspunkt wird für ein Objekt entschieden: \(x_i = 0\) (nicht mitnehmen) oder \(x_i = 1\) (mitnehmen). Äste werden abgeschnitten, sobald die obere Schranke die aktuell beste ganzzahlige Lösung nicht mehr überbietet.
3.7 Dynamische Programmierung (DP)
Mehrstufige, rekursive Optimierung. Für das Rucksackproblem: zwei Matrizen, jeweils Zeilen = Projekte, Spalten = Restkapazität von 0 bis K.
- V (Wert-Matrix): V[i, k] = maximaler Nutzen, wenn nur die ersten i Projekte betrachtet werden und Kapazität k zur Verfügung steht.
- Keep (Auswahl-Matrix): Keep[i, k] = 1, falls Projekt i in der Lösung V[i, k] verwendet wird, sonst 0.
Rekursionsformel
sonst: V[i, k] = max( V[i-1, k], wi + V[i-1, k − gi] )
Füllvorgang: Zeile für Zeile, innerhalb einer Zeile links nach rechts. Am Ende steht das Optimum in V[n, K].
Auslesen der Lösung aus der Keep-Matrix
Starte bei Keep[n, K]. Ist der Eintrag 1, wurde Projekt n gewählt → gehe zu Keep[n−1, K − gn]. Ist der Eintrag 0, wurde Projekt n nicht gewählt → gehe zu Keep[n−1, K]. Wiederhole bis Zeile 0.
Merksätze
🧮 Rechenaufgaben mit Lösung5 Aufgaben
Klausur-typische Rechenaufgaben. Klick auf eine Aufgabe, um den vollständigen Lösungsweg zu sehen.
Aufgabe 1: Vollständige Enumeration eines ILP
Löse durch vollständige Enumeration:
\[ \max z = 17 x_1 + 12 x_2 \]
u.d.N.
\[ 10 x_1 + 7 x_2 \le 40 \]
\[ x_1 + x_2 \le 5 \]
\[ x_1, x_2 \in \mathbb{Z}_{\ge 0} \]
Zähle alle zulässigen ganzzahligen Punkte auf und bestimme das Optimum.
Lösung
Wir gehen alle möglichen Werte für \(x_1\) durch und prüfen die zulässigen \(x_2\)-Werte in beiden Nebenbedingungen.
\(x_1 = 0\): \(7 x_2 \le 40 \Rightarrow x_2 \le 5{,}71\); und \(x_2 \le 5\). Also \(x_2 \in \{0,1,2,3,4,5\}\).
\(x_1 = 1\): \(10 + 7 x_2 \le 40 \Rightarrow x_2 \le 4{,}28\); und \(1 + x_2 \le 5 \Rightarrow x_2 \le 4\). Also \(x_2 \in \{0,1,2,3,4\}\).
\(x_1 = 2\): \(20 + 7 x_2 \le 40 \Rightarrow x_2 \le 2{,}86\); und \(x_2 \le 3\). Also \(x_2 \in \{0,1,2\}\).
\(x_1 = 3\): \(30 + 7 x_2 \le 40 \Rightarrow x_2 \le 1{,}43\); und \(x_2 \le 2\). Also \(x_2 \in \{0,1\}\).
\(x_1 = 4\): \(40 + 7 x_2 \le 40 \Rightarrow x_2 = 0\); und \(x_2 \le 1\). Also \(x_2 = 0\).
\(x_1 \ge 5\): unzulässig (\(10 \cdot 5 = 50 > 40\)).
Zielwerte der Kandidaten
| \(x_1\) | \(x_2\) | \(z = 17 x_1 + 12 x_2\) |
|---|---|---|
| 0 | 5 | 60 |
| 1 | 4 | 17 + 48 = 65 |
| 2 | 2 | 34 + 24 = 58 |
| 3 | 1 | 51 + 12 = 63 |
| 4 | 0 | 68 |
Prüfung (4,0): \(10\cdot 4 + 7\cdot 0 = 40 \le 40\) ✓; \(4 + 0 = 4 \le 5\) ✓.
Aufgabe 2: Branch & Bound zum ILP aus Aufgabe 1
Betrachte dasselbe ILP wie in Aufgabe 1. Die LP-Relaxation liefert die Lösung \((x_1, x_2) = (1{,}67;\ 3{,}33)\) mit \(z_{LP} = 68{,}33\).
Führe ein Branch-&-Bound-Verfahren durch, beginnend mit der Verzweigung an \(x_1\): \(x_1 \le 1\) versus \(x_1 \ge 2\). Gib den vollständigen Suchbaum an.
Lösung
Knoten P0 (Wurzel): LP-Optimum \((1{,}67;\ 3{,}33)\), \(z = 68{,}33\). Nicht ganzzahlig → verzweige an \(x_1\).
Zweig P1: \(x_1 \le 1\)
Neues LP: \(\max 17 x_1 + 12 x_2\) mit \(10 x_1 + 7 x_2 \le 40\), \(x_1 + x_2 \le 5\), \(x_1 \le 1\).
Optimum: \((1;\ 4)\), \(z = 17 + 48 = 65\). Ganzzahlig! → globale untere Schranke \(z_{IP} = 65\).
Zweig P2: \(x_1 \ge 2\)
Optimum LP: \((2;\ 2{,}86)\), \(z = 34 + 34{,}29 = 68{,}29\). Nicht ganzzahlig → verzweige an \(x_2\).
P2.1: \(x_2 \le 2\): LP-Optimum \((2{,}6;\ 2)\), \(z = 44{,}2 + 24 = 68{,}2\). Nicht ganzzahlig → verzweige an \(x_1\).
- P2.1.a: \(x_1 \le 2\): LP-Optimum \((2;\ 2)\), \(z = 58\). Ganzzahlig, aber \(58 < 65\) → verwerfen (Bounding).
- P2.1.b: \(x_1 \ge 3\): LP-Optimum \((3;\ 1{,}43)\), \(z = 51 + 17{,}14 = 68{,}14\). Nicht ganzzahlig → verzweige an \(x_2\).
- P2.1.b.i: \(x_2 \le 1\): LP-Optimum \((3{,}3;\ 1)\), \(z = 56{,}1 + 12 = 68{,}1\). Verzweige an \(x_1\).
- \(x_1 \le 3\): \((3;\ 1)\), \(z = 63 < 65\) → verwerfen.
- \(x_1 \ge 4\): \((4;\ 0)\), \(z = 68\). Ganzzahlig! \(68 > 65\) → neue beste Lösung.
- P2.1.b.ii: \(x_2 \ge 2\): \(x_1 \ge 3\) und \(x_2 \ge 2\) verletzt \(10\cdot 3 + 7\cdot 2 = 44 > 40\) → unzulässig.
- P2.1.b.i: \(x_2 \le 1\): LP-Optimum \((3{,}3;\ 1)\), \(z = 56{,}1 + 12 = 68{,}1\). Verzweige an \(x_1\).
P2.2: \(x_2 \ge 3\): mit \(x_1 \ge 2\): \(10\cdot 2 + 7\cdot 3 = 41 > 40\) → unzulässig.
Aufgabe 3: Rucksack mit Greedy-Heuristik
Ein Investor verfügt über ein Budget von 7000 GE und kann in vier Projekte investieren:
| Projekt | Investition \(g_i\) (GE) | Gewinn \(w_i\) (GE) |
|---|---|---|
| P1 | 2000 | 9000 |
| P2 | 3000 | 13000 |
| P3 | 5000 | 20000 |
| P4 | 4000 | 14000 |
Sortiere nach Rentabilität und wende die Greedy-Heuristik an.
Lösung
Schritt 1: Rentabilität berechnen \(r_i = w_i / g_i\):
- \(r_1 = 9000 / 2000 = 4{,}5\)
- \(r_2 = 13000 / 3000 \approx 4{,}33\)
- \(r_3 = 20000 / 5000 = 4{,}0\)
- \(r_4 = 14000 / 4000 = 3{,}5\)
Schritt 2: Sortierung absteigend: P1 → P2 → P3 → P4.
Schritt 3: Greedy-Auswahl (Budget = 7000):
- P1 einpacken: Investition 2000 → Restbudget 5000. Nutzen 9000.
- P2 einpacken: Investition 3000 → Restbudget 2000. Nutzen 9000 + 13000 = 22000.
- P3 prüfen: benötigt 5000 > Rest 2000 → NICHT möglich.
- P4 prüfen: benötigt 4000 > Rest 2000 → NICHT möglich.
Greedy-Lösung: \(x = (1, 1, 0, 0)\), Investition 5000 GE, Gewinn 22000 GE.
Warnung: Optimal wäre P1 + P3 mit \(g = 7000\) und \(w = 29000\)! Greedy verfehlt das Optimum um 7000 GE. → Greedy ist nicht garantiert optimal.
Aufgabe 4: Rucksack mit dynamischer Programmierung
Löse denselben Rucksack (Budget \(K = 7\), Werte in 1000er-Einheiten) mit dynamischer Programmierung:
| Objekt | Gewicht \(g_i\) | Wert \(w_i\) |
|---|---|---|
| 1 | 2 | 9 |
| 2 | 3 | 13 |
| 3 | 5 | 20 |
| 4 | 4 | 14 |
Fülle die Wertetabelle \(V[i][k]\) und rekonstruiere die optimale Menge durch Backtracking.
Lösung
Rekursion: \[ V[i][k] = \begin{cases} V[i-1][k] & \text{falls } k < g_i \\ \max\left(V[i-1][k],\ w_i + V[i-1][k - g_i]\right) & \text{sonst} \end{cases} \]
Basis: \(V[0][k] = 0\) für alle \(k \in \{0, \ldots, 7\}\).
Zeile \(i=1\) (Objekt 1: \(g=2,\ w=9\))
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| V[1][k] | 0 | 0 | 9 | 9 | 9 | 9 | 9 | 9 |
Zeile \(i=2\) (Objekt 2: \(g=3,\ w=13\))
- \(k=0,1,2\): unverändert 0, 0, 9.
- \(k=3\): \(\max(9,\ 13 + V[1][0]) = \max(9, 13) = 13\).
- \(k=4\): \(\max(9,\ 13 + V[1][1]) = \max(9, 13) = 13\).
- \(k=5\): \(\max(9,\ 13 + V[1][2]) = \max(9, 22) = 22\).
- \(k=6\): \(\max(9,\ 13 + V[1][3]) = \max(9, 22) = 22\).
- \(k=7\): \(\max(9,\ 13 + V[1][4]) = \max(9, 22) = 22\).
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| V[2][k] | 0 | 0 | 9 | 13 | 13 | 22 | 22 | 22 |
Zeile \(i=3\) (Objekt 3: \(g=5,\ w=20\))
- \(k=0..4\): unverändert 0, 0, 9, 13, 13.
- \(k=5\): \(\max(22,\ 20 + V[2][0]) = \max(22, 20) = 22\).
- \(k=6\): \(\max(22,\ 20 + V[2][1]) = \max(22, 20) = 22\).
- \(k=7\): \(\max(22,\ 20 + V[2][2]) = \max(22, 29) = 29\).
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| V[3][k] | 0 | 0 | 9 | 13 | 13 | 22 | 22 | 29 |
Zeile \(i=4\) (Objekt 4: \(g=4,\ w=14\))
- \(k=0..3\): unverändert 0, 0, 9, 13.
- \(k=4\): \(\max(13,\ 14 + V[3][0]) = \max(13, 14) = 14\).
- \(k=5\): \(\max(22,\ 14 + V[3][1]) = \max(22, 14) = 22\).
- \(k=6\): \(\max(22,\ 14 + V[3][2]) = \max(22, 23) = 23\).
- \(k=7\): \(\max(29,\ 14 + V[3][3]) = \max(29, 27) = 29\).
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| V[4][k] | 0 | 0 | 9 | 13 | 14 | 22 | 23 | 29 |
Backtracking bei \(k=7\)
- \(V[4][7] = 29 = V[3][7]\) → Objekt 4 NICHT einpacken.
- \(V[3][7] = 29 \ne V[2][7] = 22\) → Objekt 3 einpacken. Rest: \(k = 7 - 5 = 2\).
- \(V[2][2] = 9 = V[1][2]\) → Objekt 2 NICHT einpacken.
- \(V[1][2] = 9 \ne V[0][2] = 0\) → Objekt 1 einpacken. Rest: \(k = 2 - 2 = 0\). Ende.
Aufgabe 5: Branch-&-Bound für Rucksack – obere Schranke im Wurzelknoten
Betrachte den Rucksack aus Aufgabe 3 (Budget 7, Werte 9/13/20/14 bei Gewichten 2/3/5/4). Baumknoten werden notiert als \((\text{obere Schranke} / \text{Restkapazität} / \text{aktueller Nutzen})\).
Der Anfangsknoten lautet: \((56 / 7 / 0)\). Verzweigt wird an \(x_1\): links \(x_1 = 1 \to (56 / 5 / 9)\), rechts \(x_1 = 0 \to (47 / 7 / 0)\).
Erkläre, wie die obere Schranke von 56 im Wurzelknoten zustande kommt und wie sich die Schranke bei den Kindknoten ergibt.
Lösung
Obere Schranke im Wurzelknoten: Die Skript-Konvention bildet als naive Obergrenze im Wurzelknoten die Summe aller Objektnutzen (theoretisches Maximum, wenn alle passen würden):
\[ U_0 = w_1 + w_2 + w_3 + w_4 = 9 + 13 + 20 + 14 = 56. \]
Diese Schranke ist zulässig, weil kein zulässiges Bündel jemals mehr als \(U_0\) an Wert erreichen kann.
Alternative: LP-Relaxation (fraktional)
Sortierung nach Rentabilität: \(r_1 = 4{,}5\); \(r_2 \approx 4{,}33\); \(r_3 = 4{,}0\); \(r_4 = 3{,}5\).
- P1 komplett: Rest 5, Nutzen 9.
- P2 komplett: Rest 2, Nutzen 22.
- P3 fraktional: \(2/5 = 0{,}4\) → Beitrag \(0{,}4 \cdot 20 = 8\).
\(\Rightarrow U_{LP} = 22 + 8 = 30\) (schärfere Schranke, wird aber im Skript nicht gewählt).
Kindknoten
Links (\(x_1 = 1\)): Objekt 1 fest eingepackt. Neue Restkapazität \(7 - 2 = 5\), aktueller Nutzen \(9\). Obere Schranke: alle noch offenen Werte + aktueller Nutzen = \(9 + 13 + 20 + 14 = 56\). Knoten: \((56 / 5 / 9)\).
Rechts (\(x_1 = 0\)): Objekt 1 ausgeschlossen. Restkapazität 7, aktueller Nutzen 0. Obere Schranke = Summe der restlichen Werte = \(13 + 20 + 14 = 47\). Knoten: \((47 / 7 / 0)\).
Bounding-Regel: Ist die obere Schranke eines Knotens \(\le\) aktuell bester ganzzahliger Zielwert \(z^\star\), wird der Knoten verworfen. So wird der Baum drastisch verkleinert.
Übungsfragen
1. Was heißt "relaxiertes Problem" und warum liefert es eine Schranke?
Das relaxierte Problem entsteht, indem man die Ganzzahligkeitsbedingung \(x_i \in \mathbb{Z}\) weglässt und stattdessen nur \(x_i \ge 0\) fordert – man löst also das zugehörige gewöhnliche LP mit dem Simplex-Verfahren.
Da der zulässige Bereich des ILP eine Teilmenge des zulässigen Bereichs des LP ist (nämlich nur die ganzzahligen Punkte), gilt: der LP-Optimalwert ist mindestens so gut wie das ILP-Optimum. Bei Maximierung heißt das: die LP-Lösung ist eine obere Schranke für das ILP. Bei Minimierung ist sie eine untere Schranke.
2. Bei Maximierung: obere oder untere Schranke aus der Relaxation?
Obere Schranke. Da der Simplex den größeren, weniger eingeschränkten Bereich durchsucht, findet er einen Wert, der mindestens so hoch ist wie das echte ILP-Optimum. Das ILP kann diesen Wert höchstens erreichen (falls die LP-Ecke zufällig ganzzahlig ist), aber nie überbieten.
Die untere Schranke bei Maximierung ist dagegen die beste bisher bekannte ganzzahlige zulässige Lösung.
3. Wann darf ein Ast im B&B-Baum abgeschnitten werden? Nenne alle 3 Fälle.
- Unzulässig: Das relaxierte LP am Knoten hat keine zulässige Lösung (leerer Bereich). Damit hat auch das ILP an dieser Stelle keine Lösung.
- Schranke schlägt: Die obere Schranke (LP-Wert) an diesem Knoten ist kleiner oder gleich der besten bisher bekannten ganzzahligen Lösung. Es kann hier nichts Besseres mehr kommen.
- Ganzzahlig: Die LP-Lösung ist bereits ganzzahlig und zulässig. Der Knoten ist ein Optimum-Kandidat; verzweigen bringt nichts mehr.
4. Warum liefert Greedy beim Rucksack nicht immer die optimale Lösung? Beispiel!
Greedy sortiert Objekte nach Rentabilität \(r_i = w_i / g_i\) und nimmt der Reihe nach, was hineinpasst. Das ist lokal optimal, aber blind für Kombinationseffekte: manchmal ist es besser, ein Objekt mit hoher Rentabilität nicht zu nehmen, um Platz für zwei andere Objekte zu haben, die zusammen einen höheren Gesamtnutzen ergeben.
Beispiel aus dem Skript (Budget 7000 €): Nach Rentabilität sortiert kommen Projekte 3 (r = 4,33) und 1 (r = 4,00) zuerst. Wenn Greedy stattdessen Projekt 1 und 2 wählt (Gewicht 4000+3000, Gewinn 22.000 €), verpasst es das Optimum aus Projekt 1 & 3 (Gewicht 4000+3000, Gewinn 29.000 €).
Die DP-Auswertung zeigt: Projekte 1 & 3 sind optimal, Greedy bleibt darunter.
5. Wie liest man aus einer Keep-Matrix ab, welche Projekte durchgeführt werden?
Man startet in der letzten Zeile bei der vollen Kapazität, also bei Keep[n, K]:
- Ist der Eintrag 1: Projekt n wird durchgeführt. Ziehe das Gewicht \(g_n\) ab und gehe zu Keep[n−1, K − gn].
- Ist der Eintrag 0: Projekt n wird nicht durchgeführt. Gehe zu Keep[n−1, K] (gleiche Spalte).
Wiederhole das Verfahren bis zur Zeile i = 1 (oder 0, je nach Nummerierung). Die Projekte, bei denen Keep = 1 stand, bilden die optimale Lösung.
6. Interpretiere den Enumerationsbaum: was bedeutet "keine zulässige Lösung"?
Ein Knoten im B&B-Baum entspricht einem Teilproblem mit zusätzlichen Einschränkungen (z.B. \(x_1 \ge 2\) UND \(x_2 \ge 3\)). Ist der zulässige Bereich dieses Teilproblems leer (die Restriktionen widersprechen sich), spricht der Simplex "keine zulässige Lösung" an diesem Knoten aus.
Das bedeutet: Es gibt in diesem Teil des Suchraums überhaupt keinen zulässigen Punkt, weder ganzzahlig noch fraktional. Der Ast kann sofort abgeschnitten werden – man muss nicht weiter verzweigen. Es geht dabei keine Information verloren, weil hier nichts Interessantes mehr passieren kann.
7. Vollständige Enumeration vs. Branch & Bound – worin liegt der Vorteil von B&B?
Die vollständige Enumeration zählt alle ganzzahligen zulässigen Punkte auf und wertet die Zielfunktion an jedem einzelnen aus. Der Aufwand ist exponentiell und bei realen Problemen unpraktikabel.
Branch and Bound spart durch die Schranken massiv Aufwand: Sobald für einen Teilbaum die obere Schranke schlechter ist als die bereits gefundene ganzzahlige Lösung, wird der gesamte Ast abgeschnitten. Man muss nicht jeden einzelnen Punkt betrachten, sondern nur zeigen, dass in einem Bereich nichts Besseres liegen kann.
Damit ist B&B in der Praxis um Größenordnungen schneller. Im Worst Case kann B&B aber trotzdem exponentiell werden – ILP ist NP-schwer.
8. Was macht das Schnittebenenverfahren (Gomory) grundsätzlich?
Statt zu verzweigen, wird der zulässige Bereich systematisch verkleinert. Aus dem Simplex-Endtableau (das eine nicht-ganzzahlige Ecke geliefert hat) leitet man eine neue lineare Ungleichung ab, die:
- alle ganzzahligen zulässigen Punkte weiterhin enthält,
- die aktuelle Bruchecke aber ausschließt.
Diese Zeile wird ins Tableau eingefügt und mit dualem Simplex weitergelöst. Man iteriert, bis die LP-Lösung ganzzahlig ist. Anschaulich: man schneidet mit einer Ebene die "störende" Ecke ab, ohne einen ganzzahligen Punkt zu verlieren.
9. Warum kann man die LP-Lösung nicht einfach runden?
Zwei Gründe:
- Zulässigkeit verletzt: Rundet man z.B. \(x_1 = 1{,}67\) auf 2 hoch, kann eine Kapazitätsrestriktion überschritten werden. Der gerundete Punkt liegt dann außerhalb des zulässigen Bereichs.
- Nicht optimal: Selbst wenn man auf einen zulässigen ganzzahligen Punkt rundet, ist dieser meist deutlich schlechter als das echte ILP-Optimum. Die Rundung ignoriert Wechselwirkungen zwischen Variablen (siehe Rucksack-Beispiel).
Deshalb sind exakte Verfahren wie B&B, Schnittebenen oder DP nötig, um Optimalität zu garantieren.
10. Was ist der Unterschied zwischen einer heuristischen und einer exakten Methode?
Heuristik (z.B. Greedy): Findet in kurzer Zeit eine zulässige Lösung, aber ohne Optimalitätsgarantie. Man weiß nicht, wie weit sie vom Optimum entfernt ist.
Exakte Methode (Enumeration, B&B, DP, Gomory): Findet garantiert das Optimum – aber unter Umständen mit hohem Rechenaufwand (exponentielle Worst-Case-Laufzeit).
In der Praxis kombiniert man beides: Greedy liefert schnell eine untere Schranke, die B&B dann zum Abschneiden nutzt.
11. Wie fülle ich die V-Matrix in der Dynamischen Programmierung Zeile für Zeile?
Konvention: Zeilen \(i = 0, 1, \dots, n\) = Anzahl betrachteter Projekte, Spalten \(k = 0, 1, \dots, K\) = Restkapazität.
- Zeile 0 (kein Projekt betrachtet): alle Einträge = 0.
- Zeilen 1 bis n: für jede Spalte k von links nach rechts:
- Wenn \(g_i > k\) (Projekt passt nicht in Restkapazität): V[i, k] = V[i−1, k]. Wert von oben übernehmen.
- Sonst: V[i, k] = max( V[i−1, k], \(w_i\) + V[i−1, k − gi] ). Man vergleicht "Projekt weglassen" mit "Projekt nehmen + Restnutzen bei Restkapazität".
- Parallel dazu wird Keep[i, k] auf 1 gesetzt, wenn das Maximum aus der zweiten Alternative kommt (Projekt gewählt), sonst 0.
Am Ende steht das Optimum in V[n, K]; die konkrete Auswahl liest man aus Keep rückwärts aus.
12. In einem B&B-Knoten steht: obere Schranke = 26, aktuell beste ganzzahlige Lösung = 29. Was tut man?
Ast abschneiden. Die obere Schranke (26) ist bereits schlechter als das, was man mit einer anderen ganzzahligen Lösung schon erreicht hat (29). Aus diesem Teilbaum kann in keinem Nachfolgeknoten mehr eine Lösung mit Zielfunktionswert > 26 kommen – erst recht keine, die 29 überbietet.
Damit spart man sich sämtliche weiteren Verzweigungen in diesem Ast. Genau das ist der Effizienzgewinn von B&B gegenüber der vollständigen Enumeration.
13. Was passiert, wenn die LP-Relaxation direkt eine ganzzahlige Lösung liefert?
Glücksfall: Man ist sofort fertig. Da die LP-Lösung eine obere Schranke ist (bei Maximierung) und diese Schranke gleichzeitig ganzzahlig zulässig ist, kann sie kein ILP übertreffen – sie ist damit das ILP-Optimum.
Das kommt in der Praxis selten vor, aber z.B. bei speziellen Problemklassen (Zuordnungsproblem, Transportproblem mit ganzzahligen Angeboten/Nachfragen) ist es garantiert der Fall (Ganzzahligkeitseigenschaft der Nebenbedingungsmatrix).
14. Worin unterscheiden sich Branch & Bound und Dynamische Programmierung im Ansatz?
B&B ist ein top-down-Verfahren: Man startet mit dem gesamten Problem, verzweigt es in Teilprobleme und schneidet uninteressante Teile mit Schranken ab. Es funktioniert für allgemeine ILPs.
DP ist ein bottom-up-Verfahren: Man löst kleine Teilprobleme (wenige Projekte, kleine Kapazität) zuerst und baut daraus größere Lösungen auf. DP nutzt die spezielle Struktur des Problems (Rucksack: Kapazität ist diskret und beschränkt) und ist dann sehr effizient, aber nicht auf beliebige ILPs anwendbar.
Für den 0/1-Rucksack ist DP mit Laufzeit O(n · K) pseudo-polynomial und praktisch schnell, sofern K nicht zu groß ist.