Multi-Cut SDDP with Intra-Week Dispatch
Theory and implementation of the SDDP algorithm for multi-reservoir seasonal planning with Markov electricity prices and intra-week price segments.
Multi-Cut Formulation
The LP at each stage has P per-state α variables (one per future price state), not a single α. The objective is:
max revenue + Σ_p' prob(current→p') × α_p'
subject to:
α_p' ≤ cut.intercept + cut.gradient · v ∀ cut at (t+1, p')
water balance per reservoir
PQ curve constraints per plant
bounds on v, r, spill, prodEach price state's cuts are independent — no probability-weighted alignment across states. This eliminates the convergence issues caused by the single-α expected-cut approach, where states with different numbers of cuts lost probability mass.
Intra-Week Dispatch (Segmented LP)
When segment data is available (42 × 4h), the LP has per-segment discharge and production variables:
Variables: v[K], r_total[J], r_seg[J×S], prod_seg[J×S], α[P]
Constraints:
r_total[j] = Σ_s r_seg[j,s] (segment sum)
prod_seg[j,s] ≤ PQ(r_seg[j,s] / conv_s) (per-segment PQ linearisation)
water balance uses r_total (weekly)
α_p ≤ cut constraints on v (weekly)
Objective:
max Σ_j Σ_s price_s × prod_seg[j,s] × hours_s + Σ_p' tp[p'] × α_p'Forward vs Backward Pricing
- Forward pass: uses actual per-scenario segment prices — the LP dispatches optimally across the price profile for each week.
- Backward pass: uses average segment profiles per Markov price state. These are computed by averaging all scenario-week segment profiles assigned to each state.
Both passes use the same segmented LP structure. The backward's state segment profiles ensure that Benders cuts capture the value of intra-week dispatch flexibility — a plant that can shift production to peak hours has water that is worth more per Mm³.
Why Not Scalar Backward?
A scalar (mean price) backward generates shadow prices that reflect the marginal value of water at the mean price. This undervalues water because it ignores the dispatch uplift from peak-hour production. The result is a policy that produces too aggressively and stores too little.
With segment profiles in the backward, the shadow price correctly reflects that an extra Mm³ of water can be dispatched at peak prices, resulting in higher water values and more appropriate conservation.
Algorithm
State
The state at stage t is: (v⃗, p) = K reservoir volumes + discrete price state.
Forward Pass
For each of S inflow scenarios:
- Start at (v₀, p₀)
- For t = 1, ..., T:
- Draw inflow scenario and price transition
- Solve segmented LP with per-scenario segment prices
- Record volumes and stage revenue
- Total value = Σ(stage revenues) + terminal future value
Upper bound = mean of total values across scenarios.
Backward Pass (Hot-Path, Parallelised)
For t = T, T-1, ..., 1:
- Load cuts for stage t+1 (once per stage)
- In parallel across all (p, s) work items:
- Set price to state segment profile for p
- Set transition probabilities for p
- Update only water balance RHS (v₀ + inflow for scenario s)
- Solve
- Extract shadow prices → form Benders cut
- Add all cuts to library at (t, p) in deterministic order
The P × N_fwd solves within each stage are embarrassingly parallel:
- All reads (cuts from t+1, forward volumes, prices, inflows) are immutable
- Each solve writes to its own slot in a pre-allocated result array
- The cut library is only mutated after the parallel section
Work items are ordered so that items for the same price state p are contiguous. With Threads.@threads :static, each thread gets a contiguous chunk and reloads the subproblem state at most twice per stage (when p changes at a chunk boundary).
Enable with julia -t4 or JULIA_NUM_THREADS=4. Speedup scales well up to min(nthreads, P × N_fwd) work items.
The hot-path optimisation avoids redundant cut loading and price updates, giving a ~2× speedup over the naive approach.
Convergence
- Upper bound (UB): mean forward simulation revenue
- Lower bound (LB): stage-1 LP objective with current cuts
- Converged when:
(UB − LB) / |UB| < toleranceandLB ≤ UB
Buffer Reservoirs
Tiny passthrough reservoirs (< 1 Mm³) like intermediate forebays cause extreme shadow prices. Their volume is fixed at min_volume in the LP (both bounds set equal). Shadow prices are zeroed after solving, which is safe because v_buffer = 0 always — the gradient component is multiplied by zero in both the intercept and cut evaluation.
Terminal Water Values
Computed from cascade energy equivalent rather than proprietary values:
terminal_wv[p] = price[p] × total_cascade_energy_equiv × scale
energy_equiv = Σ_plant [ PQ(max_q/2) × dt / (max_q/2 × conv) ]This sums the MWh/Mm³ conversion for all downstream plants in the cascade. For a cascade with TORPA (1139 MWh/Mm³) + DOKKA (304 MWh/Mm³), the total is ~1443 MWh/Mm³.
Usage
using HydroCore, SeasonalPlanning
cascade = load_my_cascade()
scenarios = load_inflow_scenarios()
price_mod = fit_markov_price(all_prices, 7)
config = SDDPConfig(
n_iterations = 12,
n_forward_scenarios = 20,
convergence_tol = 0.03,
)
# Segment hours for 42 × 4h dispatch
seg_hours = fill(4.0, 42)
# Compute state segment profiles for backward
state_profiles = compute_state_segment_profiles(segmented_prices, price_mod)
result = solve_sddp(cascade, scenarios, price_mod, config;
v0 = initial_volumes,
initial_price_state = 3,
n_stages = 220,
segment_hours = seg_hours,
segmented_prices = seg_price_data,
state_segment_profiles = state_profiles,
terminal_cuts = terminal_cuts,
)
# Generate seasonal plan with dispatch
plan = generate_plan(result, cascade, scenarios, price_mod;
segment_hours = seg_hours,
segmented_prices = seg_price_data,
)Additional Features
Volume-Stability Convergence (§5.4.5.2)
ProdRisk tests convergence by checking that reservoir volume trajectories stabilise between iterations, not by the LB/UB gap. Enable with vol_convergence_tol > 0 in SDDPConfig or --vol-convergence on the CLI.
The forward scenario indices are fixed across iterations (pre-drawn once) so that volume trajectories are comparable. This was the single most important improvement for convergence quality.
Head Correction (§5.4.6)
A linearised premium for reservoir level corrects for variable head. See Head Correction for theory and equations. Enable with --head-correction.
AR(1) Inflow Autocorrelation (§5.4.7)
Conditional inflow sampling in the backward pass preserves wet/dry persistence. See Inflow Model for the Markov model and conditional sampling algorithm. Enable with --inflow-ar1.
Composing Features
All flags compose:
julia --project=HydroRunner HydroRunner/bin/run_case.jl cases/dokka \
--vol-convergence --head-correction --inflow-ar1