  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 Gamma 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 NPhard 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 knapsack and shortest path instances previously used in the
scientific literature and find that the heuristics obtain good quality
solutions in short computational times.
