Probabilistische Analyse diskreter Optimierungsprobleme
Final Report Abstract
Im Rahmen dieses Projektes haben wir uns mit der probabilistischen Analyse von Optimierungsproblemen beschäftigt. Dazu haben wir Heuristiken und strukturelle Eigenschaften nicht im vorherrschenden Worst-Case-Modell untersucht, sondern in einer so genannten geglätteten Analyse. Das Eingabemodell, das einer solchen Analyse zugrunde liegt, ist zweistufig: zunächst bestimmt ein Gegner eine Eingabe, anschließend wird diese zufällig leicht perturbiert. Im Gegensatz zur traditionellen Average-Case-Analyse ermöglicht dieser Ansatz eine Randomisierung der Eingabe unter Beibehaltung struktureller Eigenschaften, die vom Gegner bestimmt werden können. Ein Schwerpunkt des Projektes waren Probleme mit zwei Zielfunktionen. In solchen Situationen besteht die Schwierigkeit darin, einen guten Kompromiss zu finden. Ein Kompromiss, in dem kein Kriterium verbessert werden kann, ohne das andere zu verschlechtern, heißt Pareto-optimal, und die Menge der Pareto-optimalen Lösungen ist ein wichtiges Lösungskonzept für bikriterielle Probleme. Obwohl man in Anwendungen oft nur wenige Pareto-optimale Lösungen beobachtet, existieren für fast alle bikriteriellen Probleme Instanzen mit exponentiell vielen Pareto-optimalen Lösungen. Der Grund für diese Diskrepanz ist, dass theoretische Ergebnisse auf worst-case Instanzen beruhen, die sich stark von typischen Instanzen, die in der Praxis auftreten, unterscheiden. Diesem Problem entgegnen wir, indem wir unseren Analysen das semi-zufällige Eingabemodell der geglätteten Analyse zu Grunde legen. Wir zeigen, dass im Gegensatz zu der pessimistischen worst-case Sichtweise die Anzahl Pareto-optimaler Lösungen im Modell der geglätteten Analyse typischerweise klein ist. Dieses Ergebnis erklärt, warum diverser Heuristiken, die in der Praxis für verschiedene wichtige Optimierungsprobleme benutzt werden, effizient sind, obwohl es Eingaben gibt, auf denen sie sehr schlecht funktionieren. Ein weiterer heuristischer Ansatz, der in der Praxis zu sehr guten Ergebnissen führt, ist lokale Suche. Dabei handelt es sich um ein einfaches Trial-and-Error- Verfahren, bei dem man mit einer Lösung startet und diese sukzessiv versucht durch lokale Schritte zu verbessern. Lokale Suche spielt bei zahlreichen Heuristiken für logistische Optimierungsprobleme wie z. B. das Problem des Handlungsreisenden (TSP) eine wichtige Rolle. 2-Opt ist eine sehr einfache lokale Suchheuristik für das TSP, die bemerkenswert gute Ergebnisse in Bezug auf Laufzeit und Approximationsgüte erreicht. Es gibt zahlreiche experimentelle Studien von 2-Opt, das theoretische Wissen ist jedoch sehr begrenzt, so war bisher nicht einmal die worst-case Laufzeit auf euklidischen Eingaben bekannt. Wir beantworten diese Frage, indem wir für eine Familie von zweidimensionalen Instanzen konstruieren, auf denen 2- Opt exponentiell viele Schritte machen kann, bevor es ein lokales Optimum erreicht. Um dieses Resultat mit den Beobachtungen in der Praxis in Einklang zu bringen, untersuchen wir auch 2-Opt in einem geglätteten Eingabemodell. Wir verbessern bekannte Resultate deutlich und zeigen, dass 2-Opt auf geglätteten Eingaben sowohl bezüglich Laufzeit als auch der Qualität der erzielten Lösung sehr gute Ergebnisse erzielt.
Publications
- Smoothed Analysis of Integer Programming. In Proc. of the Utk Conf. on Integer Programming and Combinatorial Optimization (IPCO), S. 276-290, 2005. Und Mathematical Programming, 110(l):21-56, 2007. Eingeladener Beitrag zur Sonderausgabe mit ausgewählten Beiträgen von der IPCO 2005.
Heiko Röglin und Berthold Vöcking.
- The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization. In Proc. of the 12th Conf. on Integer Programming and Combinatorial Optimization (IPCO), S. 53-67, 2007.
Rene Beier, Heiko Röglin und Berthold Vöcking.
- Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP. In Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), S. 1295- 1304, 2007.
Matthias Englert, Heiko Röglin und Berthold Vöcking.
- Uncoordinated Two-Sided Markets. Erscheint in Proc. of the 9th ACM Conference on Electronic Commerce (EC) 2008.
Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin und Berthold Vöcking.
- Decision Making Based on Approximate and Smoothed Pareto Curves. In Proc. of the 16th Ann. Int. Symp. on Algorithms and Computation (ISAAC), S. 675-684, 2005. Und Theoretical Computer Science, 378(3):253-270, 2007. Eingeladener Beitrag zur Sonderausgabe mit ausgewählten Beiträgen von der'ISAAC 2005.
Heiner Ackermann, Alantha Newman, Heiko Röglin und Berthold Vöcking
