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:

α ≤ β + μᵀ v

where α 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:

  1. Cuts that underestimate the new value-to-go are simply loose — the LP optimizer ignores them in favour of tighter cuts. Harmless.

  2. 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:

YesterdayToday
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 × δ_price

with 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 + δ_today

When δ_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:

  1. Periodic full runs reset the cut library (simplest — current approach)
  2. Cut pruning: remove cuts that haven't been binding for N iterations
  3. 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.