DSP is an open-source and parallel package that implements decomposition methods for structured mixed-integer programming problems. These are structured optimization problems in the following form:
minimize c^T x + \sum_{s=1}^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 Solution Methods:
- Extensive form solver (global solver)
- Serial/parallel dual decomposition (dual bounding solver)
- Serial/parallel Dantzig-Wolfe decomposition (global solver)
- Serial/parallel Benders decomposition
Problem Types:
- Two-stage stochastic mixed-integer linear programs
- Distributionally robust stochastic mixed-integer linear programs
- Structured mixed-integer linear programs
Problem Input Formats:
- SMPS file format for stochastic programs (
.dro
optionally for distributionally robust) - MPS and DEC files for generic block-structured optimization problems
- Julia modeling package DSPopt.jl
git clone --recursive https://github.com/Argonne-National-Laboratory/DSP.git
- Kibaek Kim, Mathematics and Computer Science Division, Argonne National Laboratory.
- Victor M. Zavala, Department of Chemical and Biological Engineering, University of Wisconsin-Madison.
- Christian Tjandraatmadja, Google Research.
- Yingqiu Zhang, Industrial and Systems Engineering, Virginia Tech.
- Geunyeong Byeon, Industrial Engineering, Arizona State University.
- Hideaki Nakao, Mathematics and Computer Science Division, Argonne National Laboratory.
The contributors are listed in chronological order (first-come first-listed).
- Kibaek Kim. "Dual Decomposition of Two-Stage Distributionally Robust Mixed-Integer Programming under the Wasserstein Ambiguity Set" Optimization Online, 2020
- Kibaek Kim and Briand Dandurand. "Scalable Branching on Dual Decomposition of Stochastic Mixed-Integer Programming Problems" Mathematical Programming Computation 14(1), 2022
- Kibaek Kim, Cosmin Petra, and Victor Zavala. "An Asynchronous Bundle-Trust-Region Method for Dual Decomposition of Stochastic Mixed-Integer Programming" SIAM Journal on Optimization 29(1), 2019
- Kibaek Kim and Victor M. Zavala. "Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs" Mathematical Programming Computation 10(2), 2017
This material is based upon work supported by the U.S. Department of Energy, Office of Science, under contract number DE-AC02-06CH11357.