Simulation-Based Confidence Bounds for Two-Stage Stochastic Programs

P. W. Glynn and G. Infanger

Mathematical Programming, Volume 138, Issue 1-2, pp 15-42, (April 2013)

This paper provides a rigorous asymptotic analysis and justification of upper and lower confidence bounds proposed by Dantzig and Infanger (1995) for an iterative sampling-based decomposition algorithm, introduced by Dantzig and Glynn (1990) and Infanger (1992), for solving two-stage stochastic programs. The paper provides confidence bounds in the presence of both independent sampling across iterations, and when common samples are used across different iterations. Confidence bounds for sampleaverage approximation then follow as a special case. Extensions of the theory to cover use of variance reduction and the dropping of cuts are also presented. An extensive empirical investigation of the performance of these bounds establishes that the bounds perform reasonably on realistic problems.