Abstract
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.