Optimization Online


A Data-Driven Approach for Multi-Stage Linear Optimization

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

Abstract: We present a data-driven approach for solving multi-stage stochastic linear optimization problems in which uncertainty is correlated across stages. The proposed approach chooses decision rules which perform best when averaging over sample paths of a stochastic process; however, to avoid overfitting, we allow an adversary to slightly perturb each sample path. We show that this robust approach converges to the underlying stochastic problem as more data is obtained, even when the uncertainty is arbitrarily correlated across stages. Furthermore, we develop scalable approximation algorithms, which apply to problems with both continuous and integer decisions, by leveraging techniques from robust optimization. In computational experiments on stochastic inventory management problems, the proposed methods are practically tractable and produce decisions with near-optimal average performance. As a by-product of the aforementioned contributions, we also present new results and limitations of distributionally robust optimization with Wasserstein ambiguity sets.

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: 07/31/2019

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