The sample average approximation method for stochastic discrete optimization

Anton J. Kleywegt, Alexander Shapiro, Tito Homem-De-Mello

Research output: Contribution to journalArticlepeer-review

1076 Scopus citations

Abstract

In this paper we study a Monte Carlo simulation-based approach to stochastic discrete optimization problems. The basic idea of such methods is that a random sample is generated and the expected value function is approximated by the corresponding sample average function. The obtained sample average optimization problem is solved, and the procedure is repeated several times until a stopping criterion is satisfied. We discuss convergence rates, stopping rules, and computational complexity of this procedure and present a numerical example for the stochastic knapsack problem.

Original languageEnglish
Pages (from-to)479-502
Number of pages24
JournalSIAM Journal on Optimization
Volume12
Issue number2
DOIs
StatePublished - 2002
Externally publishedYes

Keywords

  • Discrete optimization
  • Large deviations theory
  • Law of large numbers
  • Monte Carlo sampling
  • Sample average approximation
  • Stochastic knapsack problem
  • Stochastic programming
  • Stopping rules

Fingerprint

Dive into the research topics of 'The sample average approximation method for stochastic discrete optimization'. Together they form a unique fingerprint.

Cite this