SDDP Solver — Stochastic Dual Dynamic Programming in gtopt
1. Introduction
The SDDP solver in gtopt implements a Nested Benders Decomposition (NBD) algorithm — also known as Stochastic Dual Dynamic Programming (SDDP) — to decompose the multi-phase power system planning problem into smaller, per-phase LP subproblems. This enables the solver to handle long-horizon problems (many phases/stages) that would be computationally expensive or memory-intensive to solve monolithically.
The SDDP solver is an alternative to the default monolithic solver, which assembles and solves the entire LP in one shot. Both solvers produce equivalent optimal solutions; the SDDP solver trades a single large LP for multiple smaller LP solves connected by Benders optimality cuts.
When to use SDDP
| Criterion | Monolithic | SDDP |
|---|---|---|
| Number of phases | 1–3 | ≥ 2 (designed for 5+) |
| Memory footprint | Large (full LP in memory) | Smaller (per-phase LPs) |
| State variables | Not required | Reservoir volumes, battery SoC, capacity expansion |
| Convergence guarantee | Exact (single solve) | Iterative convergence (exact at optimality) |
| Parallelism | Phases solved sequentially within one LP | Scenes solved in parallel |
2. Theoretical Background
2.1 Benders Decomposition
Benders decomposition [1] is a divide-and-conquer technique for structured linear programs. Consider a two-stage LP:
$$ \min_{x, y} \quad c^T x + d^T y \quad \text{s.t.} \quad Ax + By \ge b, \; x \ge 0, \; y \in Y $$
The key insight is that for fixed first-stage decisions $\bar{y}$, the residual (second-stage) problem in $x$ can be solved independently:
$$ \min_x \; c^T x \quad \text{s.t.} \quad Ax \ge b - B\bar{y}, \; x \ge 0 $$
The dual of this residual provides sensitivity information (dual variables / reduced costs) that quantifies how changes in $\bar{y}$ affect the second-stage cost. This information is encoded as a Benders optimality cut:
$$ \alpha \ge z^*_2 + \pi^T (y - \bar{y}) $$
where $z^*_2$ is the second-stage objective value, $\pi$ are the reduced costs of the linking (state) variables, and $\alpha$ is an auxiliary variable representing the second-stage cost approximation.
The master problem iteratively refines its decisions by accumulating cuts:
$$ \min_{y, \alpha} \; d^T y + \alpha \quad \text{s.t.} \; y \in Y, \; \text{accumulated cuts}