  We consider robust combinatorial optimization problems where the decision
maker can react to a scenario by choosing from a finite set of $k$ solutions.
This approach is appropriate for decision problems under uncertainty where the
implementation of decisions requires preparing the ground. We focus on the case
that the set of possible scenarios is described through a budgeted uncertainty
set and provide three algorithms for the problem. The first algorithm solves
heuristically the dualized problem, a non-convex mixed-integer non-linear
program (MINLP), via an alternating optimization approach. The second algorithm
solves the MINLP exactly for $k=2$ through a dedicated spatial branch-and-bound
algorithm. The third approach enumerates $k$-tuples, relying on strong bounds
to avoid a complete enumeration. We test our methods on shortest path instances
that were used in the previous literature and on randomly generated knapsack
instances, and find that our methods considerably outperform previous
approaches. Many instances that were previously not solved within hours can now
be solved within few minutes, often even faster.
