Recoverable Robustness by Column Generation

When using combinatorial models for real-life problems, we often have to cope with uncertainty in our data. Robust optimization tries to take this into account, by demanding that the solution to our problem is feasible with regard to a set of scenarios for our uncertain data.
Recoverable robustness extends this idea by adding recovery: we may recover from an initial solution to some recovery solution by some restricted recovery method.

We present a column generation framework for recoverable robustness, introducing two decomposition methods that both return separate problems for each single scenario. We apply the framework to recoverable robust variants of some well known problems, like the knapsack problem and the shortest path problem. We show that we can find the optimal solution for these recoverable robust problems using branch-and-price and the classic algorithms for these problems.

Furthermore, extensive experimentation is performed on the size robust knapsack problem, comparing these column generation techniques to pure dynamic programming and local search algorithms. We show that the separate recovery decomposition yields some practical results in solving these problems in reasonable time and scales very well with the number of scenarios.