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
Ganzzahlige Programmierung (IP)
Wenn Variablen ganzzahlig sein müssen, wird LP zum IP, und plötzlich ist das Problem NP-schwer. 8/8 OR-Klausuren behandeln das Thema.
Die Idee in einem Satz
Ganzzahlige Programmierung (Integer Programming, IP): Eine lineare Optimierung, bei der die Variablen ganzzahlig sein müssen (statt beliebig reell).
3 Typen ganzzahliger Programme
| Typ | Variablen | Beispiel |
|---|---|---|
| Reines IP | Alle x_i ∈ ℤ | Anzahl Maschinen, Anzahl Mitarbeiter |
| Gemischt-ganzzahliges IP (MIP) | Manche x_i ∈ ℤ, andere reell | Mengen-Variablen + Setup-Kosten |
| 0-1-IP (binär) | x_i ∈ \0, 1\ | Ja/Nein-Entscheidungen, Zuordnung |
0-1-IP ist der wichtigste Spezialfall, Klausur-Klassiker.
LP-Relaxation: warum nicht einfach runden?
LP-Relaxation: Lass die Ganzzahligkeits-Bedingung weg, löse das LP. Dann hast du eine kontinuierliche Lösung x_i^*, oft NICHT ganzzahlig (z.B. x₁^* = 3.75).
Naive Idee: Runde die LP-Lösung auf nächsten ganzen Wert.
Problem: Das funktioniert SELTEN. Drei Fallen:
- Rundung kann unzulässig sein. LP-Lösung
(3.75, 1.25)→ aufrunden auf(4, 2)verletzt vielleicht Restriktionen. - Rundung kann suboptimal sein. Das IP-Optimum kann an einem GITTERPUNKT liegen, der weit von der LP-Lösung entfernt ist.
- Es gibt
2ⁿRundungs-Möglichkeiten. Bei 30 Variablen schon 1 Mrd Kombinationen.
Daher: Eigene Algorithmen für IP. Standard: Branch & Bound (siehe eigenes Topic).
Integrality Gap
Integrality Gap: Differenz zwischen LP-Relaxation-Optimum und IP-Optimum.
Gap = z_(LP)^* - z_(IP)^* (bei max)
Eigenschaften:
- Bei Maximierung:
z_(LP)^* ≥ z_(IP)^*(LP ist immer mindestens so gut) - Kleine Gap → LP-Relaxation gibt gute Schätzung
- Große Gap → schwierigeres IP-Problem
LP-Relaxation liefert immer eine obere Schranke für IP (bei max) → wichtig für Branch & Bound.
Wann taucht IP auf?
1. Diskrete Entscheidungen
Anzahl Maschinen, Mitarbeiter, Fahrzeuge, alles ganze Zahlen.
2. Ja/Nein-Entscheidungen (0-1-IP)
"Soll Projekt
jdurchgeführt werden?" →x_j ∈ \0, 1\"Wird Standortieröffnet?" →y_i ∈ \0, 1\"Bekommt PersoniAufgabej?" →x_(ij) ∈ \0, 1\
3. Logische Verknüpfungen via Big-M-Methode
"Wenn Maschine läuft, MUSS Setup-Kosten anfallen" "Wenn Bestellung > 0, dann mindestens 10 Stück"
Formulierung mit binärer Variable y ∈ \0, 1\ und großer Konstante M:
x ≤ M · y
→ Wenn y = 0, dann x ≤ 0 (also x = 0). Wenn y = 1, dann x ≤ M (frei).
4. Disjunktive Restriktionen ("entweder-oder")
"Entweder Restriktion A oder Restriktion B muss erfüllt sein."
Formulierung:
a_A^T x ≤ b_A + M(1 - y) und a_B^T x ≤ b_B + My mit y ∈ \0, 1\
Klassische 0-1-IP-Probleme
Knapsack-Problem (Rucksack)
Wähle Gegenstände mit max. Wert, ohne Gewichts-Grenze zu überschreiten.
max Σ_j v_j x_j s.t. Σ_j w_j x_j ≤ W, x_j ∈ \0, 1\
NP-schwer, aber gut studiert. Greedy-Approximation: nach Wert/Gewicht sortieren.
Set-Covering-Problem
Wähle eine Menge von Standorten, die jede Region mindestens 1× abdecken.
Anwendung: Feuerwehr-Standorte, WLAN-Hotspots, Lager-Standorte.
TSP, Travelling Salesman Problem
Finde die kürzeste Rundreise durch
nStädte.
min Σ_(ij) c_(ij) x_(ij), x_(ij) ∈ \0, 1\
Mit zusätzlichen Subtour-Eliminations-Restriktionen. Klassisches NP-schweres Problem.
Assignment-Problem (Zuordnung)
Ordne
nPersonennAufgaben zu, jede Person genau eine, minimiere Gesamtkosten.
min Σ_(ij) c_(ij) x_(ij), x_(ij) ∈ \0, 1\
mit Σ_j x_(ij) = 1 ∀ i und Σ_i x_(ij) = 1 ∀ j.
Spezialfall: LP-Relaxation ist hier exakt, Lösung ist automatisch ganzzahlig. Lösbar mit Hungarian Algorithm in O(n³).
Komplexität
| Problem | Komplexität |
|---|---|
| LP (kontinuierlich) | polynomial (Simplex praktisch schnell, Karmarkar's Algorithmus theoretisch polynomial) |
| Allgemeines IP | NP-schwer |
| 0-1-IP | NP-schwer (sogar das Knapsack-Entscheidungs-Problem ist NP-vollständig) |
| Assignment-Problem | polynomial (O(n³) via Hungarian) |
| TSP | NP-schwer |
Lösungsverfahren
| Verfahren | Wann? |
|---|---|
| Branch & Bound | Allgemeines IP, exakte Lösung |
| Branch & Cut | Kombination mit Schnittebenen (Gomory-Cuts) |
| Heuristiken | Schnelle Näherungs-Lösung (Greedy, lokale Suche, Genetic) |
| Spezial-Algorithmen | Assignment (Hungarian), Matching, MinCost-Flow |
| MIP-Solver | CPLEX, Gurobi, GLPK (Open Source) |
Klausur-Faustregeln
1. IP-Relaxation gibt OBERE Schranke (bei max). Wichtig für Branch & Bound und Bounds-Argumente.
2. Rundung der LP-Lösung ist KEIN gültiger IP-Algorithmus. Resultat kann unzulässig oder weit vom Optimum entfernt sein.
3. 0-1-IP ist wichtigster Spezialfall. Klausur-Beispiele: Knapsack, Assignment, Set Cover, Standort-Auswahl.
4. Big-M-Methode für logische Verknüpfungen. x ≤ M · y koppelt x an binäre Entscheidung y.
5. NP-Schwere bedeutet exponentielle Worst-Case-Laufzeit. In der Praxis lösen MIP-Solver (Gurobi, CPLEX) erstaunlich große Instanzen.
6. Assignment ist Spezialfall: LP-Relaxation ist exakt, kein Branch & Bound nötig.
Häufige Stolpersteine
1. LP-Lösung einfach runden. Falsch. Ergebnis kann unzulässig (zu viel Material) oder suboptimal sein. IMMER mit Branch & Bound oder spezial-Algorithmus.
2. 'IP-Optimum ≤ LP-Optimum' bei min vergessen. Bei MIN-Problemen gilt z_(LP)^* ≤ z_(IP)^*. Bei MAX gilt z_(LP)^* ≥ z_(IP)^*. Klausur-Falle.
3. Big-M zu klein wählen. Wenn M zu klein gewählt wird, ist die Restriktion x ≤ M · y aktiv selbst wenn y = 1, verzerrt das LP. M muss > obere Schranke von x sein.
4. Assignment-Problem mit Branch & Bound lösen. Unnötig kompliziert, LP-Relaxation reicht (oder Hungarian Algorithm).
5. NP-schwer ≠ unlösbar. Real-world MIP-Solver lösen Instanzen mit Mio Variablen. NP-Schwere ist eine Worst-Case-Aussage.
6. Ganzzahlig vs. nichtnegativ verwechseln. x ∈ ℤ₊ heißt: ganzzahlig UND nichtnegativ. x ∈ ℤ ohne Index heißt: nur ganzzahlig, kann negativ sein.
Interaktiv verstehen
IP vs. LP-Relaxation visualisiert
3 Beispiel-Probleme (Rucksack / Produktions-Mix / Binäre Projekt-Auswahl) zeigen den Unterschied zwischen LP-Relaxation (kontinuierliche Lösung) und IP-Optimum (Gitterpunkt).
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Lösen Sie das IP" IMMER LP-Relaxation als obere/untere Schranke berechnen. Dann zeigen, dass naive Rundung fehlschlägt + nächstes Gitterpunkt-Argument. So sichert man Teilpunkte selbst ohne Branch & Bound durchgerechnet zu haben.
Praxis-Übung
Ganzzahlige Programmierung, Praxis-Übung
6 Aufgaben zu IP-Typen, LP-Relaxation, Big-M und Komplexität.
Klausurfragen mit Lösungen (6)
- F1.Was unterscheidet ein IP (Integer Program) von einem LP (Linear Program)?
Antwort: IP-Variablen müssen ganzzahlig sein, LP-Variablen sind reell
Erklärung: Beim IP müssen einige (oder alle) Variablen ganzzahlig sein (x ∈ ℤ). Beim LP sind alle Variablen reell (x ∈ ℝ). Diese scheinbar kleine Änderung macht IP NP-schwer, während LP polynomial lösbar ist. Beides sind lineare Probleme (Zielfunktion + Restriktionen linear).
- F2.Welcher Wertebereich gilt für eine binäre Variable in einem 0-1-IP?
Antwort: x ∈ {0, 1}
Erklärung: 0-1-IP: x ∈ {0, 1}. Modelliert Ja/Nein-Entscheidungen. Klausur-Klassiker: x_ij = 1 wenn Person i Aufgabe j zugeordnet, sonst 0. Wichtigster IP-Spezialfall.
- F3.Ordne das IP-Problem dem typischen Anwendungsfall zu.
Zuordnungen:
- Knapsack → Wähle Gegenstände mit max. Wert unter Gewichts-Grenze
- TSP → Finde kürzeste Rundreise durch n Städte
- Set Cover → Wähle Standorte die jede Region abdecken
- Assignment → Ordne n Personen n Aufgaben zu (1:1)
Erklärung: Klassische 0-1-IP-Probleme: Knapsack (max Wert), TSP (min Strecke), Set Cover (min Standorte), Assignment (min Kosten 1:1). Alle bis auf Assignment sind NP-schwer. Assignment ist polynomial (Hungarian Algorithm, O(n³)), LP-Relaxation ist hier sogar exakt.
Typ: Zuordnung
- F4.Was ist der 'Integrality Gap' eines IP-Problems?
Antwort: Differenz zwischen IP-Optimum und LP-Relaxations-Optimum
Erklärung: Integrality Gap = z*_LP − z*_IP (bei max). Misst, wie gut die LP-Relaxation das IP approximiert. Kleine Gap → LP-Schätzung ist gut → Branch & Bound terminiert schnell. Große Gap → IP ist 'schwer'. Wichtig: bei min ist Gap = z*_IP − z*_LP (umgekehrt).
- F5.Das Aufrunden einer LP-Lösung gibt immer das IP-Optimum.
Antwort: Falsch
Erklärung: FALSCH. Aufrunden kann (1) UNZULÄSSIG sein (Restriktionen verletzt) oder (2) suboptimal (IP-Optimum ist nicht der gerundete LP-Punkt, sondern ein anderer Gitterpunkt). Beispiel: LP gibt (3.75, 1.25), aufrunden auf (4, 2) verletzt Gewichts-Restriktion → tatsächliches IP-Optimum ist (3, 2). Daher: eigene IP-Algorithmen (Branch & Bound).
Typ: Wahr/Falsch
- F6.Bei einem Maximierungs-IP gilt für die LP-Relaxation:
Antwort: z*_LP ≥ z*_IP
Erklärung: Bei max: z*_LP ≥ z*_IP. Begründung: LP ist 'lockerer' (mehr Lösungen erlaubt, auch nicht-ganzzahlige). Also kann das LP höchstens besser sein als IP. LP-Optimum ist OBERE SCHRANKE für IP. Bei min umgekehrt: z*_LP ≤ z*_IP, LP ist UNTERE Schranke. Wichtig für Branch & Bound!
Klausur-Quiz
Ganzzahlige Programmierung, Klausur-Quiz
6 typische Klausurfragen zu IP-Modellierung, Big-M, NP-Schwere und Algorithmen.
Klausurfragen mit Lösungen (6)
- F1.Welches Problem ist NICHT NP-schwer?
Antwort: Assignment-Problem (n×n)
Erklärung: Assignment-Problem ist POLYNOMIAL, der Hungarian Algorithm (Kuhn 1955) löst es in O(n³). Andere drei sind klassische NP-schwere Probleme. Assignment ist Spezialfall, weil die LP-Relaxation automatisch ganzzahlige Lösungen liefert (Eckpunkte des LP-Polyeders sind ganzzahlig).
- F2.Welches Verfahren ist der Standard-Algorithmus für allgemeine IP-Probleme?
Antwort: Branch & Bound
Erklärung: Branch & Bound ist Standard-IP-Algorithmus: Problem in Subprobleme zerlegen (Branch), LP-Relaxation als Schranke (Bound), suboptimale Äste abschneiden (Pruning). Simplex löst nur LPs (kontinuierlich). Gradient Descent ist für nichtlineare Optimierung. Dijkstra für kürzeste Pfade.
- F3.Eine 0-1-Variable kann nur die Werte {{1}} oder {{2}} annehmen. Sie modelliert typischerweise {{3}}-Entscheidungen. Mit der {{4}}-Methode (große Konstante) lassen sich logische Verknüpfungen wie 'wenn y=1 dann x ≤ M' formulieren.
Lösungen pro Lücke:
- {{1}}: 0 / Null
- {{2}}: 1 / Eins
- {{3}}: Ja/Nein / binäre / Ja-Nein
- {{4}}: Big-M / Big M / BigM
Erklärung: 0-1-Variable: x ∈ {0, 1}. Modelliert Ja/Nein-Entscheidungen (Projekt ja/nein, Standort öffnen ja/nein). Big-M-Methode: x ≤ M · y koppelt kontinuierliche Variable x an binäre y. Wenn y=0, dann x=0. Wenn y=1, dann x ≤ M (frei). M muss obere Schranke von x sein.
Typ: Lückentext
- F4.Bringe die Schritte zur Lösung eines IP via Branch & Bound in die richtige Reihenfolge.
Richtige Reihenfolge:
- LP-Relaxation des ursprünglichen IP lösen
- Branch: Subprobleme mit zusätzlichen Restriktionen erzeugen
- Bound: LP-Relaxation als Schranke berechnen
- Prune: Suboptimale Äste abschneiden, ganzzahlige Lösung gefunden?
Erklärung: Branch & Bound: 1) LP-Relaxation lösen → Lösung x* meist nicht ganzzahlig. 2) Branch: für eine fraktionale Variable xi = 1.7 zwei Sub-Probleme: xi ≤ 1 und xi ≥ 2. 3) Bound: jedes Subproblem LP-relaxieren. 4) Prune: wenn Bound schlechter als beste bekannte ganzzahlige Lösung → Ast verwerfen. Wiederholen bis alle Äste durchgegangen.
Typ: Reihenfolge
- F5.Im Big-M-Modell x ≤ M·y, was passiert wenn y = 0?
Antwort: x ≤ 0, also bei x ≥ 0: x = 0 erzwungen
Erklärung: Wenn y = 0: x ≤ M · 0 = 0. Bei der Nichtnegativitäts-Bedingung x ≥ 0 wird also x = 0 erzwungen. Wenn y = 1: x ≤ M (effektiv frei). So koppelt Big-M die kontinuierliche Variable x an die binäre Entscheidung y. Wichtig: M muss > obere Schranke von x sein, sonst verzerrt es das Optimum.
- F6.Das Knapsack-Problem ist trotz NP-Schwere in der Praxis lösbar, moderne MIP-Solver wie Gurobi/CPLEX lösen Instanzen mit Tausenden Variablen in Sekunden.
Antwort: Wahr
Erklärung: RICHTIG. NP-Schwere ist eine Worst-Case-Aussage. In der Praxis nutzen moderne MIP-Solver (Gurobi, CPLEX, GLPK) Branch & Cut + Heuristiken + clever vor-verarbeiten. Real-world MIPs mit Tausenden Variablen sind oft in Sekunden bis Minuten lösbar. Klausur-Klassiker: 'NP-schwer ≠ unlösbar in der Praxis'.
Typ: Wahr/Falsch
