Min–max–min robustness for combinatorial problems with discrete budgeted uncertainty

Discrete Applied Mathematics, vol. 285, pp. 707–725

Abstract

We consider robust combinatorial optimization problems with cost uncertainty where the decision maker can prepare K solutions beforehand and chooses the best of them once the true cost is revealed. Also known as min–max–min robustness (a special case of K-adaptability), it is a viable alternative to otherwise intractable two-stage problems. The uncertainty set assumed in this paper considers that in any scenario, at most Γ of the components of the cost vectors will be higher than expected, which corresponds to the extreme points of the budgeted uncertainty set. While the classical min–max problem with budgeted uncertainty is essentially as easy as the underlying deterministic problem, it turns out that the min–max–min problem is NP-hard for many easy combinatorial optimization problems, and not approximable in general. We thus present an integer programming formulation for solving the problem through a row-and-column generation algorithm. While exact, this algorithm can only cope with small problems, so we present two additional heuristics leveraging the structure of budgeted uncertainty. We compare our row-and-column generation algorithm and our heuristics on min-knapsack and shortest path instances previously used in the scientific literature and find that the heuristics obtain good quality solutions in short computational times.

Authors 3

1. Marc Goerigk

   University of Siegen

   Affiliation as printed

   Network and Data Science Management, University of Siegen, Germany

   University of Siegen

2. Jannis Kurtz Aachen Department of Mathematics

   RWTH Aachen University

   Affiliation as printed

   Department of Mathematics, RWTH Aachen University, Germany

   RWTH Aachen University

3. Michaël Poss corresponding

   Centre National de la Recherche Scientifique · Université de Montpellier · Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

   Affiliation as printed

   LIRMM, University of Montpellier, CNRS, France

   Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier