Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs
- We present algorithmic innovations for the dual decomposition method to address two-stage stochastic programs with mixed-integer recourse and provide an open-source software implementation that we call DSP. Our innovations include the incorporation of Benders-like cuts in a dual decomposition framework to tighten Lagrangian subproblems and aid the exclusion of infeasible first-stage solutions for problems without (relative) complete recourse. We also use an interior-point cutting- plane method with new termination criteria for solving the Lagrangian master problem. We prove that the algorithm converges to an optimal solution of the Lagrangian dual problem in a finite number of iterations, and we also prove that convergence can be achieved even if the master problem is solved suboptimally. DSP can solve instances specified in C code, SMPS files, and Julia script. DSP also implements a standard Benders decomposition method and a dual decomposition method based on subgradi- ent dual updates that we use to perform benchmarks. We present extensive numerical results using SIPLIB instances and a large unit commitment problem to demonstrate that the proposed innovations provide significant improvements in the number of iter- ations and solution times. The software reviewed as part of this submission has been given the Digital Object Identifier (DOI) https://doi.org/10.5281/zenodo.998971.
Metadaten| Author: | Kibaek Kim, Victor M. Zavala |
|---|
| DOI: | https://doi.org/10.1007/s12532-017-0128-z |
|---|
| ISSN: | 1867-2949 |
|---|
| Parent Title (English): | Mathematical Programming Computation |
|---|
| Publisher: | Springer Science and Business Media LLC |
|---|
| Document Type: | Article |
|---|
| Language: | English |
|---|
| Year of Completion: | 2017 |
|---|
| Tag: | Software; Theoretical Computer Science |
|---|
| Volume: | 10 |
|---|
| Issue: | 2 |
|---|
| Page Number: | 42 |
|---|
| First Page: | 225 |
|---|
| Last Page: | 266 |
|---|
| Mathematical Programming Computation : | MPC 2018 - Issue 2 |
|---|