  


Minmaxmin Robust Combinatorial Optimization
Christoph Buchheim (christoph.buchheimmath.tudortmund.de) Abstract: The idea of kadaptability in twostage robust optimization is to calculate a fixed number k of secondstage policies hereandnow. After the actual scenario is revealed, the best of these policies is selected. This idea leads to a minmaxmin problem. In this paper, we consider the case where no first stage variables exist and propose to use this approach to solve combinatorial optimization problems with uncertainty in the objective function. We investigate the complexity of this special case for convex uncertainty sets. We first show that the minmaxmin problem is as easy as the underlying certain problem if k is greater than the number of variables and if we can optimize a linear function over the uncertainty set in polynomial time. We also provide an exact and practical oraclebased algorithm to solve the latter problem for any underlying combinatorial problem. On the other hand, we prove that the minmaxmin problem is NPhard for every fixed number k, even when the uncertainty set is a polyhedron, given by an inner description. For the case that k is smaller or equal to the number of variables, we finally propose a fast heuristic algorithm and evaluate its performance. Keywords: Robust Optimization · kAdaptability · Combinatorial Optimization · Complexity Category 1: Robust Optimization Category 2: Combinatorial Optimization Category 3: Integer Programming (01 Programming ) Citation: Buchheim, C. & Kurtz, J. Math. Program. (2016). doi:10.1007/s101070161053z Download: Entry Submitted: 06/18/2015 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  