Optimization Online


A Data-Driven Approach to Multi-Stage Stochastic Linear Optimization

Dimitris Bertsimas (dbertsim***at***mit.edu)
Shimrit Shtern (shimrits***at***technion.ac.il)
Bradley Sturt (bsturt***at***mit.edu)

Abstract: We propose a new data-driven approach for addressing multi-stage 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. As more sample paths are obtained, we prove that the optimal cost of the robust problem converges to that of the underlying stochastic problem. To the best of our knowledge, this is the first data-driven approach for multi-stage stochastic linear optimization which is asymptotically optimal 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.

Keywords: Stochastic programming. Robust optimization. Sample-path approximations

Category 1: Robust Optimization

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 11/03/2018
Entry Accepted: 11/03/2018
Entry Last Modified: 03/31/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society