# 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:

- distributionally robust optimization problem (with Wasserstein ambiguity set)
- 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 DSPopt.jl). For generic optimization problems, each block can be specified by mps-dec files or our C API functions (or Julia package DSPopt.jl).

NOTE: A

distributionally robustvariant of dual decomposition is available for the problems given in SMPS files and optionally with`.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

### Integer Benders Decomposition

This solves the integer Benders decomposition of stochastic programming problems with the lower bound initialized by the dual decomposition. Integer Benders decomposition runs when the first stage is a pure-binary program and the second stage is a mixed-integer program.

NOTE: A

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

file.Note: When the first stage is not a pure-binary program, 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.