On the Value of Multistage Risk-Averse Stochastic Facility Location With or Without Prioritization

Xianjun Yu, Siqian ShenarXiv 2021 · DOI · arXiv

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.

Introduction

Strategic facility location—deciding where to build warehouses, hospitals, or car-sharing stations—is a critical challenge when both future demand and available budgets are uncertain. This paper quantifies the financial and risk-reduction benefits of flexibility in long-term infrastructure planning by comparing "plan-it-all-now" (two-stage) versus "adapt-as-you-go" (multistage) models. The "Value of Multistage Stochastic Programming" (VMS) represents the cost savings gained by waiting for information to be revealed before making further commitments.

Methodology: Modeling Adaptivity and Risk

The researchers model uncertainty using scenario trees, where each node represents a possible state of the world at a specific time. This allows for a time-consistent approach to risk-averse decision-making through Expected Conditional Risk Measures (ECRMs), such as Conditional Value-at-Risk.

To address the computational complexity of multistage integer programs, the authors propose approximation algorithms that solve linear relaxations and substructure problems. These algorithms are designed to be efficient even as the scale of the problem increases. Furthermore, the paper incorporates prioritization, where a decision-maker ranks potential sites to maintain consistency across different budget realizations.

Key Insights and Results

  • Adaptivity in Correlated Markets: The VMS is significantly higher when demand is "stagewise dependent," meaning current demand levels strongly signal future trends.
  • The "Expanding Market" Advantage: The proposed approximation algorithms are asymptotically optimal as the market grows, making them highly effective for large-scale urban planning or business expansion.
  • Computational Efficiency: The introduction of "prioritization cuts"—mathematical constraints that prune the search space—reduced solve times for complex models from over an hour to just a few minutes.
  • Risk Profile: Out-of-sample testing demonstrated that multistage solutions consistently produced lower 95th-percentile costs than two-stage solutions, proving their superiority in hedging against "black swan" demand spikes.

Conclusion

This framework provides a robust tool for multistage, risk-averse facility location planning. By deriving tight analytical bounds and efficient algorithms, the authors offer a practical path for managers to balance the need for long-term consistency with the financial benefits of adaptivity. Future work may explore distributionally robust optimization to handle cases where the underlying probability distributions of demand are themselves uncertain.

Summary updated

Abstract

We consider a multiperiod stochastic capacitated facility location problem under uncertain demand and budget in each period. Using a scenario tree representation of the uncertainties, we formulate a multistage stochastic integer program to dynamically locate facilities in each period and compare it with a two-stage approach that determines the facility locations up front. In the multistage model, in each stage, a decision maker optimizes facility locations and recourse flows from open facilities to demand sites, to minimize certain risk measures of the cost associated with current facility location and shipment decisions. When the budget is also uncertain, a popular modeling framework is to prioritize the candidate sites. In the two-stage model, the priority list is decided in advance and fixed through all periods, while in the multistage model, the priority list can change adaptively. In each period, the decision maker follows the priority list to open facilities according to the realized budget, and optimizes recourse flows given the realized demand. Using expected conditional risk measures (ECRMs), we derive tight lower bounds for the gaps between the optimal objective values of risk-averse multistage models and their two-stage counterparts in both settings with and without prioritization. Moreover, we propose two approximation algorithms to efficiently solve risk-averse two-stage and multistage models without prioritization, which are asymptotically optimal under an expanding market assumption. We also design a set of super-valid inequalities for risk-averse two-stage and multistage stochastic programs with prioritization to reduce the computational time. We conduct numerical studies using both randomly generated and real-world instances with diverse sizes, to demonstrate the tightness of the analytical bounds and efficacy of the approximation algorithms and prioritization cuts.
BibTeX
@misc{yu2021value,
  author = {Xianjun Yu and Siqian Shen},
  title = {{On the Value of Multistage Risk-Averse Stochastic Facility Location With or Without Prioritization}},
  year = {2021},
  eprint = {2105.11005},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.11005},
}

Loading related content...

Figure