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

Wednesday, November 11, 2015: 3:57 PM
Salon F (Salt Lake Marriott Downtown at City Creek)
Kibaek Kim, Mathematics and Computer Science, Argonne National Laboratory, Argonne, IL and Victor M. Zavala, Department of Chemical and Biological Engineering, University of Wisconsin, Madison, WI

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 recovery of feasible solutions for problems without the (relative) complete recourse property. We also stabilize dual variables by solving the Lagrangian master problem with a primal-dual interior point method and provide termination criteria that guarantee finite termination of the algorithm. DSP can solve instances speci ed in C code, SMPS files (a standard format for stochastic programming), and StochJump (a Julia-based 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 large-scale unit commitment and biogas infrastructure design problems to demonstrate that the innovations provide signi cant improvements in the number of iterations and solution times.

Extended Abstract: File Uploaded
See more of this Session: Advances in Optimization III
See more of this Group/Topical: Computing and Systems Technology Division