Simulation-based confidence bounds for two-stage stochastic programs (Q1949266)

The two stage stochastic linear programming problems with recourse are considered. The reliability of a sampling-based algorithm is assessed using confidence bounds. The upper and lower one-sided confidence intervals for the minimum objective value are rigorously derived where the minimum value is obtained by the iterative sampling-based decomposition algorithm using independent sub-problems at each iteration. These results are generalized for the case in which the sub-problem instances are re-used in later iterations. The developed theory is extended to include the procedures of variance reduction and dropping of cuts. Numerical examples are provided to illustrate the reasonable performance of the derived bounds on realistic problems.