The Sample Average Approximation Method for Stochastic Discrete Optimization
Top Cited Papers
- 1 January 2002
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 12 (2) , 479-502
- https://doi.org/10.1137/s1052623499363220
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.Keywords
This publication has 12 references indexed in Scilit:
- A Simulated Annealing Algorithm with Constant Temperature for Discrete Stochastic OptimizationManagement Science, 1999
- Monte Carlo bounding techniques for determining solution quality in stochastic programsOperations Research Letters, 1999
- On Optimal Allocation of Indivisibles Under UncertaintyOperations Research, 1998
- Optimal allocation of simulation experiments in discrete stochastic optimization and approximative algorithmsEuropean Journal of Operational Research, 1997
- Simulated Annealing for noisy cost functionsJournal of Global Optimization, 1996
- Confidence sets for discrete stochastic optimizationAnnals of Operations Research, 1995
- Probabilistic Search with OverridesThe Annals of Applied Probability, 1995
- Asymptotic analysis of stochastic programsAnnals of Operations Research, 1991
- Simulated annealing with noisy or imprecise energy measurementsJournal of Optimization Theory and Applications, 1989
- Algorithm AS 66: The Normal IntegralJournal of the Royal Statistical Society Series C: Applied Statistics, 1973