  


Stochastic pRobust Location Problems
Lawrence V. Snyder (lvs2lehigh.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 minimumexpectedcost solution that is probust; i.e., whose relative regret is no more than 100p% in each scenario. We present probust models based on two classical facility location problems, the Pmedian problem and the uncapacitated fixedcharge location problem. We solve both problems using variable splitting (Lagrangian decomposition), in which the subproblem reduces to the multiplechoice knapsack problem. Feasible solutions are found using an upperbounding 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 minimaxregret versions of the location problems. Keywords: robust facility location, stochastic probustness, variable splitting, multiplechoice knapsack problem Category 1: Robust Optimization Category 2: Applications  OR and Management Sciences (Production and Logistics ) Citation: Technical Report #04T014, July 2004, Department of Industrial and Systems Engineering, Lehigh University Download: [Postscript][PDF] Entry Submitted: 08/03/2004 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  