Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees

Wei Zhang (), Kai Wang (), Alexandre Jacquillat () and Shuaian Wang ()
Additional contact information
Wei Zhang: School of Vehicle and Mobility, Tsinghua University, Beijing 100084, China; Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong SAR, China
Kai Wang: School of Vehicle and Mobility, Tsinghua University, Beijing 100084, China
Alexandre Jacquillat: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Shuaian Wang: Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong SAR, China

INFORMS Journal on Computing, 2023, vol. 35, issue 4, 886-908

Abstract: Stochastic programming involves large-scale optimization with exponentially many scenarios. This paper proposes an optimization-based scenario reduction approach to generate high-quality solutions and tight lower bounds by only solving small-scale instances, with a limited number of scenarios. First, we formulate a scenario subset selection model that optimizes the recourse approximation over a pool of solutions. We provide a theoretical justification of our formulation, and a tailored heuristic to solve it. Second, we propose a scenario assortment optimization approach to compute a lower bound—hence, an optimality gap—by relaxing nonanticipativity constraints across scenario “bundles.” To solve it, we design a new column-evaluation-and-generation algorithm, which provides a generalizable method for optimization problems featuring many decision variables and hard-to-estimate objective parameters. We test our approach on stochastic programs with continuous and mixed-integer recourse. Results show that (i) our scenario reduction method dominates scenario reduction benchmarks, (ii) our scenario assortment optimization, combined with column-evaluation-and-generation, yields tight lower bounds, and (iii) our overall approach results in stronger solutions, tighter lower bounds, and faster computational times than state-of-the-art stochastic programming algorithms.

Keywords: stochastic programming; scenario reduction; column evaluation and generation (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.1295 (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:35:y:2023:i:4:p:886-908

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 ().