SDDP Algorithm

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.

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

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

$$\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:

$$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 $V_{T+1}(x) = 0$, which a study may replace with an imported terminal function (§7).

Key insight: The value function $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)$), tightening the outer approximation toward the true convex cost-to-go function.

3. The SDDP Algorithm

SDDP iteratively builds piecewise-linear approximations $\underline{V}_t^k$ at iteration $k$ 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 $t$ it solves every (child, opening) pair at each trial point $\hat{x}_{t-1}$, aggregates one cut per trial point for stage $t-1$ and synchronizes the ranks so that each holds these cuts before it moves to stage $t-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+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).

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 $M$ independent scenario trajectories:

1. Start from the known initial state $x_0$ (initial storage volumes and inflow history)
2. At each stage $t = 1, \ldots, T$, sample a scenario realization $\omega_t$ from the stage’s scenario set, then solve the stage LP using the incoming state $\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 $\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 $t$
4. Pass $\hat{x}_t$ as the incoming state to stage $t+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 $M$ trajectories; every node of such a graph carries a single opening, which step 2 takes as the stage’s realization (Policy Graphs §6).

Scenario sampling

“Sample a scenario realization $\omega_t$” is controlled by the forward sampling scheme, which determines the forward pass noise source and is chosen independently for each stochastic class. There are four schemes: in-sample, the default, draws a random index $j \in \{1, \ldots, N_{\text{openings}}\}$ from the fixed opening tree — a set of pre-generated noise vectors generated once before training begins; out-of-sample draws fresh noise from the same distribution under an independent seed; external draws from a supplied scenario file; and historical, for the inflow class only, replays historical realizations. See Scenario Generation §3.2 for the schemes.

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

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

Warm-starting: The forward pass LP solution at stage $t$ provides a near-optimal basis for the backward pass solves at the same stage, significantly reducing solve times.

State canonicalization: The recorded outgoing state $\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 $\hat{x}_{t-1}$, and the cut intercept anchored at it (see Cut Management). This is what makes $\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.

3.2 Backward Pass

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

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

1. Solve the stage $t$ LP for every scenario $\omega \in \Omega_t$ (branching), using the trial state $\hat{x}_{t-1}$ as incoming state
2. From each LP solution, extract the optimal objective value $Q_t(\hat{x}_{t-1}, \omega)$ and the reduced costs of the pinned incoming-state columns. The incoming-storage and AR-lag reduced costs enter the cut when the stage’s cut projection keeps those components; the in-transit water-bucket and anticipated-thermal-slot reduced costs always do (State Augmentation §7). These reduced costs give the cut coefficients directly — no combination with FPHA or generic constraint duals is needed. See Cut Management
3. Compute per-scenario cut terms $(Q_t(\hat{x}_{t-1}, \omega), \beta(\omega))$ at the trial point, each coefficient of $\beta(\omega)$ being the reduced cost of step 2 divided by its column’s scale factor (Cut Management §2)
4. Aggregate the per-scenario cut terms into a single cut. On a policy graph, the cut of a node $n$ aggregates every (child, opening) pair $(n', \omega)$ of $n$, weighted by $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(\omega)$ over $\Omega_t$. See Cut Management §3
5. Add the aggregated cut to stage $t-1$‘s cut pool

Backward branching

“Every scenario $\omega \in \Omega_t$” refers to all $N_{\text{openings}}$ noise vectors in the fixed opening tree for stage $t$. This is the Complete backward sampling scheme — the backward pass evaluates ALL openings (the same set across all iterations), regardless of the forward pass noise source. An alternative variant would sample $n_{\text{sample}}$ openings instead of the full tree; Novomodelo uses the Complete scheme because it guarantees that cut coefficients average over the full scenario distribution at each stage. On a policy graph, the backward pass evaluates every opening of every child of the node, and the aggregation weights $P(n \to n')\, p_{n'}(\omega)$ of Cut Management §3 are uniform within each child’s openings; on the stage chain they are the uniform probabilities $p(\omega) = 1/N_{\text{openings}}$ of these openings. See Scenario Generation.

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

Feasibility

Every backward LP solve must be feasible. This is guaranteed by the recourse slack system (Category 1 penalties) — see Penalty System. Relatively complete recourse keeps every backward solve feasible; cut validity needs the conditions of Cut Management §4.

Discount factor

When discount rates are active, the discount factor is applied to the $\theta$ variable in the stage $t-1$ objective (i.e., $d_{t-1 \to t} \cdot \theta$), not to the cut coefficients. The cuts themselves remain unmodified. See Discount Rate Formulation.

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

Lower Bound: $\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 $\bar{z}_{\text{exact}}$ over every leaf path, with no sampling error (see Upper Bound Evaluation). The sampled-mean form:

$$\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 $d_{1 \to t}$ is the cumulative discount factor of stage $t$ (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

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-$t$ solves are complete, and synchronized across ranks, before any stage-$(t-1)$ solve starts, so every stage-$(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 dynamic cut selection, once it is active, 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

The stage chain used throughout this chapter — one node per stage $t \in \{1, \ldots, T\}$, connected by transitions of probability $1$, terminating at $V_{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.

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	$v_h$	$N_{hydro}$	Reservoir volume at end of stage
AR inflow lags	$a_{h,\ell}$	$N_{hydro} \cdot P^{\max}$	Lagged inflows of the AR($P_h$) models, stored $P^{\max}$ per hydro (State Augmentation §4)
In-transit water buckets	$b^{\mathrm{out}}_{h,d}$	$B$	Released water still in transit under travel-time delay — one bucket per receiving plant $h$ per maturity lag $d$
Anticipated-thermal slots	$x^{\mathrm{a}}_{s,i}$	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 — each is pinned by column bounds on its incoming-state column, and the reduced cost of that column gives its cut coefficient (section 3.2).

5.1 AR Lag State Expansion

The PAR(p) inflow model requires past inflows $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 pinned by column bounds to the corresponding incoming state value:

$$\underline{a}_{h,\ell} = \bar{a}_{h,\ell} = \hat{a}_{h,\ell} \quad \forall h \in \mathcal{H}, \; \ell \in \{1, \ldots, P^{\max}\}$$

where $\hat{a}_{h,\ell}$ is the lag $\ell$ inflow value passed from the previous stage. The reduced costs of these pinned columns, each divided by its column’s scale factor, give the lag coefficients $\beta^{lag}_{h,\ell}$, which enter the cut when the stage’s cut projection keeps the inflow-lag components, capturing the marginal value of inflow history — see Cut Management §2.

See PAR(p) Inflow Model for the complete autoregressive formulation and State Augmentation §4 for how these constraints appear in the stage LP.

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 AR lags — 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

One aggregated cut per trial point per iteration:

$$\theta_{t-1} \geq \bar{Q}_t + \bar{\beta}^\top (x_{t-1} - \hat{x}_{t-1})$$

where $\bar{Q}_t$ and $\bar{\beta}$ aggregate the per-scenario terms $Q_t(\hat{x}_{t-1}, \omega)$ and $\beta(\omega)$ of §3.2 with the weights of Cut Management §3: under the expectation, $\bar{Q}_t = \mathbb{E}[Q_t(\hat{x}_{t-1}, \omega)]$ and $\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, 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

By default the recursion ends with the terminal condition $V_{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.

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.

Configure

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

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. The choice changes neither the cut set nor the training lower bound. 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 Dynamic Cut Selection.

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
• 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 guaranteeing feasibility (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.