# What is DSP?

DSP (**D**ecomposition of **S**tructured **P**rograms) is an open-source and parallel package that implements decomposition
methods for **structured mixed-integer linear programming problems**.

Examples of the structured programming problem include:

- stochastic programming problem
- long-term planning problem
- network optimization problem

## Algorithms in DSP

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

### Dantzig-Wolfe Decomposition

This solves the dual of the dual decomposition. The key difference from the dual decomposition is the implementation of branch-and-bound method on top of the decomposition, which allows to find a global optiaml solution.

For more technical details, please refer the following papers.

- Kibaek Kim and Brian Dandurand. "Scalable Branching on Dual Decomposition of Stochastic Mixed-Integer Programming Problems" Mathematical Programming Computation (to appear), 2020
- Kibaek Kim, Audun Botterud, and Feng Qiu. "Temporal Decomposition for Improved Unit Commitment in Power System Production Cost Modeling" IEEE Transactions on Power Systems. 2018

### Dual Decomposition

This solves the Lagrangian relaxation of the constraints that couple blocks of the structure. Hence, the algorithm finds a Lagrangian dual bound that can be strictly lower than the optimal objective value for nonconvex problems (e.g., mixed-integer programs). For two-stage stochastic programs, each block is represented by a scenario subproblem. Stochastic programs can be read from SMPS files or our C API functions (or Julia package DSP.jl). For generic optimization problems, each block can be specified by mps-dec files or our C API functions (or Julia package DSP.jl).

NOTE: A

distributionally robustvariant of dual decomposition is available for the problems given in SMPS files and`.dro`

file.

For more technical details, please refer the following papers.

- Kibaek Kim. "Dual Decomposition of Two-Stage Distributionally Robust Mixed-Integer Programming under the Wasserstein Ambiguity Set" Optimization Online, 2020
- Kibaek Kim, Cosmin G. Petra, and Victor M. Zavala. "An Asynchronous Bundle-Trust-Region Method for Dual Decomposition of Stochastic Mixed-Integer Programming" SIAM Journal on Optimization, 2019
- Kibaek Kim, Mihai Anitescu, and Victor M. Zavala. "An Asynchronous Decomposition Algorithm for Security Constrained Unit Commitment under Contingency Events" Proceedings in Power System Computation Conference, 2018
- Kibaek Kim and Victor M. Zavala. "Algorithmic Innovations and Software for the Dual Decomposition Method applied to Stochastic Mixed-Integer Programs" Mathematical Programming Computation, 2017

### Benders Decomposition

This solves the Benders decomposition of stochastic programming problems with the lower bound initialized by the dual decomposition.

Note: Any second-stage integer variables will be relaxed.

Note: This algorithm requires SCIP and is available only for stochastic programs.

### Extensive Form Solver

This reformulates the problem into one large optimization problem and uses available external solver. Parallel computing is available only through the external solver (i.e., multi-threading).

Note: There is no MPI parallelism for this algorithm.