# DSP — Decompositions for Structured Programming¶

DSP is an open-source and parallel package that implements decomposition
methods for **structured mixed-integer linear programming problems**.
These are structured optimization problems in the following form:

\[\begin{split}\min \quad & c^T x + \sum_{s=1}^S q_s^T y_s \\
\text{s.t.} \quad
& A x = b \\
& T_s x + W_s y_s = h_s \quad \forall s = 1, .., S \\
& \text{mixed-integer } x, y_s\end{split}\]

Note that 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.

## Algorithms in DSP¶

DSP provides **serial** and **parallel** implementations for the four types of algorithms.

### Extensive Form Solver¶

### Dual Decomposition¶

### Dantzig-Wolfe Decomposition¶

### Benders Decomposition¶

Dual decomposition (with subgradient method and several bundle methods) with

**branch-and-bound**procedureBenders decomposition