TY - JOUR
T1 - Monte Carlo bounding techniques for determining solution quality in stochastic programs
AU - Mak, Wai Kei
AU - Morton, David P.
AU - Wood, R. Kevin
N1 - Funding Information:
David Morton's research was partially supported by the Summer Research Assignment program at The University of Texas at Austin and by the National Science Foundation through grant DMI-9702217. Kevin Wood's research was supported by the Air Force Office of Scientific Research and the Office of Naval Research. The authors thank John Birge, Julia Higle, and Suvrajeet Sen for valuable discussions, thank Andrzej Ruszczyński and Artur Świetanowski for access to their regularized decomposition code and thank the associate editor, David Goldsman, for many helpful comments.
PY - 1999/2
Y1 - 1999/2
N2 - A stochastic program SP with solution value z* can be approximately solved by sampling n realizations of the program's stochastic parameters, and by solving the resulting `approximating problem' for (x*n, z*n). We show that, in expectation, z*n is a lower bound on z* and that this bound monotonically improves as n increases. The first result is used to construct confidence intervals on the optimality gap for any candidate solution x to SP, e.g., x = x*n. A sampling procedure based on common random numbers ensures nonnegative gap estimates and provides significant variance reduction over naive sampling on four test problems.
AB - A stochastic program SP with solution value z* can be approximately solved by sampling n realizations of the program's stochastic parameters, and by solving the resulting `approximating problem' for (x*n, z*n). We show that, in expectation, z*n is a lower bound on z* and that this bound monotonically improves as n increases. The first result is used to construct confidence intervals on the optimality gap for any candidate solution x to SP, e.g., x = x*n. A sampling procedure based on common random numbers ensures nonnegative gap estimates and provides significant variance reduction over naive sampling on four test problems.
UR - http://www.scopus.com/inward/record.url?scp=0032632474&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032632474&partnerID=8YFLogxK
U2 - 10.1016/S0167-6377(98)00054-6
DO - 10.1016/S0167-6377(98)00054-6
M3 - Article
AN - SCOPUS:0032632474
SN - 0167-6377
VL - 24
SP - 47
EP - 56
JO - Operations Research Letters
JF - Operations Research Letters
IS - 1
ER -