We present a scalable branching method for the dual decomposition of stochastic mixed-integer programming. Our new branching method is based on the branching method proposed by Caro e and Schultz that creates branching disjunctions on first-stage variables only. We propose improvements to the process for creating branching disjunctions, including 1) branching on the optimal solutions of the Dantzig-Wolfe reformulation of the restricted master problem; and 2) using a more comprehensive (yet simple) measure for the dispersions associated with subproblem solution infeasibility. We prove that the proposed branching process leads to an algorithm that terminates finitely with optimal solutions feasible within a tolerance. We have implemented our new branching method, as well as the Caro e-Schultz method and a branch-and-price method. Using SIPLIB test instances, we present extensive numerical results to demonstrate that the proposed branching method yields significant reductions in the number of node subproblems and solution times.
Citation
Argonne National Laboratory, 10/2018