Optimization-Based Scenario Reduction for Data-Driven Two-Stage Stochastic Optimization

• 成果类型: Article
• 署名作者: Bertsimas, Dimitris; Mundru, Nishanth
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2265
• 发表日期: 2023
• 页码: 1343-1361
• 关键词: scenario reduction; cost function; two-stage stochastic optimization; Wasserstein Distance

摘要

We propose a novel, optimization-based method that takes into account the objective and problem structure for reducing the number of scenarios, m, needed for solving two-stage stochastic optimization problems. We develop a corresponding convex optimization-based algorithm and show that, as the number of scenarios increase, the proposed method recovers the SAA solution. We report computational results with both synthetic and real-world data sets that show that the proposed method has significantly better performance for m = 1 - 2% of n in relation to other state of the art methods (importance sampling, Monte Carlo sampling, and Wasserstein scenario reduction with squared Euclidean norm). Additionally, we propose variants of classical scenario reduction algorithms (which rely on the Euclidean norm) and show that these variants consistently outperform their traditional versions.