Optimization Online


On the Value of Multistage Stochastic Facility Location with Risk Aversion

Xian Yu(yuxian***at***umich.edu)
Siqian Shen(siqian***at***umich.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)

Abstract: We consider a multi-period capacitated facility location problem over a finite time horizon under uncertain demand in each period. We formulate a multistage stochastic integer program using a scenario tree representation of the uncertainty, and compare it with a two-stage approach that decides which facilities to open for all periods up front. In the multistage model, in each stage, after realizing the demand, a decision maker optimizes facility locations and product flows from open facilities to demand sites, with the goal of minimizing certain measures of the future random cost associated with locating facilities and satisfying demand. Using expected conditional risk measures (ECRMs), we provide tight lower bounds for the gaps between optimal objective values of risk-averse multistage models and their two-stage counterparts. Moreover, two approximation algorithms are proposed to efficiently solve risk-averse two-stage and multistage stochastic programs, whose approximation ratios are independent of the underlying stochastic process, structure of the scenario tree, number of stages, and risk-preference-related parameters. We conduct numerical studies using both randomly generated and real-world network instances to demonstrate the tightness of the analytical bounds and computational efficacy of the proposed approximation algorithms. We also provide managerial insights for guiding locating facilities with risk aversion in practice, based on various types of uncertainty cases and parameter settings.

Keywords: Multistage stochastic integer programming; risk-averse optimization; coherent risk measure; capacitated facility location; approximation algorithm

Category 1: Stochastic Programming

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 05/23/2021
Entry Accepted: 05/24/2021
Entry Last Modified: 05/23/2021

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 Optimization Society