Stochastic p-robust location problems

The two most widely considered measures for optimization under uncertainty are minimizing expected cost and minimizing worst-case cost or regret. In this paper, we present a novel robustness measure that combines the two objectives by minimizing the expected cost while bounding the relative regret in each scenario. In particular, the models seek the minimum-expected-cost solution that is p-robust; i.e., whose relative regret is no more than 100p% in each scenario. We present p-robust models based on two classical facility location problems. We solve both problems using variable splitting, with the Lagrangian subproblem reducing to the multiple-choice knapsack problem. For many instances of the problems, finding a feasible solution, and even determining whether the instance is feasible, is difficult; we discuss a mechanism for determining infeasibility. We also show how the algorithm can be used as a heuristic to solve minimax regret versions of the location problems.