## 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.

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 |