Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees
提出基于优化的情景缩减方法，通过求解小规模实例生成高质量解和紧下界，并设计列评估与生成算法，在连续和混合整数随机规划中优于现有算法。
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 .