Optimization Online


Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions

Christoph Buchheim (christoph.buchheim***at***math.tu-dortmund.de)
Jannis Kurtz (jannis.kurtz***at***math.tu-dortmund.de)

Abstract: In the classical min-max approach to robust combinatorial optimization, a single feasible solution is computed that optimizes the worst case over a given set of considered scenarios. As is well known, this approach is very conservative, leading to solutions that in the average case are far from being optimal. In this paper, we present a different approach: the objective is to compute k feasible solutions such that the best of these solutions for each given scenario is worst-case optimal, i.e., we model the problem as a min-max-min problem. In practice, these k solutions can be computed once in a preprocessing phase, while choosing the best of the k solutions can be done in real time for each scenario occuring. Using a polynomial-time oracle algorithm, we show that the problem of choosing k min-max-min optimal solutions is as easy as the underlying combinatorial problem if k is greater or equal n+1 and if the uncertainty set is a polytope or an ellipsoid. On contrary, in the discrete scenario case, many tractable problems such as the shortest path problem or the minimum spanning tree problem turn NP-hard in the new approach.

Keywords: robust optimization;combinatorial optimization;complexity

Category 1: Robust Optimization

Category 2: Combinatorial Optimization

Category 3: Integer Programming

Citation: technical report

Download: [PDF]

Entry Submitted: 11/27/2014
Entry Accepted: 11/27/2014
Entry Last Modified: 05/03/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society