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

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≥n+1k≥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.