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

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.