Benders Decomposition

Overview

Stochastic Dual Dynamic Programming (SDDP) solves large multistage stochastic optimization problems by decomposing them into smaller single-stage subproblems. This decomposition is rooted in Benders decomposition (also known as the L-shaped method), which splits a monolithic problem into a master problem and subproblems connected through linear inequalities called cuts.

In the hydrothermal dispatch context, a direct formulation over all stages, scenarios, and equipment would produce an LP with millions of variables and constraints. Benders decomposition breaks this into $T$ stage subproblems, each solved independently for a given incoming state and scenario realization.

The Stage Subproblem

Each stage $t$ solves an LP of the form:

$$\underset{x_t,{\theta }_t}{\min }{c}_t^{\top }{x}_t+{\theta }_t$$

$$\text{s.t.}{A}_t{x}_t=b_t-E_t{x}_{t-1},x_t\in {\mathcal{X}}_t,{\theta }_t\ge {\underline{V}}_{t+1}(x_t)$$

where $x_{t-1}$ is the incoming state (reservoir volumes, AR inflow lags) fixed from the previous stage, $c_t^{\top }{x}_t$ captures the immediate cost (thermal generation, penalties, regularization), and ${\theta }_t$ approximates the expected future cost from stages $t+1$ through $T$.

The full LP structure — objective terms, constraint families, slack variables, and variable bounds — is described in LP Formulation.

How Cuts Approximate Future Cost

The true future cost function $V_{t+1}(x_t)$ is convex but unknown. SDDP builds a piecewise-linear lower approximation ${\underline{V}}_{t+1}$ through iterative cut generation:

$${\underline{V}}_{t+1}(x_t)=\underset{i\in \mathcal{K}}{\max }\left\{{\alpha }_i+{\pi }_i^{\top }{x}_t\right\}$$

Each cut $({\alpha }_i,{\pi }_i)$ is a supporting hyperplane derived from dual variables of the backward pass. When the stage $t+1$ subproblem is solved at a trial state ${\hat{x}}_t$ under scenario $\omega$, the optimal dual multipliers ${\pi }^{\ast }$ of the state-linking constraints yield:

• Slope: $\pi =E_{t+1}^{\top }{\pi }^{\ast }$ (sensitivity of future cost to incoming state)
• Intercept: $\alpha =V_{t+1}({\hat{x}}_t,\omega )-{\pi }^{\top }{\hat{x}}_t$

Notation note: The matrix form $E_{t+1}^{\top }{\pi }^{\ast }$ above is the standard Benders decomposition notation from the stochastic programming literature. In Cobre’s formal specs, the cut coefficients are expressed directly in terms of LP dual variables: ${\pi }_h^v={\pi }_h^{fix}$ (the storage fixing constraint dual) and ${\pi }_{h,\ell }^{lag}$ (the lag-fixing constraint dual), without explicit technology matrices. Both conventions are mathematically equivalent — the matrix form is compact for general derivations, while the direct-dual form is more practical for implementation. See Cut Coefficient Derivation below.

In the hydrothermal problem, the state variables are reservoir storage volumes $v_h$ and AR inflow lags $a_{h,\ell }$, so the cut coefficients come from the storage fixing dual ${\pi }_h^{fix}$ and the lag-fixing constraint dual ${\pi }_{h,\ell }^{lag}$.

Cut Coefficient Derivation

The key insight is how dual variables map to cut coefficients. Cobre introduces an explicit incoming-state LP variable for each state dimension, fixed to the trial value via an equality constraint:

$$v_h^{in}={\hat{v}}_h,a_{h,\ell }={\hat{a}}_{h,\ell }$$

By the LP envelope theorem, the dual of each fixing constraint equals the total derivative of the optimal objective with respect to the fixed value, accounting for all downstream effects:

For storage, the dual ${\pi }_h^{fix}$ captures contributions from the water balance, FPHA hyperplane constraints, and any generic constraints that reference incoming storage — all aggregated automatically by the LP solver through the single incoming-storage variable. No manual dual combination is required.

The cut intercept ensures the cut passes exactly through the trial point:

$${\alpha }_t=Q_t({\hat{x}}_{t-1},\omega )-\sum _h{\pi }_{t,h}^v\cdot {\hat{v}}_h-\sum _{h,\ell }{\pi }_{t,h,\ell }^{lag}\cdot {\hat{a}}_{h,\ell }$$

where $Q_t({\hat{x}}_{t-1},\omega )$ is the optimal stage $t$ objective value.

Single-Cut Aggregation

In the backward pass, each trial state is evaluated against all $|\Omega |$ scenario realizations. The resulting per-scenario cuts are aggregated into one cut per trial point using probability-weighted expectation:

$${\bar{\alpha }}_{t-1}=\sum _{\omega \in \Omega }p(\omega )\cdot {\alpha }_t(\omega )$$

$${\bar{\pi }}_{t-1,h}^v=\sum _{\omega \in \Omega }p(\omega )\cdot {\pi }_{t,h}^v(\omega )$$

$${\bar{\pi }}_{t-1,h,\ell }^{lag}=\sum _{\omega \in \Omega }p(\omega )\cdot {\pi }_{t,h,\ell }^{lag}(\omega )$$

where $p(\omega )$ is the probability of scenario $\omega$ (uniform for the fixed opening tree: $p(\omega )=1/|\Omega |$). The aggregated cut $(\bar{\alpha },{\bar{\pi }}^v,{\bar{\pi }}^{lag})$ is added to stage $t-1$’s cut pool. This single-cut formulation keeps the LP compact: after $K$ iterations the LP has $K$ cuts, regardless of the number of scenarios per iteration.

The Forward-Backward Iteration

SDDP alternates between two passes:

1. Forward pass: Simulate scenario paths from stage 1 to $T$, solving each stage LP with the current cut approximation. This produces trial states ${\hat{x}}_t$ and a statistical upper bound on optimal cost.

2. Backward pass: Traverse from stage $T$ back to stage 1. At each stage, solve subproblems for all scenario realizations at each trial state, extract dual multipliers, aggregate them into new cuts, and add each cut to the stage’s cut pool. The first-stage objective (including ${\theta }_1$) provides a deterministic lower bound.

Cuts accumulate over iterations, progressively tightening ${\underline{V}}_{t+1}$ toward the true $V_{t+1}$. The algorithm converges when the gap between lower and upper bounds falls below a tolerance.

Why the LP Formulation Matters

The quality of Benders cuts depends directly on the LP formulation:

• Recourse slacks (deficit, excess) guarantee feasibility for every scenario, ensuring duals always exist. Without relatively complete recourse, the backward pass would encounter infeasible subproblems.
• Penalty magnitudes shape the value function. Correct priority ordering ensures that cuts propagate economically meaningful signals across stages.
• State variable identification determines which dual multipliers contribute to cut coefficients. Every constraint linking the current stage to the incoming state produces a component of $\pi$.

Related Topics

• LP Formulation — complete stage subproblem: objective, constraints, penalties, and Benders cut interface
• Cut Management — cut selection, deletion, and storage strategies
• SDDP Theory — the iterative algorithm structure
• Forward-Backward Pass — detailed mechanics of the forward simulation and backward cut generation passes

Further Reading

• Pereira, M. V. F. and Pinto, L. M. V. G. (1991). “Multi-stage stochastic optimization applied to energy planning.” Mathematical Programming, 52(1-3), 359-375.
• Benders, J. F. (1962). “Partitioning procedures for solving mixed-variables programming problems.” Numerische Mathematik, 4(1), 238-252.
• Birge, J. R. and Louveaux, F. V. (2011). Introduction to Stochastic Programming. Springer, 2nd edition.
• SDDP.jl documentation: https://sddp.dev/stable/
• Cut Management (spec): ../specs/math/cut-management.md