Argonne National Laboratory

Algorithmic Innovations and Software for the Dual Decomposition Method Applied to Stochastic Mixed-Integer Programs

TitleAlgorithmic Innovations and Software for the Dual Decomposition Method Applied to Stochastic Mixed-Integer Programs
Publication TypeJournal Article
Year of Publication2015
AuthorsKim, K, Zavala, VM
JournalMathematical Programming Computation
Date Published11/2015
Other NumbersANL/MCS-P5357-0615
AbstractWe 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.  
DOI10.13140/RG.2.1.2062.3202
PDFhttp://www.mcs.anl.gov/papers/P5357-0615.pdf