We develop algorithmic innovations for the dual decomposition method to address two-stage stochastic programs with mixed-integer recourse and provide a parallel software implementation that we call DSP. Our innovations include the derivation of valid inequalities that tighten Lagrangian subproblems and that allow the guaranteed recovery of feasible solutions for problems without (relative) complete recourse. We propose an interior-point cutting-plane method to solve the Lagrangian master problem, and we provide termination criteria that guarantee finite termination of the algorithm. DSP can solve instances specified in C code, SMPS files, and StochJump (a Julia-based and parallel algebraic modeling language). DSP also implements a standard Benders decomposition method and a dual decomposition method based on subgradient dual updates that we use to perform benchmarks. We present numerical results using standard SIPLIB instances and a large-scale unit commitment problem to demonstrate that the innovations provide significant improvements in the number of iterations and solution times.
Citation
Mathematics and Computer Science Division Argonne National Laboratory, 9700 South Cass Avenue, Argonne, IL 60439, USA June, 2015