Toy Four-Reservoir SDDP Walkthrough

Purpose

This chapter extends the single-reservoir walkthrough in Toy Single-Reservoir Walkthrough to a four-reservoir, four-bus system, still using a 0-order (seasonal-sampling) inflow model. The chapter demonstrates two phenomena that the single-reservoir case cannot exhibit:

• Multi-dimensional cuts. The cut becomes a hyperplane with one storage coefficient per reservoir: the probability-weighted reduced cost of that reservoir’s pinned incoming-storage column.
• Per-bus dispatch with independent supply. Each bus carries its own demand and is served by its local hydro and a local thermal; the LP solves the regional dispatches simultaneously inside one stage problem.

Novomodelo’s repository ships a reference case at examples/4ree/ modelling the four-region Brazilian interconnected system (SUDESTE, SUL, NORDESTE, NORTE) over 12 monthly stages (January to December 2015), with 126 thermals, five buses and five transmission lines. The fifth bus, NOFICT1, is a fictitious transit node with no load and no generation; the lines are SUDESTE–SUL, SUDESTE–NORDESTE, SUDESTE–NOFICT1, NORDESTE–NOFICT1 and NORTE–NOFICT1. The shipped case has no inter-reservoir cascade coupling (each region’s reservoir is independent), no spatial inflow correlation, and uses a constant hydro productivity model. This walkthrough preserves those properties but replaces the production-scale numbers with hand-traceable values: 4 stages, 3 openings, one thermal per bus, no transmission. This walkthrough is a pedagogical caricature, not a reproduction of the shipped case.

The chapter does not cover transmission, cascade coupling, the FPHA production model, an infinite-horizon cyclic policy, multi-resolution studies, or risk measures. Those topics are addressed in the chapters cited in section 8.

---

1. The Case in One Picture

The system has four buses, each with one local hydro (productivity 1.0), one local thermal, and one local demand block. The four reservoirs are independent — no cascade coupling. There is no transmission between buses in this walkthrough; each bus self-balances dispatch from its local resources.

Per-hydro parameters:

Hydro	Bus	$\bar V_h$	$\hat v_{h,0}$	$\mu_h$	$\sigma_h$	Productivity
H1	B1	100	30	15	5	1.0
H2	B2	100	30	12	4	1.0
H3	B3	80	20	10	3	1.0
H4	B4	80	20	8	3	1.0

Per-bus demand:

Bus	$D_b$
B1	25
B2	20
B3	15
B4	12

System-level parameters:

Parameter	Symbol	Value
Stages	$T$	4
Openings per stage	$N_t$	3
Thermal marginal cost	$c^{th}$	50 $/MWh
Deficit cost	$c^{def}$	1000 $/MWh
Discount factor	$d$	1.0

Each bus’s demand exceeds its local hydro mean inflow ($D_1 - \mu_1 = 10$, $D_2 - \mu_2 = 8$, $D_3 - \mu_3 = 5$, $D_4 - \mu_4 = 4$), so reservoirs deplete over the four-stage horizon and thermal generation appears in later stages.

---

2. Stage LP for This Case

The stage-$t$ LP is assembled from the general formulation in LP Formulation, specialised to four hydros, four buses with one local thermal each, four storage state variables, and 0-order inflow (no AR-lag state).

Objective (minimise current-stage cost plus future cost):

$$\min \quad \sum_{b=1}^{4} \bigl( 50\, g^{th}_b + 1000\, \delta_b \bigr) + \theta$$

Per-bus load balance (each bus self-balances, no transmission):

$$g_b + g^{th}_b + \delta_b = D_b, \qquad b = 1, 2, 3, 4$$

where $g_b$ is the local hydro generation at bus $b$.

Hydro generation (constant productivity at all four plants):

$$g_h \;=\; 1.0 \cdot q_h, \qquad h = 1, 2, 3, 4$$

Water balances (each reservoir is independent — no cascade):

$$v_h \;=\; v^{in}_h + a_h - q_h, \qquad h = 1, 2, 3, 4$$

(For this walkthrough $\zeta = 1$: one m³/s of turbining per stage withdraws one hm³.)

Incoming-storage pinning (the reduced cost of each pinned column becomes the cut coefficient):

$$v^{in}_h \;=\; \hat{v}_{h,t-1}, \qquad h = 1, 2, 3, 4$$

Bounds: $0 \leq v_h \leq \bar V_h$; $q_h, g_h, g^{th}_b, \delta_b \geq 0$; $\theta \geq 0$.

Future cost variable $\theta$: as in the single-reservoir case, the terminal stage carries no cuts; cuts of the form $\theta \geq \beta_0 + \sum_h \beta^v_h\, v_h$ are added by the backward pass to earlier stages’ LPs. With four reservoirs the cut is now a 4-coefficient hyperplane in storage state space, with each $\beta^v_h \leq 0$ reflecting that storage at hydro $h$ reduces future cost.

Note again the absence of any AR-lag state: 0-order inflow has no memory, so storage is the entire state vector.

---

3. The 0-Order Inflow Model with Four Hydros

Each hydro $h$ samples its own inflow independently from a normal distribution with hydro-specific seasonal mean and standard deviation:

$$a_{h,t} \;=\; \mu_h + \sigma_h\, \varepsilon_{h,t}, \qquad \varepsilon_{h,t} \sim \mathcal{N}(0, 1)$$

with hydro-specific $(\mu_h, \sigma_h)$ from the parameter table in section 1. The innovations are independent across hydros — there is no correlation.json file in the actual examples/4ree/ case, and this walkthrough preserves that property.

If a correlation.json file were supplied, the spatial structure $C$ between innovations would be applied via the spectral factorisation $\varepsilon = C^{1/2} z$ with $C^{1/2} = U \Lambda^{1/2} U^{\top}$ — see PAR(p) Inflow Model §6 for the multivariate case. For this walkthrough the four innovations are drawn independently.

The three openings used in the backward pass correspond to a single shared $\varepsilon \in \{-1, 0, +1\}$ applied uniformly to all four hydros (a simplifying choice: in novomodelo each opening is one noise vector with a value for every stochastic entity, each hydro included, so the hydros’ inflows need not move together). Each opening has equal probability $p = 1/3$.

---

4. Iteration 1 — Forward Pass

The forward pass samples one trajectory using $\varepsilon_t = 0$ for every stage, so each hydro receives its mean inflow at every stage. With $\theta$ free at zero (no cuts in iteration 1), the LP minimises the per-bus thermal and deficit costs at each stage.

Because at the initial state every bus has enough hydro plus storage to meet demand from hydro alone, stages 1–3 carry zero cost. Stage 4 runs water-short on two of the four buses, and a third (B3) has exactly enough.

Stage 1 — incoming storage $\hat x_0 = (30, 30, 20, 20)$, inflows $(15, 12, 10, 8)$. At every bus, $q_h = D_b$ (demand met from hydro); end-of-stage storage:

$$x_1 = (30 + 15 - 25,\; 30 + 12 - 20,\; 20 + 10 - 15,\; 20 + 8 - 12) = (20, 22, 15, 16).$$

Stage cost: $0$ (no thermal, no deficit).

Stage 2 — $\hat x_1 = (20, 22, 15, 16)$. Same pattern: each bus meets demand from hydro; storage decreases by $D_b - \mu_h$:

$$x_2 = (10, 14, 10, 12).$$

Stage cost: $0$.

Stage 3 — $\hat x_2 = (10, 14, 10, 12)$. Bus 1 reaches a knife edge: water available $= \hat v_{1,2} + a_1 = 10 + 15 = 25 = D_1$; the LP turbines all available water and ends with $v_{1,3} = 0$. Other buses still have surplus.

$$x_3 = (0, 6, 5, 8).$$

Stage cost: $0$.

Stage 4 — $\hat x_3 = (0, 6, 5, 8)$, inflows $(15, 12, 10, 8)$. Now two buses go water-short, and B3’s available water exactly meets its demand:

Bus	$\hat v_{h,3}$	$a$	Avail.	$D$	$q$	$g^{th}$	$\delta$
B1	0	15	15	25	15	10	0
B2	6	12	18	20	18	2	0
B3	5	10	15	15	15	0	0
B4	8	8	16	12	12	0	0

Stage 4 cost: $50 \times 10 + 50 \times 2 = 500 + 100 = 600$.

Trajectory upper-bound estimate: $0 + 0 + 0 + 600 = 600$.

---

5. Iteration 1 — Backward Pass

The backward pass walks stages $4 \to 2$. At each stage it pins the incoming storage to the trial point from the forward pass, evaluates all three openings, reads the four pinned-column reduced costs, and aggregates into a 4-coefficient cut. The mechanics follow Cut Management sections 2–3, generalised from one storage coefficient (single-reservoir case) to four (this case).

Stage 4 (terminal)

Trial point: $\hat x_3 = (0, 6, 5, 8)$. Inflows under the three shared openings (all four hydros move together with $\varepsilon$):

Opening	$\varepsilon$	$a_1$	$a_2$	$a_3$	$a_4$
$\omega_1$	$-1$	10	8	7	5
$\omega_2$	$0$	15	12	10	8
$\omega_3$	$+1$	20	16	13	11

For each opening, each bus solves its local dispatch independently (no transmission, no $\theta$ at the terminal stage):

$\omega_1$ (dry):

Bus	Avail.	$D$	$q$	$g^{th}$	Stage cost	$\beta^v_h$
B1	10	25	10	15	750	$-50$
B2	14	20	14	6	300	$-50$
B3	12	15	12	3	150	$-50$
B4	13	12	12	0	0	$0$

$Q_4(\omega_1) = 750 + 300 + 150 + 0 = 1200$.

The storage cut coefficient at each bus — the reduced cost of the pinned incoming-storage column — follows the single-reservoir logic: water-limited buses with thermal active have $\beta^v_h = -50$; buses where demand is met by hydro alone have $\beta^v_h = 0$.

$\omega_2$ (mean):

Bus	Avail.	$D$	$q$	$g^{th}$	Stage cost	$\beta^v_h$
B1	15	25	15	10	500	$-50$
B2	18	20	18	2	100	$-50$
B3	15	15	15	0	0	$0$
B4	16	12	12	0	0	$0$

$Q_4(\omega_2) = 600$. B3 is at a kink (available water exactly meets demand): one more unit of storage ends in the terminal $x_4$, which has zero value, while one unit less needs one unit of thermal worth $50$. Every value in $[-50, 0]$ is a valid subgradient; as in the single-reservoir walkthrough, the walkthrough takes the rate for one more unit of storage, $\beta^v_3(\omega_2) = 0$.

$\omega_3$ (wet):

Bus	Avail.	$D$	$q$	$g^{th}$	Stage cost	$\beta^v_h$
B1	20	25	20	5	250	$-50$
B2	22	20	20	0	0	$0$
B3	18	15	15	0	0	$0$
B4	19	12	12	0	0	$0$

$Q_4(\omega_3) = 250$.

Per-opening intercepts $\beta_{0,4}(\omega) = Q_4(\omega) - \sum_h \beta^v_h(\omega)\, \hat{v}_{h,3}$:

Opening	$Q_4$	$-\sum_h \beta^v_h \hat v_{h,3}$	$\beta_{0,4}$
$\omega_1$	$1200$	$50(0) + 50(6) + 50(5) + 0(8) = 550$	$1750$
$\omega_2$	$600$	$50(0) + 50(6) + 0(5) + 0(8) = 300$	$900$
$\omega_3$	$250$	$50(0) + 0(6) + 0(5) + 0(8) = 0$	$250$

(The signs flip because $\beta^v < 0$ and the formula subtracts a negative-times-positive product.)

Aggregation ($p = 1/3$):

$$\bar\beta_{0,4} = \tfrac{1}{3}(1750 + 900 + 250) = \tfrac{2900}{3} \approx 966.7$$

Hydro	$\bar\beta^v_h$
H1	$\tfrac{1}{3}(-50 - 50 - 50) = -50$
H2	$\tfrac{1}{3}(-50 - 50 + 0) = -\tfrac{100}{3}$
H3	$\tfrac{1}{3}(-50 + 0 + 0) = -\tfrac{50}{3}$
H4	$\tfrac{1}{3}(0 + 0 + 0) = 0$

Cut added to stage 3’s LP:

$$\theta \;\geq\; \tfrac{2900}{3} - 50\, v_1 - \tfrac{100}{3}\, v_2 - \tfrac{50}{3}\, v_3 + 0 \cdot v_4$$

Sanity check. At $x = \hat x_3 = (0, 6, 5, 8)$, the cut evaluates to

$$\tfrac{2900}{3} - 0 - \tfrac{600}{3} - \tfrac{250}{3} + 0 = \tfrac{2900 - 600 - 250}{3} = \tfrac{2050}{3} \approx 683.3.$$

This equals the probability-weighted expected stage-4 cost at the trial point, $\bar Q_4 = (1/3)(1200 + 600 + 250) = 2050/3 \approx 683.3$: the cut is exact there by construction, and it lies on or below the expected stage-4 cost at every other storage vector.

The four storage coefficients $(-50, -100/3, -50/3, 0)$ rank by how much each reservoir reduces expected future cost. H1 is the most valuable: thermal at B1 was active in all three openings, so an extra unit at H1 saves $50$ in every scenario and the average is $-50$. H4 has zero coefficient: B4 was thermal-free in every opening, so storage at H4 has no marginal value at this trial point.

Stages 3 and 2

The same procedure repeats at the earlier stages, with the cut from the next stage active in the LP. At each stage:

1. Pin the incoming storage vector $\hat x_{t-1}$ (column bounds).
2. Solve all three opening LPs with the next-stage cut active.
3. Read four pinned-column reduced costs per opening (one per reservoir).
4. Compute per-opening intercepts via $\beta_0(\omega) = Q(\omega) - \sum_h \beta^v_h(\omega)\, \hat v_{h,t-1}$.
5. Aggregate by probability-weighted averaging into one 5-coefficient cut (intercept plus four storage slopes).
6. Add the cut to the previous stage’s LP.

By the end of the backward pass, stages 1 through 3 each carry one cut; stage 4 has none.

---

6. The Cut as a 4-D Hyperplane

The fundamental change from the single-reservoir case is the dimensionality of the cut. Each cut is now a hyperplane in 4-dimensional storage state space:

$$\underline{V}_t^k(v) \;=\; \max_{i = 1, \ldots, k} \Bigl\{ \bar\beta_0^i + \bar\beta^{v,i}_1\, v_1 + \bar\beta^{v,i}_2\, v_2 + \bar\beta^{v,i}_3\, v_3 + \bar\beta^{v,i}_4\, v_4 \Bigr\}.$$

Several practical consequences follow:

Per-reservoir slopes. At the terminal stage the buses share no constraint, so the stage problem splits into four independent bus problems, and each slope of the iteration-1 stage-3 cut comes from its own bus alone: $\bar\beta^v_h$ averages the reduced cost of hydro $h$‘s pinned incoming-storage column over the three openings, whatever the other reservoirs hold. The slopes are $-50$, $-100/3$, $-50/3$ and $0$: one more unit at H1 saves $50$ in every opening, and one more unit at H4 saves nothing at this trial point. The cut stacks four independent marginal water values; trading water between reservoirs needs a coupling that the caricature leaves out, such as transmission or a cascade (section 8).

The figure shows the four slopes of this cut as bars and each opening’s reduced cost as a dot: H1 is water-limited in all three openings ($-50$ each), H2 in $\omega_1$ and $\omega_2$, H3 in $\omega_1$ only (its $\omega_2$ kink takes $0$), and H4 in none. The plotted values come from a tested module that re-runs this stage-4 backward pass.

Cut tightness is local, not global. Each cut equals the expected cost the backward pass computed at its trial point; far from the trial point it can be a loose lower bound on the cost-to-go. The forward pass spreads trial points across the storage state space as iterations progress, and each new trial point produces a cut that tightens the approximation in its neighbourhood. When the cuts bound the cost-to-go from below and when the approximation converges is set out in Cut Management — when bounds and certificates hold.

Per-bus thermal regime drives slope structure. A bus whose thermal is always idle (B4 in this trial) gets $\bar\beta^v_h = 0$; the corresponding reservoir’s storage has no marginal value at the visited state. As subsequent iterations sample trial points where B4 also runs short, that reservoir’s slope becomes negative in those cuts, and the cumulative cut pool eventually covers the region where every reservoir’s storage carries a non-zero marginal value.

---

7. Convergence on This Case

The percent form of the optimality gap divides the gap by the magnitude of the lower bound, $\lvert\underline{z}^k\rvert$ (floored at one currency unit). The iteration count needed to close it depends on the demand-to-inflow ratios, the reservoir capacities and the variance of the inflows, and the upper bound of a sampled forward pass is a statistical estimate that certifies nothing (Cut Management — Tier 3). The shipped 4ree runs four sampled forward passes per iteration and stops at its iteration limit of 256; novomodelo rejects a gap stopping rule at setup under a sampled forward pass. See Stopping Rules for the available criteria.

---

8. What This Example Does Not Show

The toy walkthrough above keeps to four reservoirs at four buses with no transmission. It does not cover:

• Transmission networks: the shipped examples/4ree/ case has five transmission lines, three of them through the fictitious transit bus NOFICT1, that let cheap generation at one bus serve another. With transmission, the load balance becomes a network constraint and the per-bus thermal share depends on line capacities and exchange costs. The cut structure does not change — still one storage coefficient per reservoir — but the per-opening LPs are no longer separable across buses.
• Cascade coupling: in branched cascades, downstream reservoirs receive upstream releases via a water-balance term $v_h = v^{in}_h + a_h - q_h - s_h + \sum_{h' \in \mathcal{U}_h}(q_{h'} + s_{h'})$; the storage cut coefficient at upstream plants then carries the expected downstream value of released water. See System Element Modeling Overview for cascade topology and Cut Management for how cascade sensitivities propagate through the pinned-column reduced cost.
• FPHA production model: nonlinear head-dependent productivity approximated by piecewise-linear hyperplanes; one of the planes binds at the optimum and contributes to the storage cut coefficient. See Hydro Production Function Models.
• Spatial inflow correlation: when a correlation.json file is supplied, the per-hydro innovations are drawn from a correlated multivariate normal via spectral factorisation. See PAR(p) Inflow Model §6.
• Autoregressive inflow memory: a PAR(p) model with $p \geq 1$ adds one lag state variable per hydro per lag; whether a stage’s cuts carry a coefficient for each lag is that stage’s cut-state projection (State Augmentation §7).
• Risk measures: CVaR weighting that shifts cut aggregation probabilities away from uniform $p = 1/N_t$ toward worst scenarios, raising cut intercepts and slopes in the dry direction. See Risk Measures.
• Cyclic policy graphs: the four-stage horizon ends without a cut linking back to stage 1. A cyclic (periodic) policy graph, in which the first stage’s cost-to-go would feed the last stage, is a reserved design: stages.json accepts only finite_horizon as policy_graph.type and rejects cyclic at case load. See Horizon Modes.
• Multi-resolution studies: stages of different lengths in one horizon, for example a weekly head followed by a monthly tail, sharing one set of cuts. See Multi-Resolution Studies.

---

Cross-References

• Toy Single-Reservoir Walkthrough — Single-reservoir baseline; core SDDP loop, 0-order inflow, forward/backward/cut in the simplest setting
• LP Formulation — Complete stage LP
• LP Layout and Scaling — Column and row layout
• State Augmentation — Column-bound state pinning, reduced-cost extraction
• System Element Modeling Overview — Hydro plant element, cascade topology (not exercised here), water-balance convention, FPHA overview
• Hydro Production Function Models — Constant-productivity (used here) and FPHA hyperplane fitting; impact on Benders cut coefficients
• PAR(p) Inflow Model — Inflow model definition; the $p = 0$ degenerate case (white noise) used here; spatial correlation factorisation for multivariate cases
• Cut Management — Dual extraction, per-opening intercepts, single-cut aggregation; sign convention $\beta^v = \partial Q/\partial \hat v$
• Risk Measures — CVaR definition, EAVaR convex combination, risk-adjusted aggregation weights
• Horizon Modes — Finite (supported) vs. reserved cyclic policy graphs and the season-indexed cut pool