|
|
Forschungsschwerpunkte
Kombinatorische Auktionen...
sind eine spannende
Anwendung von Optimierung und Spieltheorie auf den
Entwurf Elektronischer Märkte (E-Commerce) zum Handel von unteilbaren
Gütern.
Hierbei geht es
darum, eine optimale Lösung eines diskreten Allokationsproblems zu finden,
wobei die Zielfunktion dem Algorithmus unbekannt ist.
Die Zielfunktion ist nur den Bietern (und zwar jedem ein anderer Teil)
bekannt.
Die Bieter können nicht zur Ehrlichkeit gezwungen werden. Die
einzige Möglichkeit, die wahre Zielfunktion dennoch von ihnen zu erhalten, besteht
darin, sie mit einer geeigneten Situation zu konfrontieren, in der ihre
Ehrlichkeit mit ihrem Ziel, den Eigennutzen zu maximieren, richtig
aligniert ist.
Bisher wurden solche
Entwurfsprobleme vor allem mit den Methoden des Mechanism-Design angegangen. Da
jedoch das Mechanism-Design algorithmische Aspekte, die zur Lösung
der anwendungsrelevanten, großen Probleme sehr wichtig wären, nahezu
völlig ignoriert, kann
Optimierung
hierzu wichtige Beiträge
leisten. Auktionen und Handelssituationen, die nur ein einzelnes Gut
involvieren, sind schon lange gut verstanden; doch über den Handel mehrerer
Güter, wenn die Güter Substitute sind
oder einander komplementieren (d.h. der Wert einer Menge unterscheidet
sich von der Summe der Werte der Elemente der Menge), ist weniger bekannt.
Diese Mehrgutauktionen sind in den
vergangenen Jahren vor allem aus drei Gründen wichtiger geworden:
- Fortschritte bei den Optimierungsalgorithmen erlauben es mittlerweile,
Probleme von nahezu anwendungsrelevanter Größe zu lösen, die
zuvor unlösbar
schienen;
- Privatisierungen öffentlicher Güter durch Regierungen und der hohe
Wettbewerbsdruck der vergangenen Jahre auf Firmen, die Einkaufskosten
(z.B. im Rahmen der
Lean-Production) zu senken, haben zu wichtigen neuen Anwendungen
mit hohen Umsätzen geführt;
- die rapide Verbreitung des Internets erlaubt die Durchführung
komplizierterer und besserer Auktionen.
Wichtige Anwendungen von Mehrgutauktionen sind beispielsweise die
Privatisierung der tschechischen und slowakischen Industrie nach dem
Beginn der freien Marktwirtschaft, die Versteigerung von
Spektrumnutzungsrechten
durch Regierungen weltweit (wie die UMTS-Auktion in Deutschland im Sommer
2000 und Spektrum-Auktionen in den USA seit 1994), von Transporttouren
durch große Firmen (z.B. Sears, The Home Depot) an viele Speditionen, von
Regierungsanleihen, von Landerechten auf begehrten Flughäfen, von
Rohstoffeinkäufen durch multinationale Konzerne von ihren Lieferanten
und das Netzwerkrouting.
In Zusammenarbeit mit Prof. R.V. Vohra (Northwestern University)
habe ich die deutsche
UMTS-Auktion analysiert [dVV01] und einen Übersichtsartikel [dVV03]
über kombinatorische Auktionen geschrieben. Gemeinsam mit
Prof. S. Bikhchandani (UCLA), Prof. J. Schummer (Northwestern
University) und Prof. R.V. Vohra konnten wir für mehrere
Anwendungen kombinatorischer Auktionen mittels einer Analyse des
primaldualen Algorithmus für geeignete Formulierungen neuartige,
anreizkompatible, aufsteigende Auktionen angeben [dVBSV02,BdVSV08,dVSV07,BdVSV11].
Eine andere wichtige Fragestellung bei kombinatorischen Auktionen ist
es, die bestmögliche Allokation bezüglich der abgegebenen Gebote zu
bestimmen. Dieses Problem lässt
sich normalerweise als (NPP-schweres) Setpacking Problem beschreiben.
In der Praxis wird es oftmals mit Branch-and-Bound oder Branch-and-Cut
Algorithmen gelöst. Die erste kombinatorische Spektrum-Auktion sollte
die Auktion #31 der Federal Communications Commission (FCC) sein. Die
Setpacking Probleme, die bei Auktion #31 und ihren
Nachfolgern und Verallgemeinerungen auftreten, führen zu großen und
schweren Instanzen. Um sie dennoch lösen zu können, habe ich während
eines Aufenthaltes am IBM T.J. Watson Research Center zusammen mit Dr.
O. Günlük und Dr. L. Ladányi (beide IBM) einen Branch-and-Price
Algorithmus entwickelt. Zur Evaluation des Algorithmus haben wir
realistische kombinatorische Datensätze aus den Ergebnissen der
FCC-Auktion #4 konstruiert. Unser Algorithmus konnte die selbstkonstruierten
und die gegebenen Testinstanzen schnell lösen.
Hierbei erwiesen sich unsere neuen Instanzen als deutlich
schwerer als viele "Standardbenchmarks", die in der
Literatur häufig benutzt werden [GLdV05].
Eigene Beiträge zum Thema: [dVV01,dVBSV02,dVV03,dVV04,dVSV07,BdVSV08,GLdV05,BdVSV11]
Optimierung in zirkulären Graphenstrukturen
Ein gemeinsames Thema
vieler meiner Aufsätze liegt
in der Untersuchung algorithmischer Fragen zu zirkulären Graphenstrukturen.
In den Arbeiten [CdV01,CdV02a] zeigen wir gemeinsam mit
Prof. E. Cheng, dass das Problem,
ein kürzestes
nichteinfaches t-Antiweb in einem Graphen zu finden, für festes t
aus N
in polynomieller Zeit lösbar ist, jedoch NPP-schwer wird, wenn t
Teil der Eingabe ist. Für den beschriebenen effizienten Algorithmus muss in einem
anderen Graphen ein nichteinfacher kürzester Kreis vorgeschriebener Parität
bezüglich t gefunden werden.
In der Arbeit [CdV02b] werden Facetten des Stable-Set Polytops
beschrieben, die von
Antiweb-Wheels induziert werden.
Mit neuen Transformationen konnte ich kürzlich
einen schnelleren O(|V|2|E|+|V|3log|V|) Separationsalgorithmus für die 1-Radungleichungen angeben
als den zuvor bekannten O(|V|4) Algorithmus.
Bei der Suche nach effizienteren Algorithmen fanden wir in [BGdV04]
Methoden, um aus Kreisbasen minimale Kreisbasen zu berechnen. Hierzu
mussten kürzeste Kreisprobleme unter einer (für [BGdV04])
oder mehreren [in Vorbereitung]Paritätsbedingungen gelöst werden. Für
[in Vorbereitung] haben wir weiterhin k-kürzeste Kreisalgorithmen unter
Paritätsbedingungen entwickelt.
In den Aufsätzen [CdV04] mit Prof. E. Cheng und [LLdV05]
mit Prof. J. Lee und
Prof. J. Leung
werden weitere Kreisprobleme
unter Paritätsbedingungen untersucht, wie sie bei der Separation
über dem Polytop der Stabilen Multisets und der Kantenfärbungen auftreten.
Eigene Beiträge zum Thema: [CdV01,CdV02a,CdV02c,CdV02b,CdV04,LLdV05,BGdV04,BGdV09]
Algorithmen für Kreisbasen großer Graphen zur
Schaltkreisverifikation
Zunächst im Rahmen eines Industrie-Projektes
und von Herbst 2001 bis Herbst 2004 in einem DFG-Projekt, studiere ich mit
Prof. P. Gritzmann (TU München) und Dr. F. Berger (Brooklyn
Polytechnic, NY) Algorithmen
zur Bestimmung dünner Kreisbasen für große Graphen. Dabei geht es
darum, für Graphen, die elektrische Schaltungen repräsentieren und
für ein zugehöriges System von Algebrodifferenzialgleichungen eine
Schranke für den algebraischen Rang des Systems zu bestimmen. Die
Laufzeit der verwendeten Algorithmen wächst mit dem
Besetzungsgrad der Systemmatrix. Um die Rangabschätzung
also schnell zu erhalten, ist eine dünne
Darstellung der Differenzialgleichungen erforderlich. Hierzu müssen
vor allem die
Kirchhoff-Spannungsgesetze dünn repräsentiert werden, wozu eine
dünne Kreisbasis des zugrundeliegenden Graphen bestimmt wird. Zwar
ist ein exakter Algorithmus zur Bestimmung minimaler Kreisbasen bekannt, seine Komplexität ist jedoch
für die praxisrelevanten Problemgrößen inakzeptabel hoch. Daher
haben wir einerseits Approximationsalgorithmen studiert, entwickelt
und getestet
und andererseits einen beweisbar schnelleren, exakten Algorithmus
gefunden. Darauf aufbauend haben wir neue Algorithmen für neue
zyklische Graphinvarianten
entwickelt, die zur Beschleunigung der Suche von Molekülen in riesigen
Strukturdatenbanken benutzt werden können.
Eigene Beiträge zum Thema: [BGdV04]
Diskrete Tomographie
Ein weiteres Thema, das durch meine Dissertation angeregt wurde und
teilweise durch ein BMBF Projekt gefördert wurde,
beschäftigte ich mich mit dem
NPP-schweren Rekonstruktionsproblem der Diskreten Tomographie, bei dem
es sich um eine spezielle Form eines verallgemeinerten
Setpartioning-Problems handelt. Dieses Rekonstruktionsproblem ist wichtig,
um in der Halbleiterproduktion die Oberfläche von Chips mit atomarer Auflösung
zu kontrollieren. In Zusammenarbeit mit Prof. P. Gritzmann und Dr. M.
Wiegelmann (München) konnte ich neue Approximationsalgorithmen angeben und
scharfe Gütegarantien beweisen. Die
Algorithmen lösen große Testprobleme (250 000 binäre Variablen)
mit kleinem absolutem Fehler 1 (d.h. 0.001%).
Die erhaltene Schranke habe ich nun auch für gewichtete Multiset-Packing
und -Covering Probleme verallgemeinert.
Weiterhin habe ich das Tomographie-Polytop studiert, Facetten und
Separationsalgorithmen angegeben und einen exakten Algorithmus zur
Lösung implementiert.
Zusammen mit Prof. P. Gritzmann konnte ich vollständig die
Komplexität der inversen ganzzahligen und der inversen binären
Radontransformationen klassifizieren.
Eigene Beiträge zum Thema: [GPdVW98,GdVW00,GdV02,GdV03,BLGdV08]
Stable Set Polyeder und Ganzzahlige Optimierung
Ein
weiteres Thema meiner Dissertation war das
Stable Set Optimierungsproblem. Ich fand mit der partiellen Substitution eine
neue Graphenoperation, für die ich
Bedingungen studierte, unter denen sie eine Facette in eine Facette
überführt, und gab Separationsalgorithmen an, die diese Struktur
ausnutzen.
Zusammen mit Prof. E. Cheng (Oakland University) studierte ich
Antiweb-Ungleichungen und ihre Verallgemeinerung zu
Antiwebwheel-Ungleichungen. Obwohl Antiweb-Ungleichungen schon seit
1975 bekannt sind, war die Komplexität ihres Separationsproblems
unbekannt.
Für Antiwebs konnten wir zeigen, dass das
Separationsproblem NPP-schwer ist, wenn die Antiwebs beliebig große
Cliquen enthalten, aber polynomial wird, wenn nur Antiwebs mit
Cliquen beschränkter Größe separiert werden sollen. Gleichermaßen konnten
wir effiziente Separationsalgorithmen für Antiwebwheels konstruieren, wenn
die Cliquengröße beschränkt ist, und hinreichende Bedingungen
dafür angeben, dass sie Facetten definieren.
Kürzlich konnte ich einen schnelleren O(|V|2|E|+|V|3log|V|) Separationsalgorithmus für die 1-Radungleichungen angeben
als den zuvor bekannten O(|V|4) Algorithmus.
Als Heuristik für ganzzahlige Optimierung wurden in
[BHdV10] Verallgemeinerungen und Verfeinerungen von Wedelin's
Algorithmus studiert, um schnell gute Lösungen für ganzzahlige
Optimierungsprobleme zu erhalten.
Eigene Beiträge zum Thema: [CdV01,CdV02a,CdV02c,CdV02b,CdV04,LLdV05,BHdV10]
|
|
|
