  


Minmaxmin robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions
Christoph Buchheim (christoph.buchheimmath.tudortmund.de) Abstract: In the classical minmax 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 worstcase optimal, i.e., we model the problem as a minmaxmin 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 polynomialtime oracle algorithm, we show that the problem of choosing k minmaxmin 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 NPhard 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  