A branch-and-cut algorithm for two-stage stochastic mixed-binary programs with continuous first-stage variables

摘要

This paper presents a branch-and-cut method for two-stage Stochastic Mixed-Integer Programming (SMIP) problems with continuous first-stage variables. This method is derived based on disjunctive decomposition (D{sup}2) for SMIP, an approach in which disjunctive programming is used to derive valid inequalities for SMIP. The novelty of the proposed method derives from branching on the first-stage continuous domain while the branch-and-bound process is guided by the disjunction variables in the second-stage. Finite convergence of the algorithm for mixed-binary second-stage is established and a numerical example to illustrate the new method is given.