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

Zavala, V. M., University of Wisconsin-Madison

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 guaranteefinite termination of the algorithm. DSP can solve instances specied in C code, SMPSfiles (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 signicant improvements in the number of iterations and solution times.


This paper has an Extended Abstract file available; you must purchase the conference proceedings to access it.


Do you already own this?



AIChE Members $150.00
AIChE Graduate Student Members Free
AIChE Undergraduate Student Members Free
Non-Members $225.00