Skip to content

SDDP Algorithm

This chapter describes the Stochastic Dual Dynamic Programming (SDDP) algorithm as implemented in Novomodelo: the multistage stochastic formulation, the iterative forward/backward pass structure, convergence monitoring, policy graph topologies, state variable requirements, and the single-cut formulation. It serves as the algorithmic foundation referenced by the other methodology chapters.

For notation conventions (index sets, parameters, decision variables, dual variables), see Notation Conventions.

For the entity view of this chapter, see Water value and future cost.

Novomodelo solves the hydrothermal dispatch problem: determining optimal generation schedules for hydro and thermal plants over a planning horizon under inflow uncertainty. Key characteristics:

  • Flexible for short or long horizons: daily, weekly or monthly stages, over horizons from short to long
  • Large state space: the state dimension grows with the number of reservoirs and the AR orders of their inflow models
  • Stochastic inflows: PAR(p) autoregressive models with seasonal patterns
  • Customize modeling complexity stagewise: Scenario generation, hydro production and others are configurable stagewise and elementwise

The hydrothermal dispatch problem is formulated as a multistage stochastic program:

min⁡E[∑t=1Tct(xt,ut)]\min \mathbb{E}\left[ \sum_{t=1}^{T} c_t(x_t, u_t) \right]

subject to stage-linking constraints and uncertainty realization. The nested formulation uses value functions:

Vt(xt−1)=Eωt[min⁡xt,ut{ct(xt,ut)+Vt+1(xt):(xt,ut)∈Xt(xt−1,ωt)}]V_t(x_{t-1}) = \mathbb{E}_{\omega_t}\left[ \min_{x_t, u_t} \left\{ c_t(x_t, u_t) + V_{t+1}(x_t) : (x_t, u_t) \in \mathcal{X}_t(x_{t-1}, \omega_t) \right\} \right]

with terminal condition VT+1(x)=0V_{T+1}(x) = 0, which a study may replace with an imported terminal function (§7).

Key insight: The value function Vt(x)V_t(x) is convex and piecewise linear (for LP subproblems), enabling outer approximation via Benders cuts.

Value function approximation via Benders cuts — each cut is a tangent at a trial point (its slope is the analytic derivative V′(v)V'(v)), tightening the outer approximation toward the true convex cost-to-go function.

SDDP iteratively builds piecewise-linear approximations V‾tk\underline{V}_t^k at iteration kk of the true value functions. Each iteration starts with a forward pass that solves the stages in order along sampled or enumerated scenario paths, recording the trial points and the path costs from which the upper bound is computed (Upper Bound Evaluation). A backward pass then walks the stages from the last down to the second: at each stage tt it solves every (child, opening) pair at each trial point x^t−1\hat{x}_{t-1}, aggregates one cut per trial point for stage t−1t-1 and synchronizes the ranks so that each holds these cuts before it moves to stage t−1t-1. Periodic cut selection and the cap on active cuts then run when the study configures them, and the lower bound is evaluated by solving the first stage over its openings. If the stopping rules are not met, iteration k+1k+1 starts again from the forward pass; once they are met, training stops, and the policy is simulated when the study enables the simulation phase (Stopping Rules describes how the rules combine).

Forward passBackward passPeriodic cut selection, active-cut capwhen configuredLower boundfirst stage solved over its openingsStopping rules met?Simulationwhen the study enables itSolve the stages along sampled or enumerated pathsrecord trial points x̂ₜ and path costsSolve every (child, opening) pairat each trial point x̂ₜ₋₁Aggregate one cut per trial pointadded to stage t−1Synchronize the new cutsso every rank holds them t > 2 · t ← t−1t ← Tt = 2no · k ← k+1yes

The forward pass simulates the system under the current policy to generate trial points — the visited states that will be used by the backward pass to construct cuts.

For each of MM independent scenario trajectories:

  1. Start from the known initial state x0x_0 (initial storage volumes and inflow history)
  2. At each stage t=1,…,Tt = 1, \ldots, T, sample a scenario realization ωt\omega_t from the stage’s scenario set, then solve the stage LP using the incoming state x^t−1\hat{x}_{t-1} and the sampled scenario. The LP includes all current Benders cuts as constraints on the future cost variable θ\theta
  3. Record the optimal state x^t\hat{x}_t (end-of-stage storage volumes and updated AR lags), canonicalized onto its admissible bounds (see below), as the trial point for stage tt
  4. Pass x^t\hat{x}_t as the incoming state to stage t+1t+1

Under an enumerated forward pass, every root-to-leaf path of the policy graph is visited exactly once in each iteration, with no sampling, and the paths play the role of the MM trajectories; every node of such a graph carries a single opening, which step 2 takes as the stage’s realization (Policy Graphs §6).

The forward pass produces: (a) trial points {x^t}\{\hat{x}_t\} at each stage for each trajectory, and (b) stage costs for upper bound estimation.

Parallelization: Forward trajectories are independent — Novomodelo distributes MM trajectories across MPI ranks, with threads solving individual stage LPs within each rank.

Warm-starting: When the backward pass warm-starts, the basis of the forward solve at stage tt seeds the backward pass solves of stage tt at the same trial point, reducing their solve times (LP Warm-Start).

State canonicalization: The recorded outgoing state x^t\hat{x}_t is not the raw LP primal but its projection onto the resolved admissible bounds. Each bounded coordinate — end-of-stage storage, in-transit water volume, and any anticipated-thermal commitment hold — is clamped into its resolved interval, while the unbounded inflow (AR) lags pass through unchanged. The projection is the identity for an in-box optimum, so a solve whose state stays within bounds is unaffected by it. It is applied once, at read-back, and every consumer reads that one canonical vector: the forward trajectory, the backward-pass trial state x^t−1\hat{x}_{t-1}, and the cut intercept anchored at it (see Cut Management). This is what makes x^t\hat{x}_t a well-defined function of the stage’s optimal value and its resolved bounds — independent of which degenerate optimal vertex the solve terminated at or of round-off. See Determinism & Provenance.

The backward pass improves the value function approximation by generating new Benders cuts, walking stages in reverse order from TT down to 22 and adding cuts to stages T−1T-1 down to 11.

At each stage tt, for each trial point x^t−1\hat{x}_{t-1} collected during the forward pass:

  1. Solve the stage tt LP for every scenario ω∈Ωt\omega \in \Omega_t (branching), using the trial state x^t−1\hat{x}_{t-1} as incoming state
  2. From each LP solution, extract the optimal objective value Qt(x^t−1,ω)Q_t(\hat{x}_{t-1}, \omega), the reduced costs of the pinned incoming-state columns, and the duals of the rows that read the realized inflow and of the cut rows. The storage and inflow-lag coefficients enter the cut when the stage’s cut projection keeps those components; the in-transit water-bucket and anticipated-thermal-slot coefficients always do (State Augmentation §7). The reduced costs give the storage, bucket and slot coefficients directly — no combination with FPHA or generic constraint duals is needed — and the duals give the inflow-lag coefficients by the chain rule (PAR(p) Folding §4). See Cut Management
  3. Compute per-scenario cut terms (Qt(x^t−1,ω),β(ω))(Q_t(\hat{x}_{t-1}, \omega), \beta(\omega)) at the trial point, each storage, bucket and slot coefficient of β(ω)\beta(\omega) being the reduced cost of step 2 divided by its column’s scale factor, and each inflow-lag coefficient the chain rule of step 2 over the unscaled duals (Cut Management §2). Novomodelo forms the inflow-lag coefficients once per child, from the duals aggregated under the weights of step 4, which in exact arithmetic gives the aggregate of the per-scenario coefficients (PAR(p) Folding §4)
  4. Aggregate the per-scenario cut terms into a single cut. On a policy graph, the cut of a node nn aggregates every (child, opening) pair (n′,ω)(n', \omega) of nn, weighted by P(n→n′) pn′(ω)P(n \to n')\, p_{n'}(\omega), with the risk measure acting once on that joint law; on the stage chain the node has one child and the weights are the uniform p(ω)p(\omega) over Ωt\Omega_t. See Cut Management §3
  5. Add the aggregated cut to stage t−1t-1‘s cut pool

The backward pass produces one new cut per stage per trial point per iteration.

Scenario tree under a sampled forward pass — the forward pass samples M sparse paths through the branching tree, while the backward pass evaluates every opening at each trial point and aggregates them into one Benders cut. The sparse-forward / exhaustive-backward asymmetry keeps an iteration tractable where full-tree evaluation is infeasible; an enumerated forward pass visits every path instead (§3.1).

Forward pass — sparse (sample M paths)Backward pass — exhaustive (all openings)x₀x̂₁ᴬx̂₂ᴬx̂₁ᴮx̂₂ᴮtrial point x̂ω⁽¹⁾ω⁽²⁾ω⁽³⁾aggregateβ̄, Q̄ₜ under the risk measureone Benders cutadded to stage t−1 path Apath Beach visited trial point x̂

Lower Bound: z‾k\underline{z}^k is the first stage’s risk-adjusted value over its openings with the current cuts (Upper Bound Evaluation — Lower bound). It does not decrease across iterations, and Tier 1 states when it is a valid bound.

Upper Bound: Under a sampled forward pass, this is a statistical estimate — the sample mean over the forward pass trajectories; under an enumerated forward pass, it is the exact probability-weighted bound zˉexact\bar{z}_{\text{exact}} over every leaf path, with no sampling error (see Upper Bound Evaluation). The sampled-mean form:

zˉk=1M∑m=1M∑t=1Td1→t ct(xt(m),ut(m))\bar{z}^k = \frac{1}{M} \sum_{m=1}^{M} \sum_{t=1}^{T} d_{1 \to t}\, c_t(x_t^{(m)}, u_t^{(m)})

where d1→td_{1 \to t} is the cumulative discount factor of stage tt (Discount Rate Formulation §5). With an imported terminal function (§7), each trajectory’s cost also includes the discounted value of that function at the trajectory’s final state.

Optimality Gap: the distance between the upper and the lower bound, reported in percent of the lower bound; Stopping Rules defines it and the gap-based stopping rule that consumes it.

3.4 Execution Model and Performance Considerations

Seção intitulada “3.4 Execution Model and Performance Considerations”

The SDDP iteration structure has specific properties that guide the parallelization strategy and solver lifecycle design. These are summarized here as architectural constraints.

Backward pass synchronization: The backward pass enforces a per-stage synchronization barrier: the cuts generated by the stage-tt solves are complete, and synchronized across ranks, before any stage-(t−1)(t-1) solve starts, so every stage-(t−1)(t-1) solve includes them. This serializes the algorithm at stage boundaries.

Each forward and backward stage solve loads the stage’s LP template, which holds the cuts active when the template was built, and appends the cuts added since; under the dynamic method, once its lazy loop starts, these solves load a bounded resident subset of the pool instead (Cut Management §8). Work is distributed across ranks and threads as Performance Accelerators describes.

The software architecture that realises these constraints is described in the novomodelo-sddp README.

The stage chain used throughout this chapter — one node per stage t∈{1,…,T}t \in \{1, \ldots, T\}, connected by transitions of probability 11, terminating at VT+1(x)=0V_{T+1}(x) = 0 or an imported terminal function (§7) — is the special case of a more general policy graph: a structure of nodes, probability-weighted transitions, and per-node future-cost pools. See Policy Graphs for the full node/transition/pool structure, the two probability axes (between-node edge weights versus within-node openings), the discount-separate convention, and the mapping onto the SDDP.jl family.

Novomodelo’s policy graph is finite-horizon only: an acyclic, leaf-terminated graph in which every trajectory starts at a root and reaches a leaf after a bounded number of stages. A cyclic graph shape — a later stage transitioning back to an earlier one, for infinite-periodic-horizon planning — is reserved and rejected when the case is loaded. See Horizon Modes for the cyclic target design this reservation anticipates, and Policy Graphs for the complete list of structural limitations.

For SDDP to generate valid cuts, the subproblem must satisfy the Markov property: future costs depend only on the current state, not on the path by which the current state was reached.

State variables in Novomodelo:

ComponentVariableCountDescription
Hydro storagevhv_hNhydroN_{hydro}Reservoir volume at end of stage
AR inflow lagsah,ℓa_{h,\ell}Nhydro⋅Pmax⁡N_{hydro} \cdot P^{\max}Lagged inflows of the AR(PhP_h) models, stored Pmax⁡P^{\max} per hydro (State Augmentation §4)
In-transit water bucketsbh,doutb^{\mathrm{out}}_{h,d}BBReleased water still in transit under travel-time delay — one bucket per receiving plant hh per maturity lag dd
Anticipated-thermal slotsxs,iax^{\mathrm{a}}_{s,i}one ring per anticipated plantCommitments decided and not yet delivered — each holds one slot of its plant’s ring until its delivery stage

The last two components are present only when the study declares them: water travel-time arcs introduce the in-transit buckets, and anticipated thermals introduce the ring slots. A study with neither reduces to the classical storage (+ AR-lag) state. All four components are genuine Markov state. The storage, the buckets and the ring slots are pinned by column bounds on their incoming-state columns, and the reduced cost of each column gives its cut coefficient (section 3.2); the inflow lags have no LP column, reach the LP through right-hand sides, and take their cut coefficients from the duals by the chain rule (§5.1).

The PAR(p) inflow model requires past inflows ah,t−1,ah,t−2,…a_{h,t-1}, a_{h,t-2}, \ldots to compute current inflow. To maintain the Markov property, these lags are included as state variables. They are not LP columns: before each solve, the realized inflow of each hydro is computed from the incoming lags and the noise of the opening,

z^h=bh,m(t)+∑ℓ=1Pmax⁡ψm(t),ℓ a^h,ℓ+σm(t) εt\hat{z}_h = b_{h,m(t)} + \sum_{\ell=1}^{P^{\max}} \psi_{m(t),\ell} \, \hat{a}_{h,\ell} + \sigma_{m(t)} \, \varepsilon_t

where a^h,ℓ\hat{a}_{h,\ell} is the lag ℓ\ell inflow value passed from the previous stage, and z^h\hat{z}_h enters the rows that read the inflow as a right-hand-side constant (LP Formulation §5). The lag coefficients βh,ℓlag\beta^{lag}_{h,\ell}, which enter the cut when the stage’s cut projection keeps the inflow-lag components, capture the marginal value of inflow history; they are computed from the unscaled duals of the solve by the chain rule — see Cut Management §2 and PAR(p) Folding.

See PAR(p) Inflow Model for the complete autoregressive formulation and State Augmentation §4 for how the lags enter the stage LP.

5.2 Travel-Time and Anticipated-Thermal State Expansion

Seção intitulada “5.2 Travel-Time and Anticipated-Thermal State Expansion”

Two further mechanisms expand the state vector beyond storage and AR lags, and both are carried as Markov state by the same column-bound pinning as the storage — their pinned columns’ reduced costs, each divided by its column’s scale factor, give their cut coefficients.

In-transit water buckets. When a hydro’s main cascade arc carries a travel time, released water reaches its downstream plant only after a delay. The volume in transit is tracked as augmented Benders state — one bucket slot per downstream plant per maturity lag — so that a stage’s future cost depends only on the current in-transit volumes, not on the release path that produced them.

Anticipated-thermal slots. An anticipated thermal commits generation ahead of its delivery stage, by a stage count or a physical lead time. Each commitment decided and not yet delivered holds one slot of the plant’s commitment ring from its decision stage (the first stage, for a commitment decided before the study) to its delivery stage. The ring slots are Markov state so that the cut at each stage prices the commitments already in flight.

Both expansions are optional and instance-specific; see System Element Modeling Overview for the entity configuration and State Augmentation §6 for the in-transit bucket rows and State Augmentation §5 for the anticipated-thermal delivery gating in the stage LP.

One aggregated cut per trial point per iteration:

θt−1≥Qˉt+βˉ⊤(xt−1−x^t−1)\theta_{t-1} \geq \bar{Q}_t + \bar{\beta}^\top (x_{t-1} - \hat{x}_{t-1})

where Qˉt\bar{Q}_t and βˉ\bar{\beta} aggregate the per-scenario terms Qt(x^t−1,ω)Q_t(\hat{x}_{t-1}, \omega) and β(ω)\beta(\omega) of §3.2 with the weights of Cut Management §3: under the expectation, Qˉt=E[Qt(x^t−1,ω)]\bar{Q}_t = \mathbb{E}[Q_t(\hat{x}_{t-1}, \omega)] and βˉ=E[β(ω)]\bar{\beta} = \mathbb{E}[\beta(\omega)], and under a risk measure the risk-adjusted probabilities of Risk Measures §7 replace those weights.

  • Pros: Fewer cuts, a smaller LP and faster solves than a multi-cut formulation (Birge & Louveaux, 1988), which keeps one cut per opening at each trial point
  • Cons: May require more iterations to converge than a multi-cut formulation

Novomodelo implements the single-cut formulation (Cut Management §3).

By default the recursion ends with the terminal condition VT+1(x)=0V_{T+1}(x) = 0 of §2. A study may replace it with a fixed terminal function defined by cuts imported from one pool of an upstream policy, the terminal boundary cuts, which form the terminal stage’s cut pool. The backward pass generates no cut for that pool and none is removed from it, so the function stays fixed for the whole run.

The imported cuts are valid for the upstream model’s cost-to-go, so the study’s lower bound and policy are valid relative to the imported function, the fixed terminal function of the Tier 1 hypotheses. A downstream model that differs from the upstream one is not corrected by training, and the difference biases the policy near the horizon. The imported cuts only bound the future-cost variable from below, so such a difference never makes a stage subproblem infeasible; it changes the value.

The source pool, the compatibility conditions, the carried state and the calendar reconciliation are owned by Post-Study Boundary & Chained Studies.

The methodology above defines the forward/backward pass structure and the execution-model constraints that shape it; the tab below covers how Novomodelo’s software surface configures backward-pass work scheduling.

Novomodelo’s backward-pass work-scheduling knob lives in config.json’s training.parallelism block. This tab shows how the scheduler is chosen; the backward pass and execution model the scheduler distributes work within stay in the methodology sections above (§3.2 Backward Pass, §3.4 Execution Model and Performance Considerations).

training.parallelism — Backward-Pass Scheduler Configuration

Seção intitulada “training.parallelism — Backward-Pass Scheduler Configuration”

The scheduler decides how backward-pass work is split across workers: one trial point per work unit by default, or one (trial point, opening block) pair per work unit with by_node. Under either scheduler the cut set and the training lower bound do not depend on the worker count or on the order in which workers claim the units. The two schedulers chain a trial point’s openings differently, so a solve can start from another basis (LP Warm-Start §2) and, where a stage LP has several optimal solutions, end at another one; the cuts of the two can then differ. The example selects by_node with four openings per block:

{
"training": {
"parallelism": {
"backward_scheduler": { "method": "by_node", "block_size": 4 }
}
}
}

training.parallelism lists the methods, fields, defaults and load errors; By-node scheduling covers when to use by_node and its interaction with the dynamic selection method.

  • Notation Conventions — All index sets, parameters, decision variables, and dual variable definitions
  • LP Formulation — Complete stage subproblem LP that the forward/backward passes solve
  • Policy Graphs — The node/transition/pool generalisation of the stage chain; two probability axes, discount-separate convention, and structural limitations (finite-horizon only, cyclic reserved)
  • Cut Management — Cut generation, aggregation, selection, validity conditions, and the append-only monotonicity guarantee
  • Determinism & Provenance — Read-back canonicalization of the trial-point values onto admissible bounds, and the reproducibility mechanisms (canonical state-block ordering, pinned solve order) it rests on
  • PAR(p) Inflow Model — Stochastic inflow model driving uncertainty in the forward pass
  • PAR(p) Folding — the realized inflow as a right-hand-side constant and the inflow-lag cut coefficients by the chain rule
  • Discount Rate Formulation — Discounted Bellman equation, stage-dependent rates, discount factor on θ
  • Horizon Modes — The reserved cyclic policy-graph target design (season function, cycle convergence inequality, season-indexed cut pool, fixed-point Bellman operator) that the finite-horizon-only restriction in Policy Graphs anticipates
  • Post-Study Boundary & Chained Studies — the imported terminal function: source pool, compatibility conditions, carried state and calendar reconciliation
  • Upper Bound Evaluation — Upper bound estimation methods
  • Stopping Rules — Convergence criteria that terminate the iterative process
  • Risk Measures — CVaR and risk-averse extensions to the Bellman recursion
  • Penalty System — Recourse slacks and the precondition under which they keep every stage LP feasible (relatively complete recourse)
  • Equipment-Specific Formulations — Thermal equipment modelling
  • Scenario Generation — Fixed opening tree, sampling scheme abstraction, enumerated scenario trees
  • Running Novomodelo: Running Studies — the software workflow that trains and runs this algorithm.