Optimization Online


Stochastic p-Robust Location Problems

Lawrence V. Snyder (lvs2***at***lehigh.edu)
Mark S. Daskin (m-daskin***at***northwestern.edu)

Abstract: 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.

Keywords: robust facility location, stochastic p-robustness, variable splitting, multiple-choice knapsack problem

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Technical Report #04T-014, July 2004, Department of Industrial and Systems Engineering, Lehigh University

Download: [Postscript][PDF]

Entry Submitted: 08/03/2004
Entry Accepted: 08/05/2004
Entry Last Modified: 08/03/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society