TY - JOUR
T1 - The sample average approximation method for stochastic discrete optimization
AU - Kleywegt, Anton J.
AU - Shapiro, Alexander
AU - Homem-De-Mello, Tito
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
KW - Discrete optimization
KW - Large deviations theory
KW - Law of large numbers
KW - Monte Carlo sampling
KW - Sample average approximation
KW - Stochastic knapsack problem
KW - Stochastic programming
KW - Stopping rules
UR - http://www.scopus.com/inward/record.url?scp=0036013019&partnerID=8YFLogxK
U2 - 10.1137/S1052623499363220
DO - 10.1137/S1052623499363220
M3 - Article
AN - SCOPUS:0036013019
SN - 1052-6234
VL - 12
SP - 479
EP - 502
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 2
ER -