Optimization Online


On the Value of Multistage Stochastic Facility Location with (or without) Risk Aversion

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

Abstract: We study the capacitated facility location problem over a finite time horizon with uncertain demand at each stage. We model a multistage stochastic integer program based on a scenario tree representation of the multi-period uncertainty, as opposed to a two-stage approach that does not have the flexibility of dynamically locating facilities but has to decide multi-period facility-location plans at the beginning of the horizon. At each stage, after realizing the demand, we optimize facility locations and recourse flows from built facilities to demand sites, with the goal of minimizing certain measure of the total cost of locating facilities and transportation. We quantify the lower bounds for the gaps between optimal objective values of the multistage models and their two-stage counterparts, under risk-neutral and risk-averse (coherent risk) measures. We also show that the bound with risk aversion is at least as large as the risk-neutral bound. We employ Stochastic Dual Dynamic integer Programming (SDDiP) for solving the risk-neutral multistage model, and extend the method for the risk-averse case using expected conditional risk measures (ECRMs). We conduct computational studies on diverse instances to empirically demonstrate the bounds, as well as to show the computational efficacy of SDDiP for solving both risk-neutral and risk-averse multistage models.

Keywords: Multistage stochastic integer programming; risk-averse optimization; Stochastic Dual Dynamic integer Programming (SDDiP)

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- Science and Engineering (Facility Planning and Design )


Download: [PDF]

Entry Submitted: 09/16/2018
Entry Accepted: 09/16/2018
Entry Last Modified: 09/16/2018

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