Scalable Branching on Dual Decomposition of Stochastic Mixed-Integer Programming Problems

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

Article

Download

View Scalable Branching on Dual Decomposition of Stochastic Mixed-Integer Programming Problems