Mathematical Programming Computation, Volume 10, Issue 2, June 2018

Font Size:  Small  Medium  Large

Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs

Kibaek Kim, Victor M. Zavala

Abstract


We present algorithmic innovations for the dual decomposition method to address two-stage stochastic programs with mixed-integer recourse and provide an open-source software implementation that we call DSP. Our innovations include the incorporation of Benders-like cuts in a dual decomposition framework to tighten Lagrangian subproblems and aid the exclusion of infeasible first-stage solutions for problems without (relative) complete recourse. We also use an interior-point cutting- plane method with new termination criteria for solving the Lagrangian master problem. We prove that the algorithm converges to an optimal solution of the Lagrangian dual problem in a finite number of iterations, and we also prove that convergence can be achieved even if the master problem is solved suboptimally. DSP can solve instances specified in C code, SMPS files, and Julia script. DSP also implements a standard Benders decomposition method and a dual decomposition method based on subgradi- ent dual updates that we use to perform benchmarks. We present extensive numerical results using SIPLIB instances and a large unit commitment problem to demonstrate that the proposed innovations provide significant improvements in the number of iter- ations and solution times. The software reviewed as part of this submission has been given the Digital Object Identifier (DOI) https://doi.org/10.5281/zenodo.998971.


Full Text: PDF

mpc footer
© MPS 2008-2018