Many objectives have been proposed for optimization under uncertainty. The typical stochastic programming objective of minimizing expected cost may yield solutions that are inexpensive in the long run but perform poorly under certain realizations of the random data. On the other hand, the typical robust optimization objective of minimizing maximum cost or regret tends to be overly conservative, planning against a disastrous but unlikely scenario. In this paper, we present facility location models that combine 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, the P-median problem and the uncapacitated fixed-charge location problem. We solve both problems using variable splitting (Lagrangian decomposition), in which the subproblem reduces to the multiple-choice knapsack problem. Feasible solutions are found using an upper-bounding heuristic. 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.
Citation
Technical Report #04T-014, July 2004, Department of Industrial and Systems Engineering, Lehigh University