Optimization Online


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

Kibaek Kim (kimk***at***anl.gov)
Victor M. Zavala (victor.zavala***at***wisc.edu)

Abstract: 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 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.

Keywords: stochastic mixed-integer programming; decomposition; parallel; large-scale; open-source software

Category 1: Stochastic Programming

Category 2: Optimization Software and Modeling Systems

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: Mathematics and Computer Science Division Argonne National Laboratory, 9700 South Cass Avenue, Argonne, IL 60439, USA June, 2015

Download: [PDF]

Entry Submitted: 06/12/2015
Entry Accepted: 06/12/2015
Entry Last Modified: 09/15/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society