Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees
INFORMS Journal on Computing · 2023-07 · 35 (4) · 886-908
DOI: 10.1287/ijoc.2023.1295 ↗Kurz gefasst
Fachartikel in der Zeitschrift INFORMS Journal on Computing, 2023-07. Verfasst von Wei Zhang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 46-mal zitiert (Crossref) und nennt 58 Literaturangaben.
Abstract (Originalsprache)
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. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2023.1295 .
Zitieren
APA
Zhang, W., Wang, K., Jacquillat, A., & Wang, S. (2023). Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees. INFORMS Journal on Computing, 35(4), 886-908. https://doi.org/10.1287/ijoc.2023.1295
Vancouver
Zhang W, Wang K, Jacquillat A, Wang S. Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees. INFORMS Journal on Computing. 2023;35(4):886-908. doi:10.1287/ijoc.2023.1295
BibTeX
@article{Zhang2023,
author = {Zhang, Wei and Wang, Kai and Jacquillat, Alexandre and Wang, Shuaian},
title = {Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees},
journal = {INFORMS Journal on Computing},
year = {2023},
volume = {35},
number = {4},
pages = {886--908},
doi = {10.1287/ijoc.2023.1295}
}
EUVIMED