Auktionen sind ein wichtiger Marktmechanismus für Güter deren Preis nicht eindeutig vorgegeben ist. Die Preisbildung und Allokation erfolgt auf Basis von Geboten. Kombinatorische Auktionen erlauben es, Gebote nicht nur für einzelne Güter, sondern
auch für Kombinationen von Gütern, sog. Güterbündel, abzugeben. Dies kann sinnvoll sein, da der Preis, den ein Bieter für ein bestimmtes Gut bereit ist zu zahlen, oftmals auf komplexe Weise von anderen Gütern und deren Preis abhängt. Eine Berücksichtigung dieser Synergien kann zu einer besseren Allokation und einer Erhöhung der Erlöse des Auktionators führen. Das grundlegende Problem von Kombinatorischen Auktionen mit dem sich diese Arbeit beschäftigt, ist die Allokation der Güter, also die Bestimmung der Gebote, die den Zuschlag erhalten. Im allgemeinen Fall wächst die Anzahl der möglichen Gebote exponentiell mit der Anzahl der angebotenen Güter. Die Bestimmung der optimalen Lösung ist im allgemeinen Fall NP-vollständig. In Kapitel 2 wird die Problematik detailliert beschrieben und es wird auf dieser Grundlage eine formale Darstellung erarbeitet. Kapitel 3 beschäftigt sich damit, wie mit Hilfe der Lagrange Relaxation und des Column Generation Verfahren eine Lösung des Problems erfolgen kann.
Inhaltsverzeichnis
1 Einleitung
2 Kombinatorische Auktionen
2.1 Synergieeffekte
2.1.1 Komplementarität / Superadditivität
2.1.2 Substituierbarkeit / Subadditivität
2.2 Grundlegende Fragen
2.3 Formale Darstellung des CAP
2.3.1 Allgemeine Formulierung des CAP
2.3.2 CAP für superadditive Wertfunktionen
2.4 Das Set-Packing Problem (SPP)
2.5 Komplexität des SPP
3 Dezentrale Lösungsverfahren
3.1 Duales SPP
3.2 Lagrange Relaxation
3.2.1 Formale Beschreibung
3.2.2 Interpretation für Auktionen
3.2.3 Heuristik zur Bestimmung des Lagrange-Multiplikators
3.3 RSB-Allokationsprozedur für airport time slots
3.4 Column Generation
3.4.1 Vorgehen zur Lösung von Kombinatorischen Auktionen
Zielsetzung & Themen
Diese Arbeit befasst sich mit der Optimierung der Allokation bei kombinatorischen Auktionen. Das primäre Ziel ist die Untersuchung mathematischer Verfahren zur Bestimmung gewinnbringender Gebote, wobei der Fokus auf der Bewältigung der NP-Vollständigkeit bei zunehmender Güteranzahl liegt.
- Grundlagen kombinatorischer Auktionen und Synergieeffekte
- Formale Modellierung als Set-Packing Problem (SPP)
- Anwendung der Lagrange-Relaxation zur dezentralen Lösungsfindung
- Methodik der Column Generation zur effizienten Variablenbehandlung
- Fallbeispiel: Allokationsprozeduren für Flughafen-Zeitschlitze
Auszug aus dem Buch
3.4 Column Generation
Column Generation ist eine Technik zum Lösen linearer Programme mit einer außerordentlich großen Zahl an Variablen. Jede Variable führt zu einer Spalte (engl. column) in der Restriktionsmatrix, daher der Name. Eine naive Implementierung des Simplex-Algorithmus benötigt Speicher für alle Spalten der Restriktionsmatrix. Selbst wenn nur ein geringer Teil dieser Spalten überhaupt einmal in die optimale Basis einer zulässigen Lösung kommt. Darüber hinaus sind von den nicht in der aktuellen Basis enthaltenen Variablen nur diejenigen interessant, die zu einer (möglichst großen) Verbesserung führen.
Das Column Generation Verfahren nutzt diese Beobachtung folgendermaßen. Zuerst wird eine optimale Lösung für eine Teilmenge von Spalten bzw. Variablen erzeugt. Dieses Subproblem ist das sog. Masterproblem. Als nächstes wird mit Hilfe der Dualen Variablen untersucht, ob eine der nicht berücksichtigten Spalte zu einer Verbesserung führt. Ist dies der Fall, wird diejenige Spalte in das Masterproblem aufgenommen, die zu der höchsten Verbesserung führt und das neue Masterproblem wird erneut gelöst. Gibt es keine Spalte mit reduzierten Kosten so ist die Lösung des Masterproblems optimal für das gesamte Problem.
Zusammenfassung der Kapitel
1 Einleitung: Einführung in die Marktmechanismen von Auktionen und Definition des Allokationsproblems bei Güterbündeln.
2 Kombinatorische Auktionen: Analyse der Synergieeffekte, formale Definition des Combinatorial Auction Problem (CAP) und Komplexitätsbetrachtung des Set-Packing Problems.
3 Dezentrale Lösungsverfahren: Untersuchung mathematischer Lösungsansätze mittels Lagrange-Relaxation, Heuristiken zur Multiplikatorbestimmung und Anwendung der Column Generation zur Bewältigung hoher Variablenmengen.
Schlüsselwörter
Kombinatorische Auktionen, Set-Packing Problem, Lagrange Relaxation, Column Generation, Allokation, Marktmechanismen, Güterbündel, Superadditivität, Winner Determination Problem, Duale Probleme, Subgradienten-Verfahren, Flughafen-Allokation, Optimierung, Lineare Programmierung, Spieltheorie
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die mathematische Lösung der Allokation bei kombinatorischen Auktionen, bei denen Bieter auf Bündel von Gütern statt nur auf Einzelgüter bieten können.
Was sind die zentralen Themenfelder?
Die zentralen Themen sind die mathematische Modellierung als Set-Packing Problem, dezentrale Lösungsalgorithmen und die effiziente Handhabung von Rechenkomplexität.
Was ist das primäre Ziel der Forschungsfrage?
Das Ziel ist die Untersuchung, wie durch Lagrange-Relaxation und Column Generation eine optimale oder beinahe optimale Zuteilung von Geboten in NP-vollständigen Szenarien erreicht werden kann.
Welche wissenschaftliche Methode wird verwendet?
Es werden Methoden des Operations Research eingesetzt, insbesondere mathematische Programmierung (Integer Programming) und iterative Algorithmen zur Preis- und Mengenbestimmung.
Was wird im Hauptteil behandelt?
Im Hauptteil werden formale Beschreibungen des CAP, das Set-Packing Problem, sowie Algorithmen wie die Lagrange-Relaxation und Column Generation zur dezentralen Problemlösung detailliert erläutert.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit wird durch Begriffe wie Kombinatorische Auktionen, Set-Packing Problem, Lagrange Relaxation und Column Generation charakterisiert.
Wie unterscheidet sich die Lagrange-Relaxation von einer direkten Lösung?
Die Lagrange-Relaxation vereinfacht das Problem durch Entspannung der Nebenbedingungen, wobei Abweichungen bestraft werden, was oft eine schnellere, wenn auch manchmal unzulässige Näherungslösung liefert.
Welchen Zweck erfüllt der Second Price Surplus (SePS) bei Ygges Heuristik?
Der SePS dient dazu, Gebote zu rangieren, um schnell eine qualitativ hochwertige Lösung als Basis für exakte Algorithmen zu erzeugen.
Warum ist das "Winner Determination Problem" bei vier Flughäfen eine Herausforderung?
Aufgrund der enormen Anzahl an Restriktionen und Variablen wächst der Rechenaufwand so stark, dass die Lösung des ganzzahligen Problems hohe Anforderungen an Hardware und Algorithmen stellt.
- Quote paper
- Stefan Gretschel (Author), 2003, Lagrange Relaxation und Column Generation für Kombinatorische Auktionen, Munich, GRIN Verlag, https://www.grin.com/document/39340
