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

This paper addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second-stage integer problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the current literature in that it avoids explicit enumeration of the search space while guaranteeing finite termination. Computational experiments on standard test problems indicate superior performance of the proposed algorithm in comparison to those in the existing literature.The authors wish to acknowledge partial financial support from the IBM Research Division, ExxonMobil Upstream Research Company, and the National Science Foundation under awards DMI 95-02722, DMI 00-99726, and DMI 01-15166