On Solution Quality in Stochastic Programming

Determining whether a solution is of high quality (optimal or near optimal) is a fundamental question in optimization theory and algorithms. We develop a Monte Carlo sampling-based procedure for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedure's output is a confidence interval on this gap. We present a result that justifies a single-replication procedure that only requires solving one optimization problem. This is in contrast to an existing multiple-replications procedure. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We point to variants of this procedure that require two replications instead of one, use optimal solutions, and perform better empirically.