A combined deterministic and sampling-based sequential bounding method for stochastic programming

We develop an algorithm for two-stage stochastic programming with a convex second stage program and with uncertainty in the right-hand side. The algorithm draws on techniques from bounding and approximation methods as well as sampling-based approaches. In particular, we sequentially refine a partition of the support of the random vector and, through Jensen's inequality, generate deterministically valid lower bounds on the optimal objective function value. An upper bound estimator is formed through a stratified Monte Carlo sampling procedure that includes the use of a control variate variance reduction scheme. The algorithm lends itself to a stopping rule theory that ensures an asymptotically valid confidence interval for the quality of the proposed solution. Computational results illustrate our approach.