A Data-Driven Approach to Multistage Stochastic Linear Optimization

• 成果类型: Article
• 署名作者: Bertsimas, Dimitris; Shtern, Shimrit; Sturt, Bradley
• 署名单位: Massachusetts Institute of Technology (MIT); Technion Israel Institute of Technology; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2022.4352
• 发表日期: 2023
• 页码: 51-74
• 关键词: stochastic programming; robust optimization; sample-path approximations

摘要

We propose a new data-driven approach for addressing multistage stochastic linear optimization problems with unknown distributions. The approach consists of solving a robust optimization problem that is constructed from sample paths of the underlying stochastic process. We provide asymptotic bounds on the gap between the optimal costs of the robust optimization problem and the underlying stochastic problem as more sample paths are obtained, and we characterize cases in which this gap is equal to zero. To the best of our knowledge, this is the first sample path approach for multistage stochastic linear optimization that offers asymptotic optimality guarantees when uncertainty is arbitrarily correlated across time. Finally, we develop approximation algorithms for the proposed approach by extending techniques from the robust optimization literature and demonstrate their practical value through numerical experiments on stylized data-driven inventory management problems.