Algorithms and Concepts for Robust Optimization
Algorithmen und Konzepte für die robuste Optimierung
von Marc Goerigk
Datum der mündl. Prüfung:2012-09-24
Erschienen:2013-01-14
Betreuer:Prof. Dr. Anita Schöbel
Gutachter:Prof. Dr. Anita Schöbel
Gutachter:Prof. Dr. Marco Lübbecke
Dateien
Name:goerigk.pdf
Size:2.38Mb
Format:PDF
Zusammenfassung
Englisch
In this work we consider uncertain optimizition problems where no probability distribution is known. We introduce the approaches RecFeas and RecOpt to such a robust optimization problem, using a location theoretic point of view, and discuss both theoretical and algorithmic aspects. We then consider both continuous and discrete problem applications of robust optimization: Linear programs from the Netlib benchmark set, and the aperiodic timetabling problem on the continuous side; intermodal load planning, steiner trees, periodic timetabling, and timetable information on the discrete side. Finally, we present the software library ROPI as a framework for robust optimization with support for most established mixed-integer programming solvers.
Keywords: Robust Optimization; Uncertain Optimization; Operations Research; Software Library
Weitere Sprachen
In dieser Arbeit betrachten wir unsichere
Optimierungsprobleme, für die keine Wahrscheinlichkeitsverteilung
bekannt ist. Basierend auf Methoden aus der Standortplanung, führen
wir die Ansätze RecFeas und RecOpt für solche robusten
Optimierungsprobleme ein, und diskutieren sowohl theoretische, als
auch algorithmische Aspekte. Anschließend behandeln wir
kontinuierliche und diskrete Anwendungsprobleme der robusten
Optimierung: Auf kontinuierlicher Seite lineare Programme der
Netlib Sammlung und das Problem der aperiodischen
Fahrplangestaltung; auf diskreter Seite intermodale Verladeplanung,
Steinerbäume, periodische Fahrplangestaltung und Fahrplanauskunft.
Abschließend präsentieren wir die Software-Bibliothek ROPI für
robuste Optimierung, die die meisten gängigen Lösungsprogramme für
gemischt-ganzzahlige Programme unterstützt.
Schlagwörter: Robuste Optimierung; Unsichere Optimierung; Operations Reserach; Software Bibliothek