A finite branch-and-bound algorithm for two-stage stochastic integer programs (Q1881566)

This paper presents a branch-and-bound algorithm for a general class of two-stage stochastic programs with integer recourse and discrete distributions. A number of structural properties of the value function of the second-stage integer program are discovered, and are used in the analysis of the algorithm. While the algorithm does not perform explicit enumeration, it can be guaranteed finite convergence. Computational experiments on standard test problems indicate superior performance of the algorithm in comparison to those in the existing literature.