SDDP Algorithm
Purpose
Seção intitulada “Purpose”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.
1. Problem Context
Seção intitulada “1. Problem Context”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
2. Multistage Stochastic Programming Formulation
Seção intitulada “2. Multistage Stochastic Programming Formulation”The hydrothermal dispatch problem is formulated as a multistage stochastic program:
subject to stage-linking constraints and uncertainty realization. The nested formulation uses value functions:
with terminal condition , which a study may replace with an imported terminal function (§7).
Key insight: The value function 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 ), tightening the outer approximation toward the true convex cost-to-go function.
3. The SDDP Algorithm
Seção intitulada “3. The SDDP Algorithm”SDDP iteratively builds piecewise-linear approximations at iteration 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 it solves every (child, opening) pair at each trial point , aggregates one cut per trial point for stage and synchronizes the ranks so that each holds these cuts before it moves to stage . 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 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).
3.1 Forward Pass
Seção intitulada “3.1 Forward Pass”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 independent scenario trajectories:
- Start from the known initial state (initial storage volumes and inflow history)
- At each stage , sample a scenario realization from the stage’s scenario set, then solve the stage LP using the incoming state and the sampled scenario. The LP includes all current Benders cuts as constraints on the future cost variable
- Record the optimal state (end-of-stage storage volumes and updated AR lags), canonicalized onto its admissible bounds (see below), as the trial point for stage
- Pass as the incoming state to stage
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 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 at each stage for each trajectory, and (b) stage costs for upper bound estimation.
Parallelization: Forward trajectories are independent — Novomodelo distributes 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 seeds the backward pass solves of stage at the same trial point, reducing their solve times (LP Warm-Start).
State canonicalization: The recorded outgoing state 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 , and the cut intercept anchored at it (see Cut Management). This is what makes 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.
3.2 Backward Pass
Seção intitulada “3.2 Backward Pass”The backward pass improves the value function approximation by generating new Benders cuts, walking stages in reverse order from down to and adding cuts to stages down to .
At each stage , for each trial point collected during the forward pass:
- Solve the stage LP for every scenario (branching), using the trial state as incoming state
- From each LP solution, extract the optimal objective value , 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
- Compute per-scenario cut terms at the trial point, each storage, bucket and slot coefficient of 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)
- Aggregate the per-scenario cut terms into a single cut. On a policy graph, the cut of a node aggregates every (child, opening) pair of , weighted by , 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 over . See Cut Management §3
- Add the aggregated cut to stage ‘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).
3.3 Convergence Monitoring
Seção intitulada “3.3 Convergence Monitoring”Lower Bound: 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 over every leaf path, with no sampling error (see Upper Bound Evaluation). The sampled-mean form:
where is the cumulative discount factor of stage (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- solves are complete, and synchronized across ranks, before any stage- solve starts, so every stage- 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.
4. Policy Graph Structure
Seção intitulada “4. Policy Graph Structure”The stage chain used throughout this chapter — one node per stage , connected by transitions of probability , terminating at 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.
5. State Variables and the Markov Property
Seção intitulada “5. State Variables and the Markov Property”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:
| Component | Variable | Count | Description |
|---|---|---|---|
| Hydro storage | Reservoir volume at end of stage | ||
| AR inflow lags | Lagged inflows of the AR() models, stored per hydro (State Augmentation §4) | ||
| In-transit water buckets | Released water still in transit under travel-time delay — one bucket per receiving plant per maturity lag | ||
| Anticipated-thermal slots | one ring per anticipated plant | Commitments 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).
5.1 AR Lag State Expansion
Seção intitulada “5.1 AR Lag State Expansion”The PAR(p) inflow model requires past inflows 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,
where is the lag inflow value passed from the previous stage, and enters the rows that read the inflow as a right-hand-side constant (LP Formulation §5). The lag coefficients , 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.
6. Single-Cut Formulation
Seção intitulada “6. Single-Cut Formulation”One aggregated cut per trial point per iteration:
where and aggregate the per-scenario terms and of §3.2 with the weights of Cut Management §3: under the expectation, and , 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).
7. Terminal Boundary Cuts
Seção intitulada “7. Terminal Boundary Cuts”By default the recursion ends with the terminal condition 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.
Implementation in Novomodelo
Seção intitulada “Implementation in Novomodelo”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.
Cross-References
Seção intitulada “Cross-References”- 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.