Stage Subproblem LP Formulation

Overview

At each stage of the SDDP algorithm, the dispatcher solves a linear program (LP) that models the power system for that time period. This LP is the fundamental computational unit of the solver: the forward pass executes it once per stage to simulate the policy, and the backward pass executes it once per stage per scenario to generate Benders cuts.

Understanding the LP structure is important because it directly shapes the quality of the cuts and the economic signals propagated across stages. A well-structured LP ensures that cuts carry meaningful marginal water values and that every scenario is feasible.

Cost and Penalty Taxonomy

The objective function combines four types of costs. The distinction matters because each type serves a different algorithmic role.

Resource Costs

Resource costs represent actual operating expenditures with economic meaning:

Cost	Symbol	Units	Role
Thermal generation	$c_{j, s}^{t h}$	$/MWh	Fuel cost, typically 50–500
Contract dispatch	$c_{c}^{c t r}$	$/MWh	Positive for imports, negative for exports

Category 1: Recourse Slacks

These penalty terms guarantee that every LP is feasible regardless of the inflow scenario. Without them, the backward pass could encounter infeasible subproblems, making cut generation impossible.

Penalty	Symbol	Units	Purpose
Load deficit	$c_{b, s}^{d e f}$	$/MWh	Unserved energy (piecewise, 1,000–10,000)
Excess generation	$c_{b}^{e x c}$	$/MWh	Absorbs uncontrollable surplus (0.001–0.1)

Category 2: Constraint Violation Penalties

These provide soft enforcement of physical constraints that may be impossible to satisfy under extreme conditions. They must be high enough to propagate penalty signals into the future cost function and influence reservoir decisions multiple stages ahead.

Penalty	Symbol	Violated Constraint
Storage below minimum	$c_{h}^{s v -}$	$v_{h} \geq \underline{V}_{h}$
Filling target shortfall	$c_{h}^{f i ll}$	$v_{h} \geq \underline{V}_{h}$ (terminal)
Turbined flow minimum	$c_{h}^{t v -}$	$q_{h, k} \geq \underline{Q}_{h}$
Outflow minimum/maximum	$c_{h}^{o v \pm}$	$\underline{O}_{h} \leq o_{h, k} \leq \overset{ˉ}{O}_{h}$
Generation minimum	$c_{h}^{gv -}$	$g_{h, k} \geq \underline{G}_{h}$

Category 3: Regularization Costs

Very small costs (2–3 orders of magnitude below economic costs) that break degeneracy and guide the solver toward physically preferred solutions when the LP is otherwise indifferent:

Cost	Symbol	Purpose
Spillage	$c_{h}^{s p i ll}$	Prefer turbining over spilling
FPHA turbined flow	$c_{h}^{f p ha}$	Prevent degenerate FPHA solutions
Exchange	$c_{ℓ}^{e x c h}$	Prevent unnecessary power flows

Priority Ordering

The ordering must be maintained to ensure correct economic signals:

$c^{f i ll} > c^{s v -} > c^{d e f} > c^{t v -}, c^{o v \pm}, c^{gv -} > c^{t h}, c^{c t r} ≫ c^{s p i ll}, c^{f p ha}, c^{e x c h}$

Filling a dead reservoir (dam safety) has the highest priority; load shedding ranks above generation costs; regularization terms are negligible compared to any economic quantity.

The Stage Subproblem LP

The complete objective minimizes total cost over all load blocks $k \in K$ :

$min k \in K \sum τ_{k} [j \sum c_{j}^{t h} g_{j, k} + b \sum s \sum c_{b, s}^{d e f} δ_{b, k, s} + b \sum c_{b}^{e x c} ϵ_{b, k} + h \sum c_{h}^{s p i ll} s_{h, k} + other violation terms]$

$+ h \sum [c_{h}^{s v -} σ_{h}^{v -} + c_{h}^{f i ll} σ_{h}^{f i ll}] + θ$

Storage violation penalties ( $σ_{h}^{v -}$ , $σ_{h}^{f i ll}$ ) appear outside the block sum because they apply to end-of-stage storage (hm³), not per-block flow rates.

Key Constraint Families

Load Balance

For each bus $b$ and block $k$ , supply must meet demand. Hydro generation, thermal dispatch, imports, and transmission flows contribute to supply; deficit and excess slack variables ensure feasibility:

$h \in H_{b} \sum g_{h, k} + j \in T_{b} \sum g_{j, k} + (flows in) - (flows out) + s \sum δ_{b, k, s} - ϵ_{b, k} = D_{b, k}$

Hydro Water Balance

End-of-stage storage equals incoming storage plus net inflows and minus all outflows, scaled by the time conversion factor $ζ = 0.0036 \times \sum_{k} τ_{k}$ :

$v_{h} = v_{h}^{in} + ζ [a_{h} + k \sum w_{k} (i \in U_{h} \sum (q_{i, k} + s_{i, k}) - q_{h, k} - s_{h, k} - e_{h, k})]$

where $a_{h}$ is the incremental inflow from the PAR(p) model and $v_{h}^{in}$ is the incoming storage.

State-Fixing Constraints and the Benders Interface

A critical design choice is the introduction of explicit incoming-state LP variables $v_{h}^{in}$ and $a_{h, ℓ}$ , each fixed to the trial value via an equality constraint:

$v_{h}^{in} = \overset{v}{^}_{h}, a_{h, ℓ} = \overset{a}{^}_{h, ℓ}$

The dual of each fixing constraint is the cut coefficient for that state dimension. This “fishing constraint” technique collects all sensitivity information into a single dual value per state variable — the LP solver automatically propagates contributions from all downstream constraints (water balance, FPHA, generic constraints) through the incoming-state variable. The result appears in the stage LP as:

$θ \geq α_{i} + h \sum π_{i, h}^{v} \cdot v_{h} + h, ℓ \sum π_{i, h, ℓ}^{l a g} \cdot a_{h, ℓ}$

where $π_{i, h}^{v}$ is the dual of the storage fixing constraint and $π_{i, h, ℓ}^{l a g}$ is the dual of the lag fixing constraint. Each new Benders cut is derived from these duals after each backward-pass solve.

Hydro Production Models

Two production models are available during training:

Constant productivity: A linear equality linking generation to turbined flow:

$g_{h, k} = ρ_{h} \cdot q_{h, k}$

where $ρ_{h}$ (MW per m³/s) depends on turbine efficiency and reference head. Simple and fast.

FPHA (piecewise-linear): A set of $M$ linear hyperplanes forming a concave upper bound on generation as a function of storage and flow:

$g_{h, k} \leq γ_{0}^{m} + γ_{v}^{m} \cdot v_{h}^{a vg} + γ_{q}^{m} \cdot q_{h, k} + γ_{s}^{m} \cdot s_{h, k}$

where $v_{h}^{a vg} = (v_{h}^{in} + v_{h}) /2$ is average stage storage. FPHA captures head variation and the effect of spillage on tailrace level, at the cost of more constraints per hydro.

Cobre Methodology Reference