• search hit 7 of 9
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:André Chassein
URN (permanent link):urn:nbn:de:hbz:386-kluedo-45857
Document Type:Preprint
Language of publication:English
Publication Date:2017/02/17
Year of Publication:2017
Publishing Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2017/02/22
Number of page:24
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):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]
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 30.07.2015
Newer document versions:urn:nbn:de:hbz:386-kluedo-50970