Optimization Online


Min-max-min Robust Combinatorial Optimization

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

Abstract: The idea of k-adaptability in two-stage robust optimization is to calculate a fixed number k of second-stage policies here-and-now. After the actual scenario is revealed, the best of these policies is selected. This idea leads to a min-max-min 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 min-max-min 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 oracle-based algorithm to solve the latter problem for any underlying combinatorial problem. On the other hand, we prove that the min-max-min problem is NP-hard 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 k-Adaptability Combinatorial Optimization Complexity

Category 1: Robust Optimization

Category 2: Combinatorial Optimization

Category 3: Integer Programming (0-1 Programming )

Citation: Buchheim, C. & Kurtz, J. Math. Program. (2016). doi:10.1007/s10107-016-1053-z


Entry Submitted: 06/18/2015
Entry Accepted: 06/18/2015
Entry Last Modified: 08/01/2016

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