SDP Theory — Single Reservoir Water Values
This document derives the Stochastic Dynamic Programming (SDP) algorithm used in the WaterValues package. It follows Kompendium 1, Chapter 6.
Problem setup
State: volume v ∈ [v_min, v_max] (Mm³)
Decision: turbine release r ∈ [0, r_max] (Mm³/week)
Stochastic input: weekly inflow q (Mm³/week)
Objective: maximise expected total revenue over a horizon of T weeks
State transition (water balance)
v_{t+1} = v_t + q_t - r_t ∈ [v_min, v_max]The inflow q_t is uncertain at the time of decision. In this single-reservoir SDP we treat q_t as a random variable with known distribution (approximated by historical weekly values).
If the balance would violate the bounds, we clamp:
- Lower: force
r_t ≤ v_t + q_t - v_min(cannot release more than available) - Upper: spill if
v_t + q_t - r_t > v_max(forced spill, no revenue)
The value function
Define:
V_t(v) = maximum expected revenue from week t to end of horizon,
given reservoir volume v at start of week tThis satisfies Bellman's equation (backward induction):
V_t(v_i) = (1/S) Σ_{s=1}^{S} max_{r} [ price_t × P(r) × Δt
+ V_{t+1}(v_i + q_s - r) ]
subject to:
max(0, v_i + q_s - v_max) ≤ r ≤ min(r_max, v_i + q_s - v_min)where:
S= number of inflow scenariosq_s= scenario s inflow (Mm³/week)P(r)= power [MW] from PQ curve at discharge r [converted to m³/s]Δt= 168 h/weekprice_t= electricity price[NOK/MWh](flat in this version)
Terminal condition
The algorithm works backward from week T = 52 to week 1. We need a starting value V_{53}(v) to begin the recursion. We use:
V_{53}(v) = terminal_wv × vwhere terminal_wv [NOK/Mm³] is an initial estimate of the long-run water value. A reasonable choice:
terminal_wv ≈ price × average_efficiency [MWh/m³] × 1e6(energy content of one Mm³ × price per MWh)
The algorithm iterates multiple full years (cycles) until the value function stops changing — at that point the answer is independent of the terminal condition. Typically 5–15 cycles suffice.
Cyclic iteration for convergence
Rather than running the algorithm over a single year and depending on the terminal condition, we iterate cyclically:
Repeat for n_cycles:
V_next ← V_52 from previous cycle (or terminal condition on first cycle)
for t = 52 downto 1:
compute V_t from V_{t+1}
check convergence: max |V_new - V_old| < tolAfter convergence, V_t(v) represents the steady-state value function — the long-run expected revenue from operating optimally from week t with volume v.
Water value extraction (finite differences)
The water value table is extracted from the converged value function:
WV_t(v_i) ≈ [V_t(v_{i+1}) - V_t(v_{i-1})] / [v_{i+1} - v_{i-1}] central diff.At boundaries:
i = 1: forward difference(V[2] - V[1]) / (g[2] - g[1])i = N: backward difference(V[N] - V[N-1]) / (g[N] - g[N-1])
The resulting WV matrix has dimensions (52 weeks × N volume points) and units of NOK/Mm³.
Optimisation over release r
With constant head, P(r) is concave (piecewise-linear PQ curve) and revenue is linear in P. The future value V_{t+1}(·) is also concave by induction (starting from the linear terminal condition). The sum is therefore concave.
In the current implementation we use a fine grid search (500 points over [rlo, rhi]) rather than a golden-section or gradient method. This is clear and correct; a future optimisation could use ternary search.
Key assumptions and limitations
| Assumption | Consequence |
|---|---|
| Constant head (PQ at reference head) | No head-volume coupling; slightly optimistic for reservoirs with large head variation |
| Flat electricity price | Water values reflect seasonal storage value only; price spikes not captured |
| Empirical inflow scenarios | Distribution bounded by historical observations; no extreme events |
| Single reservoir | Cascade interactions ignored; extend in Phase 4 |
These are intentional simplifications for the first implementation. Each can be relaxed systematically:
- Variable head → use HV curve in the optimisation
- Seasonal/stochastic price → add price as a state variable (Kompendium 1, §6.5)
- Fitted distribution → log-normal or Gamma fit to weekly inflows
Convergence properties
- The value function iteration converges geometrically in the discount-free case (operating horizon wraps around annually)
- Empirically, 5–15 cycles suffice for a flat-price model with 30 volume points
- Convergence is checked as
max |ΔV| < tol(default tol = 1 NOK)
Reference
- Bellman (1957): Dynamic Programming
- Kompendium 1, §6.1–6.3 (NTNU, Fosso 2018)
- Pereira & Pinto (1985): "Stochastic optimization of a multireservoir hydroelectric system"