A Stochastic Benders Decomposition Scheme for Large-Scale Stochastic Network Design

Dimitris Bertsimas (), Ryan Cory-Wright (), Jean Pauphilet () and Periklis Petridis ()
Additional contact information
Dimitris Bertsimas: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Ryan Cory-Wright: Department of Analytics, Marketing and Operations, Imperial College Business School, London SW7 2AZ, United Kingdom
Jean Pauphilet: Management Science and Operations, London Business School, London NW1 4SA, United Kingdom
Periklis Petridis: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

INFORMS Journal on Computing, 2025, vol. 37, issue 5, 1163-1181

Abstract: Network design problems involve constructing edges in a transportation or supply chain network to minimize construction and daily operational costs. We study a stochastic version where operational costs are uncertain because of fluctuating demand and estimated as a sample average from historical data. This problem is computationally challenging, and instances with as few as 100 nodes often cannot be solved to optimality using current decomposition techniques. We propose a stochastic variant of Benders decomposition that mitigates the high computational cost of generating each cut by sampling a subset of the data at each iteration and nonetheless, generates deterministically valid cuts, via a dual averaging technique, rather than the probabilistically valid cuts frequently proposed in the stochastic optimization literature. We implement both single-cut and multicut variants of this Benders decomposition as well as a variant that uses clustering of the historical scenarios. To our knowledge, this is the first single-tree implementation of Benders decomposition that facilitates sampling. On instances with 100–200 nodes and relatively complete recourse, our algorithm achieves 5%–7% optimality gaps compared with 16%–27% for deterministic Benders schemes, and it scales to instances with 700 nodes and 50 commodities within hours. Beyond network design, our strategy could be adapted to generic two-stage stochastic mixed-integer optimization problems where second-stage costs are estimated via a sample average.

Keywords: generalized Benders decomposition; network design; stochastic integer optimization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0074 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:5:p:1163-1181

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().