Sample intelligence-based progressive hedging algorithms for the stochastic capacitated reliable facility location problem

Nezir Aydin*, Alper Murat, Boris S. Mordukhovich

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Selecting facility locations requires significant investment to anticipate and prepare for disruptive events like earthquakes, floods, or labor strikes. In practice, location choices account for facility capacities, which often cannot change during disruptions. When a facility fails, demand transfers to others only if spare capacity exists. Thus, capacitated reliable facility location problems (CRFLP) under uncertainty are more complex than uncapacitated versions. To manage uncertainty and decide effectively, stochastic programming (SP) methods are often employed. Two commonly used SP methods are approximation methods, i.e., Sample Average Approximation (SAA), and decomposition methods, i.e., Progressive Hedging Algorithm (PHA). SAA needs large sample sizes for performance guarantee and turn into computationally intractable. On the other hand, PHA, as an exact method for convex problems, suffers from the need to iteratively solve numerous sub-problems which are computationally costly. In this paper, we developed two novel algorithms integrating SAA and PHA for solving the CRFLP under uncertainty. The developed methods are innovative in that they blend the complementary aspects of PHA and SAA in terms of exactness and computational efficiency, respectively. Further, the developed methods are practical in that they allow the specialist to adjust the tradeoff between the exactness and speed of attaining a solution. We present the effectiveness of the developed integrated approaches, Sampling Based Progressive Hedging Algorithm (SBPHA) and Discarding SBPHA (d-SBPHA), over the pure strategies (i.e. SAA). The validation of the methods is demonstrated through two-stage stochastic CRFLP. Promising results are attained for CRFLP, and the method has great potential to be generalized for SP problems.

Original languageEnglish
Article number135
JournalArtificial Intelligence Review
Volume57
Issue number6
DOIs
Publication statusPublished - Jun 2024

Keywords

  • Capacitated reliable facility location
  • Hybrid algorithm
  • Progressive hedging
  • Sample average approximation
  • Stochastic programming

Fingerprint

Dive into the research topics of 'Sample intelligence-based progressive hedging algorithms for the stochastic capacitated reliable facility location problem'. Together they form a unique fingerprint.

Cite this