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 subgradient 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 iterations 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. (Source: http://freecode.com/)

References in zbMATH (referenced in 11 articles , 1 standard article )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Kim, Kibaek; Dandurand, Brian: Scalable branching on dual decomposition of stochastic mixed-integer programming problems (2022)
  2. Aravena, Ignacio; Papavasiliou, Anthony: Asynchronous Lagrangian scenario decomposition (2021)
  3. Maher, Stephen J.: Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework (2021)
  4. Bakir, Ilke; Boland, Natashia; Dandurand, Brian; Erera, Alan: Sampling scenario set partition dual bounds for multistage stochastic programs (2020)
  5. Carpentier, Pierre; Chancelier, Jean-Philippe; De Lara, Michel; Pacaud, François: Mixed spatial and temporal decompositions for large-scale multistage stochastic optimization problems (2020)
  6. Escudero, Laureano F.; Monge, Juan F.; Rodríguez-Chía, Antonio M.: On pricing-based equilibrium for network expansion planning. A multi-period bilevel approach under uncertainty (2020)
  7. Lara, Cristiana L.; Siirola, John D.; Grossmann, Ignacio E.: Electric power infrastructure planning under uncertainty: stochastic dual dynamic integer programming (SDDiP) and parallelization scheme (2020)
  8. Kim, Kibaek; Petra, Cosmin G.; Zavala, Victor M.: An asynchronous bundle-trust-region method for dual decomposition of stochastic mixed-integer programming (2019)
  9. Li, Can; Grossmann, Ignacio E.: A finite (\epsilon)-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables (2019)
  10. Munguía, Lluís-Miquel; Oxberry, Geoffrey; Rajan, Deepak; Shinano, Yuji: Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs (2019)
  11. Kim, Kibaek; Zavala, Victor M.: Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs (2018)