Optimization Online


Min-max-min Robust Combinatorial Optimization Subject to Discrete Uncertainty

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

Abstract: We consider combinatorial optimization problems with uncertain objective functions. In the min-max-min robust optimization approach, a fixed number k of feasible solutions is computed such that the respective best of them is optimal in the worst case. The idea is to calculate a set of candidate solutions in a potentially expensive preprocessing and then select the best solution out of this set in real-time, once the actual scenario is known. In this paper, we investigate the complexity of this min-max-min problem in the case of discrete uncertainty, as well as its connection to the classical min-max robust counterpart. Essentially, it turns out that the min-max-min problem is not harder to solve than the min-max problem, while producing much better solutions in general.

Keywords: Robust Optimization, k-Adaptability, Discrete Uncertainty

Category 1: Robust Optimization

Category 2: Combinatorial Optimization

Category 3: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 02/01/2016
Entry Accepted: 02/01/2016
Entry Last Modified: 02/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