Warm-Start SDDP: Concept and Theory
Motivation
In operational hydropower planning, inflow forecasts and price prognoses are updated frequently — typically daily for day-ahead markets. A full SDDP run with 50+ iterations is expensive (tens of seconds to minutes depending on system size). When the change in input data between consecutive runs is small, most of the previous solution remains valid.
Warm-starting reuses the Benders cut library from the previous run to seed the new optimisation. Because the cuts already approximate the value-to-go function well, the algorithm converges in a fraction of the iterations — often 3–5 instead of 50+.
The Operational Setup
The real operational context differs from the synthetic test cases used during development:
- True calendar: planning starts from today's date, not 1 January
- 5-year horizon: multi-year reservoirs require looking 260 weeks (5 × 52) ahead
- Prognosis + statistics: the first year uses a meteorological inflow prognosis; years 2–5 are sampled from weather-year statistics (30–50 years of historical record)
- Daily updates: new forecasts arrive daily; each day the planning horizon rolls forward by one step
Scenario construction
For a 5-year horizon starting on date D (calendar week W):
Year 1 (stages 1–52):
Inflow prognosis for the next 12 months
Year 2–5 (stages 53–260):
For each weather year in the historical record:
Sample 4 years of weekly inflow, starting at calendar week W
(wrapping around Dec→Jan as needed)This creates Nweatheryears scenarios. All share the same prognosis year but differ in the statistical extension.
Why Warm-Starting Works: Cut Validity Under Perturbation
SDDP cuts are outer approximations (supporting hyperplanes) of the expected future value function:
α ≤ β + μᵀ vwhere α is the future-value variable, v is the reservoir volume vector, β is the intercept, and μ is the gradient (shadow prices).
When input data (inflows, prices) change slightly:
Cuts that underestimate the new value-to-go are simply loose — the LP optimizer ignores them in favour of tighter cuts. Harmless.
Cuts that overestimate the new value-to-go (e.g., prices decreased, making future revenue lower than old cuts claim) cause the forward pass to temporarily over-value water storage. The backward pass then generates new, correct cuts that override the stale ones. After a few iterations, the solution is correct.
In both cases, the algorithm is always feasible — stale cuts never cause infeasibility. They just make the first few iterations suboptimal.
Stage Shifting for Rolling Horizons
When the planning horizon rolls forward by one day (weekly resolution: by one week), yesterday's cut library must be shifted:
| Yesterday | Today |
|---|---|
| Stage 1 (this week) | — (in the past) |
| Stage 2 | → Stage 1 |
| Stage 3 | → Stage 2 |
| ... | ... |
| Stage T | → Stage T-1 |
| — | Stage T (new, no cuts) |
We shift the cut library: drop stage 1, rename stage t → t−1. The new final stage starts with no cuts (terminal value = 0), same as a fresh run's final stage.
The shift amount is computed from the calendar: if yesterday's start date was March 22 and today is March 29 (weekly resolution), shift by 1. If today is March 23 (daily resolution), also shift by 1. The calendar handles the mapping.
Drift Metric
To decide whether warm-starting is appropriate, we need to quantify "how much did the input change?"
Inflow drift
For each reservoir k with mean inflow profile q̄ₖ (length T, averaged across scenarios):
δ_inflow = (1/K) Σₖ ‖q̄ₖ^new − q̄ₖ^old‖₂ / ‖q̄ₖ^old‖₂Important: when comparing between days, the profiles are aligned by calendar date (not by stage index). Today's stage 1 and yesterday's stage 2 both correspond to the same calendar week — they should be compared directly.
Price drift
For the mean price scenario p̄ (length T, averaged across scenarios):
δ_price = ‖p̄^new − p̄^old‖₂ / ‖p̄^old‖₂Also aligned by calendar date.
Combined drift
δ = w_inflow × δ_inflow + w_price × δ_pricewith configurable weights (default: equal 0.5 / 0.5).
Cumulative drift
If today's run is a warm start from yesterday, which was itself a warm start from the day before, small daily drifts can accumulate. We track:
δ_cumulative = δ_since_last_full_run + δ_todayWhen δ_cumulative exceeds a configured limit (e.g., 0.20), a full run is triggered regardless of today's individual drift.
Decision Logic
Load previous state (includes start_date, cuts, cumulative drift)
Compute stage shift from date difference
Compute δ_today (calendar-aligned)
Update δ_cumulative
if δ_cumulative > cumulative_limit
→ FULL RUN (drift too large)
elif δ_today > drift_threshold
→ FULL RUN (single update too large)
elif days_since_full_run ≥ full_run_interval
→ FULL RUN (periodic refresh)
else
→ WARM START (shift cuts, limited iterations)Cut Accumulation and Pruning
Over many warm starts, the cut library grows. Most old cuts become non-binding (loose). While this doesn't affect correctness, it slows LP solves. Mitigation strategies:
- Periodic full runs reset the cut library (simplest — current approach)
- Cut pruning: remove cuts that haven't been binding for N iterations
- Cut limit: keep at most M cuts per (stage, price_state), dropping the loosest when the limit is reached
The current implementation uses strategy 1 (periodic full runs via full_run_interval). Active cut pruning is deferred to a future phase pending operational experience.
Price Model Stability
The Markov price model is currently kept fixed between full runs. This is the simplest approach: cuts are indexed by price state, and state definitions don't change between warm starts.
Re-fitting the price model daily would require re-mapping old cuts to new price states (complex). This is deferred pending discussion with domain experts.