Skip to content

An open-source parallel optimization solver for structured mixed-integer programming

License

Notifications You must be signed in to change notification settings

Argonne-National-Laboratory/DSP

Repository files navigation

DSP

Release: GitHub tag (latest SemVer) DOI

Documentation: Documentation Status

Status: Build Status codecov


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

Installation

git clone --recursive https://github.com/Argonne-National-Laboratory/DSP.git

Contributors

  • 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).

Key Publications

Acknowledgements

This material is based upon work supported by the U.S. Department of Energy, Office of Science, under contract number DE-AC02-06CH11357.