UNIVERSITÄTSBIBLIOTHEK

Having a Plan B for Robust Optimization

  • We extend the standard concept of robust optimization by the introduction of an alternative solution. In contrast to the classic concept, one is allowed to chose two solutions from which the best can be picked after the uncertain scenario has been revealed. We focus in this paper on the resulting robust problem for combinatorial problems with bounded uncertainty sets. We present a reformulation of the robust problem which decomposes it into polynomially many subproblems. In each subproblem one needs to find two solutions which are connected by a cost function which penalizes if the same element is part of both solutions. Using this reformulation, we show how the robust problem can be solved efficiently for the unconstrained combinatorial problem, the selection problem, and the minimum spanning tree problem. The robust problem corresponding to the shortest path problem turns out to be NP-complete on general graphs. However, for series-parallel graphs, the robust shortest path problem can be solved efficiently. Further, we show how approximation algorithms for the subproblem can be used to compute approximate solutions for the original problem.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:André Chassein
URN (Permalink):urn:nbn:de:hbz:386-kluedo-45857
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):17.02.2017
Jahr der Veröffentlichung:2017
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):22.02.2017
Seitenzahl:24
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Klassifikation (Mathematik):90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C47 Minimax problems [See also 49K35]
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 30.07.2015
Neuere Dokument-Versionen:urn:nbn:de:hbz:386-kluedo-50970