DSP is a parallel and open-source software package that implements decomposition methods for solving stochastic mixed-integer programming (SMIP) problems. These are structured optimization problems considering uncertain scenario realizations s with probabilities p_s in the following form:
    minimize   c^T x + \sum_{s=1}^S p_s q_s^T y_s
subject to   A x                              = b
T_s x +                    W_s y_s = h_s for s = 1, .., S
some x, y_s are integers

where x and y_s are decision variable vectors with dimensions n_1 and n_2, respectively, A, T_s and W_s are matrices of dimensions m_1 by n_1, m_2 by n_1 and m_2 by n_2, respectively, and c, q_s, b, and h_s are vectors of appropriate dimensions.

DSP can solve models in SMPS and StochJuMP formats on distributed computing systems. DSP is maintained by Kibaek Kim and Victor M. Zavala at Argonne's Mathematics and Computer Science Division.

Features

The methods implemented in DSP are:
• Dual decomposition methods
• Interior-point cutting-plane method with Benders procedure (see [1])
• Cutting-plane method
• Standard Benders decomposition method
• Extensive form method
The features available in DSP are:
• Interfaces for the StochJuMP.jl package (a scalable algebraic modeling package for stochastic programming in Julia)
• Object-oriented design that allows users to easily customize and extend DSP with their own methods

Credits

DSP has been developed and is maintained by:
• Kibaek Kim, Mathematics and Computer Science Division, Argonne National Laboratory.
• Victor M. Zavala, Mathematics and Computer Science Division, Argonne National Laboratory.

References

1. Kibaek Kim and Victor M. Zavala. "Algorithmic Innovations and Software for the Dual Decomposition Method applied to Stochastic Mixed-Integer Programs" Optimization Online, 2015 [pdf]

Acknowledgements

This material is based upon work supported by the U.S. Department of Energy, Office of Science, under contract number DE-AC02-06CH11357. We gratefully acknowledge the computing resources provided on Blues, a high-performance computing cluster operated by the Laboratory Computing Resource Center at Argonne National Laboratory. We thank E. Michael Gertz and Stephen Wright for providing the OOQP software package.