Kolonnen-Generierung (Dantzig-Wolfe)
- Eingeführt von
- George B. Dantzig and Philip Wolfe
- Jahr
- 1960
- Typ
- algorithm
- Familie
- Optimization
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Die Kolonnen-Generierung, entwickelt von George B. Dantzig und Philip Wolfe im Jahr 1960, ist eine leistungsstarke Optimierungstechnik zur Lösung von linearen Optimierungsproblemen großer Dimension mit spezieller Struktur.
Auch bekannt als Dantzig-Wolfe-Dekomposition, zerlegt sie das Problem in ein Master-Problem (beschränkt auf eine Teilmenge von Variablen/Spalten) und ein Preis-Subproblem (Identifizierung neuer Variablen), wobei die Lösung iterativ verbessert wird, indem nur relevante Spalten eingeführt werden.
Die Intuition hinter der Methode
Die Methode erkennt, dass viele große Optimierungsprobleme eine spezielle Struktur aufweisen: zahlreiche Variablen, aber wenige wirklich wichtige Nebenbedingungen oder natürlich zerlegbare Teilprobleme. Anstatt das vollständige Problem mit allen möglichen Variablen zu lösen, behält die Kolonnen-Generierung nur eine kleine Teilmenge vielversprechender Spalten (Variablen) bei. Das Preis-Subproblem, das mittels reduzierter Kosten und der Problemstruktur gelöst wird, identifiziert neue Spalten, die die Master-Lösung verbessern. Durch iteratives Hinzufügen der vielversprechendsten Spalten baut der Algorithmus effizient eine Lösung auf und vermeidet die rechnerische Belastung, alle Spalten gleichzeitig zu handhaben.
Geschichte
Dantzig und Wolfe führten 1960 das Dekompositionsprinzip für lineare Programme ein und legten damit die theoretische Grundlage. Gilmore und Gomory (1961) wendeten es auf das Zuschnittproblem an und demonstrierten dessen praktische Leistungsfähigkeit. Die Methode gewann in den 1980er und 90er Jahren an Bedeutung für Fahrzeug-Routing- und Personalplanungsprobleme. Die Integration mit Branch-and-Bound, wodurch Branch-and-Price-Algorithmen entstanden, erweiterte die Anwendbarkeit auf die ganzzahlige Programmierung. Moderne Anwendungen umfassen die Flugpersonalplanung, Schiffsroutenplanung und die Optimierung großer Logistiksysteme.
Wann wird sie eingesetzt?
Wenden Sie die Kolonnen-Generierung an, wenn Sie lineare Programme großer Dimension mit spezieller Struktur lösen, insbesondere wenn die Anzahl der Variablen riesig ist, aber eine kleine Teilmenge die optimale Lösung dominiert. Sie ist ideal für Zuschnittprobleme, Fahrzeug-Routing, Personalplanung und Rucksackprobleme. Verwenden Sie sie, wenn die Problemstruktur eine effiziente Lösung des Preis-Subproblems ermöglicht. Für Probleme ohne ausnutzbare Struktur oder moderater Größe sind Standard-LP-Löser praktischer.
Grenzen und Hinweise
- Erfordert eine Problemstruktur, die eine effiziente Lösung des Preis-Subproblems ermöglicht
- Die Konvergenz kann langsam sein, insbesondere nahe der Optimalität (Tailing-off-Effekt)
- Die Lösung des Preis-Subproblems muss zuverlässig und effizient sein, sonst gehen die Effizienzgewinne verloren
- Die Implementierungskomplexität ist höher als bei Standard-LP-Methoden
- Numerische Stabilitätsprobleme mit großen dualen Werten und reduzierten Kosten
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Löst Probleme großer Dimension, die aufgrund von Spaltenexplosion mit Standardmethoden unlösbar sind
- Nutzt die Problemstruktur, um nur relevante Spalten zu generieren
- Liefert Schranken für die Lösungsqualität während der Iteration
- Natürlich geeignet für Probleme mit spezieller Teilstruktur (identische Teilprobleme, Symmetrie)
- Integrierbar mit Branch-and-Bound für ganzzahlige Programme (Branch-and-Price)
Anwendungen
- Zuschnittproblem: Minimierung von Verschnitt beim Schneiden von Material in geforderte Größen
- Fahrzeug-Routing: Optimierung von Routen für Lieferungen und Transporte unter Berücksichtigung von Zeitfenstern und Kapazitätsbeschränkungen
- Personalplanung: Zuweisung von Besatzungsmitgliedern zu Flügen oder Schichten unter Minimierung der Gesamtkosten
- Rucksackproblem (Bin Packing): Effizientes Packen von Gegenständen in Behälter zur Minimierung von Verschnitt und Anzahl der Behälter
- Dienstplanung (Rostering): Planung von Arbeitskräften über Schichten hinweg unter Berücksichtigung von Verfügbarkeit und Präferenzen
- Flugplanung: Koordination von Flugplänen, Besatzungszuweisungen und Flugzeugwartung
So funktioniert es
So funktioniert es
Beginnen Sie mit einem eingeschränkten Master-Problem, das nur eine Teilmenge der für eine anfängliche zulässige Lösung notwendigen Spalten enthält.
Lösen Sie das Duale des aktuellen eingeschränkten Masters mit dem Simplex-Tableau. Identifizieren Sie reduzierte Kosten und richten Sie das Preis-Subproblem ein, um Variablen mit negativen reduzierten Kosten (bei Minimierung) zu finden.
Lösen Sie das Preis-Subproblem unter Ausnutzung seiner speziellen Struktur. Wenn eine neue Spalte mit negativen reduzierten Kosten gefunden wird, fügen Sie sie dem Master-Problem hinzu und wiederholen Sie den Vorgang. Wenn keine verbessernde Spalte existiert, ist die aktuelle Lösung optimal.
Häufige Fallstricke
- Auswahl eines ineffizienten Preis-Subproblem-Algorithmus, der die Effizienzgewinne der Kolonnen-Generierung zunichte macht
- Erkennen der Problemstruktur, die sich für die Dekomposition eignet, nicht, was zu schlechter Leistung führt
- Unzureichende Konvergenzerkennung oder zu strenge Toleranz, was zu verschwendeten Iterationen führt
- Keine Implementierung von Stabilisierungstechniken zur Bewältigung des Tailing-off-Effekts
Häufig gestellte Fragen
Was ist das Preis-Subproblem bei der Kolonnen-Generierung und wie hängt es mit reduzierten Kosten zusammen?
Das Preis-Subproblem identifiziert neue Variablen (Spalten) mit negativen reduzierten Kosten, die die Master-Lösung verbessern. Die Werte der reduzierten Kosten stammen aus dem Dualen des eingeschränkten Master-Problems und leiten die Suche im Preis-Subproblem.
Warum ist die Kolonnen-Generierung besser als die Lösung des vollständigen Problems mit allen Spalten?
Bei vielen Problemen ist die Anzahl der potenziellen Spalten exponentiell oder unendlich, was eine Aufzählung aller unmöglich macht. Die Kolonnen-Generierung erzeugt nur die notwendigen Spalten bei Bedarf und reduziert dadurch den Rechenaufwand drastisch.
Was ist der Tailing-off-Effekt und wie kann er gemildert werden?
Tailing-off tritt auf, wenn die Kolonnen-Generierung nahe der Optimalität nur langsame Fortschritte macht und viele Spalten mit minimaler Verbesserung generiert. Stabilisierungstechniken (Dual-Glättung, Trust-Region-Methoden, Cutoff-Strategien) reduzieren seine Auswirkungen.
Wie erweitert Branch-and-Price die Kolonnen-Generierung auf die ganzzahlige Programmierung?
Branch-and-Price kombiniert Kolonnen-Generierung mit Branch-and-Bound: An jedem Knoten löst die Kolonnen-Generierung die LP-Relaxation, und Verzweigungsentscheidungen schränken das Problem weiter ein, wenn LP-Lösungen gebrochen sind (nicht ganzzahlig).
Verwandte Methoden
Quellen
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.
DOI-Referenz öffnenKopiert.Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.
DOI-Referenz öffnenKopiert.