A stochastic program SP with solution value z* can be approximately solved
by sampling n realizations of the program's stochastic parameters, and by s
olving 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 monotoni
cally improves as n increases. The first result is used to construct confid
ence intervals on the optimality gap for any candidate solution (x) over ca
p to SP, e.g., (x) over cap=x(n)*. A sampling procedure based on common ran
dom numbers ensures nonnegative gap estimates and provides significant vari
ance reduction over naive sampling on four test problems. (C) 1999 Elsevier
Science B.V. All rights reserved.