Cut Management

Purpose

This chapter defines the complete Benders cut lifecycle in Novomodelo: what cuts represent mathematically, how cut coefficients relate to LP dual variables, how per-scenario cuts are aggregated into a single cut, under what conditions cuts are valid, and what selection strategies are available to control cut pool growth.

1. Cut Definition

A Benders cut at stage $t-1$ is a linear inequality that provides a lower bound on the cost-to-go function $V_t(x)$ under the validity conditions of §4:

$$\theta \geq \beta_0 + \beta^{\top} x$$

where:

• $\theta$ is the future cost variable in the stage $t-1$ LP
• $\beta_0$ is the cut intercept
• $x$ is the vector of the state components the cut projects onto, and $\beta$ the vector of their cut coefficients, one per component
• $\beta^v_h$ is the storage coefficient for hydro $h$ (marginal value of water)
• $\beta^{lag}_{h,\ell}$ is the AR lag coefficient for hydro $h$, lag $\ell$ (marginal value of inflow history)
• $v_h$, $a_{h,\ell}$ are the storage and AR-lag state variables (see State Augmentation §1)

The cut carries a coefficient for each enabled state dimension: the storage $v_h$ and the inflow lags $a_{h,\ell}$ when the stage’s projection selection keeps them (State Augmentation §7), and the in-transit travel-time buckets and commitment-ring slots, when present, always. A cut is stored densely over the components it projects onto: every such component carries a coefficient in every cut, read from the reduced cost of its pinned column (§2), and a coefficient may be zero; the cut’s LP row omits the components whose coefficient is structurally zero.

Novomodelo adds cuts monotonically across iterations: an active cut is never removed from the lower-bound LP within a training run. Because the cut set only grows, the lower-bound estimate is non-decreasing across iterations of a training run. This is a methodology-level guarantee — the outer approximation of the value function can only become tighter iteration by iteration.

2. Reduced-Cost Extraction

After solving the stage $t$ subproblem for trial state $\hat{x}_{t-1}$ and scenario $\omega_t$, the cut coefficients are derived from the LP reduced costs of the pinned incoming-state columns — the columns whose lower and upper bounds were set equal to the incoming state value (see State Augmentation §2).

Both storage and inflow lags use the same pattern: an incoming-state LP variable is pinned to the trial value by equal column bounds, and the reduced cost of that column gives the cut coefficient directly:

Pinned column	Reduced cost	Cut coefficient	Units
Incoming storage (hydro $h$)	$\bar{c}^{in}_h$	$\beta^v_{t,h} = \bar{c}^{in}_h / d^{col}_h$	$/hm³
AR lag (hydro $h$, lag $\ell$)	$\bar{c}^{lag}_{h,\ell}$	$\beta^{lag}_{t,h,\ell} = \bar{c}^{lag}_{h,\ell} / d^{col}_{h,\ell}$	$/(m³/s)

where $d^{col}$ is the per-column prescaler factor that unscales the reduced cost; a further factor $K$ converts to original cost units at the reporting boundary (see LP Layout and Scaling §2). When the study has in-transit water or anticipated thermals, each incoming bucket column and each incoming commitment-ring slot column contributes one coefficient by the same rule; the coefficient multiplies the matching outgoing column of the cut’s stage (State Augmentation §3; State Augmentation — Ring-Slot Cut Coefficient).

The cut intercept ensures the cut passes through the trial point:

$$\beta_{0,t} = Q_t(\hat{x}_{t-1}, \omega_t) - \beta_t^{\top} \hat{x}_{t-1}$$

where $Q_t(\hat{x}_{t-1}, \omega_t)$ is the optimal objective value of the stage $t$ subproblem and the product $\beta_t^{\top} \hat{x}_{t-1}$ runs over the components the cut projects onto (§1), each coefficient paired with the trial value of its own component: storage and inflow lags when the stage keeps them, buckets and ring slots always. A component the cut projects out contributes no product term; its linear term at the trial value is folded into the intercept (§4, condition 4). The trial state $\hat{x}_{t-1}$ this intercept is anchored at is the canonicalized (read-back-clamped) outgoing state of the previous stage’s forward solve — its LP primal projected onto its admissible bounds — so the pinned incoming-state columns and the intercept share one in-box anchor (see SDDP Algorithm §3.1).

Sign convention: By the LP envelope theorem, $\partial Q_t / \partial \hat{x}_j = \beta_j$, the sensitivity of the optimal value to the pinned incoming state. For a column pinned at $\underline{x}_j = \bar{x}_j = \hat{x}_j$, that sensitivity is exactly the column’s reduced cost — equal, by KKT parity, to the multiplier the equivalent equality row $x^{in}_j = \hat{x}_j$ would have carried — so the cut coefficient is taken directly from the reduced cost with no sign flip (after the per-column unscaling above). The reduced cost automatically captures all downstream effects: for storage, this includes contributions from the water balance, FPHA hyperplanes, the evaporation row, and any generic constraints that reference the incoming storage variable $v^{in}_h$ (see LP Formulation).

Storage coefficient sign: more incoming storage lowers $Q_t$ wherever the extra water displaces thermal generation or deficit, in this stage or a later one, so the storage coefficient is non-positive there; it can turn positive where the extra water can only leave the reservoir at a cost, such as a spillage cost or an outflow-limit penalty.

Design note

Pinning an incoming-state column to the trial value and reading its reduced cost gives the sensitivity directly. Novomodelo realises it through column bounds rather than an equality row: a bound-pinned column’s reduced cost is the sensitivity, which removes the $N(1+P^{\max})$ redundant equality rows per stage, plus one per bucket and ring slot, while keeping the property that one value per state coordinate captures all downstream effects automatically. See State Augmentation §2.

Cut dimension: the enabled state subset

Each stage’s cuts project onto the state components its selection keeps — the storage and the inflow lags as each stage selects them, the in-transit buckets and the commitment-ring slots always — as defined in State Augmentation §7.

In a multi-rank run each stage’s cut synchronization derives its wire layout from that stage’s own cut dimension. The Configure tab under Implementation in Novomodelo lists the per-stage field.

3. Single-Cut Aggregation

In the single-cut formulation, the per-outcome cuts of the backward pass are aggregated into one cut per trial point. The cut of a policy-graph node $n$ (Policy Graphs) aggregates over the pairs $(n', \omega)$ formed by every child $n'$ of $n$ and every opening $\omega \in \Omega_{n'}$ of that child, each pair weighted by the product $P(n \to n')\, p_{n'}(\omega)$ of the transition probability from $n$ to $n'$ and the probability of opening $\omega$ within $n'$. Under the expectation, the aggregated cut is the expectation of the per-pair cuts under that joint law:

$$\bar{\beta}_0 = \sum_{(n', \omega)} P(n \to n')\, p_{n'}(\omega)\, \beta_0(n', \omega)$$ $$\bar{\beta} = \sum_{(n', \omega)} P(n \to n')\, p_{n'}(\omega)\, \beta(n', \omega)$$

where $\beta_0(n', \omega)$ and $\beta(n', \omega)$ are the intercept and the coefficient vector of the cut read from child $n'$‘s subproblem under opening $\omega$ at the trial point (§2). The coefficient sum is a vector sum over every component the cut projects onto (§1): the storage and the inflow lags when the projection keeps them, and the in-transit buckets and the commitment-ring slots always. Under a risk measure, the products $P(n \to n')\, p_{n'}(\omega)$ are replaced by the risk-adjusted probabilities of Risk Measures, computed on that same joint law: the risk measure of node $n$‘s stage acts once on all the pairs together, never on each child’s openings separately with the results then averaged across the children.

On the stage chain every non-leaf node has a single child, reached with probability $1$, so the pairs are the openings $\omega \in \Omega_t$ of stage $t$ and their weights are the uniform $p(\omega)$: the aggregation runs over one stage’s openings.

Opening tree correspondence

The per-pair cuts $\beta_0(n', \omega)$, $\beta(n', \omega)$ correspond to the openings of each child: the noise vectors the fixed opening tree — a pre-generated set of branchings created once before training begins — holds for the child, or the single externally supplied realization of a child that carries one. The backward pass always evaluates every opening of every child, so the weights are uniform within each child’s openings, $p_{n'}(\omega) = 1/|\Omega_{n'}|$, which on the stage chain is $p(\omega) = 1/N_{\text{openings}}$. See Scenario Generation.

The aggregated cut $(\bar{\beta}_0, \bar{\beta})$ is added to node $n$‘s cut pool, which on the stage chain is the cut pool of stage $t-1$.

Discount factor

When the problem uses stage-dependent discount rates, discounting is applied to the $\theta$ variable in the stage $t-1$ objective function (i.e., $d_{t-1 \to t} \cdot \theta$), rather than scaling the cut coefficients directly. This is simpler — the cuts remain unmodified and the discount factor appears only in the objective. See Discount Rate Formulation for the discounted Bellman equation and how discount factors interact with cut generation.

Multi-cut formulation

Novomodelo implements the single-cut formulation above, with one future-cost variable per stage; it implements no multi-cut variant.

4. Cut Validity

A cut is valid if it is a lower bound on the true cost-to-go function everywhere in the feasible state space:

$$\beta_{0,i} + \beta_i^\top x \leq V_{t+1}(x) \quad \forall x \in \mathcal{X}_t$$

Here $\beta_i$ is read as zero on every component the cut projects out, so the cut is constant in those components.

Validity conditions: The cuts generated by SDDP are valid under:

1. Convexity of the cost-to-go in the incoming state — the incoming state enters each stage problem affinely, through the bounds of its pinned columns; Tier 1 names what breaks it.
2. Relatively complete recourse — feasibility for all states and scenarios. In Novomodelo, this is guaranteed by the recourse slack system (Category 1 penalties): every constraint that could be violated by exogenous uncertainty has a penalty slack variable, ensuring the LP is always feasible. See Penalty System.
3. Correct sensitivity extraction — the reduced costs used as cut coefficients must come from an optimal LP solution (not an infeasible or unbounded one)
4. Cuts span every state component the cost-to-go depends on — the intercept absorbs the contribution of every component the cut projects out (State Augmentation §7), at its trial value, so the cut is guaranteed to lie below the cost-to-go only on the slice through the trial point where those components keep their trial values. When the cost-to-go depends on such a component, as it depends on the inflow lags under a PAR(p > 0) model, $\underline{z}^k$ is not guaranteed to be a lower bound and the gap is not a certificate.

When Bounds and Certificates Hold

Three guarantees attach to the bounds SDDP reports, each under its own hypotheses: a valid lower bound, the convergence of that bound, and a certificate on the gap between the two bounds. Tiers 2 and 3 each require Tier 1. The table summarizes the three tiers; the subsections state every hypothesis and what breaks it.

Tier	What holds	Requires	Broken by
1. Valid lower bound	$\underline{z}^k$ is at most the optimal value of the model as trained	A cost-to-go convex in the incoming state and non-negative; relatively complete recourse; cuts exact at their trial points and spanning every state component the cost-to-go depends on; a fixed terminal function	A truncation inflow non-negativity method under PAR(p > 0); a cut that omits a state component the cost-to-go depends on; a cost-to-go that takes negative values
2. Convergence	$\underline{z}^k$ converges to that optimal value with probability 1 under an expectation measure at every stage	Tier 1; finitely many openings at every node; a forward pass that samples the backward pass’s scenario paths or enumerates them; a selection that preserves the approximation at every visited state	A forward pass that draws from another distribution; periodic pruning over recent trial points only; a per-stage cap on active cuts; a finite $k_1$; a DCS solve that reaches its round cap
3. Gap certificate	$\bar{z}^k - \underline{z}^k$ bounds the optimality gap of the policy	Tier 1; an exact upper bound on the same tree under the same measure: an enumerated forward pass and a measure uniform across stages	A sampled, out-of-sample, historical or external upper bound; a measure that varies across stages

Tier 1: Valid Lower Bound

At every iteration $k$, $\underline{z}^k$ is at most the optimal value of the model as trained, under the nested risk-adjusted objective of Risk Measures. It rests on these hypotheses:

• Convexity. The cost-to-go of every stage is convex in the incoming state: the incoming state enters each stage problem affinely, through the bounds of its pinned columns. The truncation methods of Inflow Non-Negativity Solution Methods break this in the inflow-lag components under a PAR(p > 0) model, because the noise floor they impose is solved from the trial point’s lags; keeping the lag components in the cut does not restore it. Without a non-negativity method, or with the penalty method, the inflow stays affine in the lags.
• Relatively complete recourse. Every stage problem is feasible for every incoming state and realization, which the penalty slacks of Penalty System provide.
• Exact cuts. Every cut is exact at its trial point and below the risk-adjusted cost-to-go everywhere: the backward pass solves the stage problem of every successor–opening pair to optimality and combines their cuts with probabilities from the risk set of the stage’s coherent risk measure that attain that measure at the trial point.
• Full state span. The cuts span every state component the cost-to-go depends on. When a component the cost-to-go depends on is projected out of the cut (State Augmentation §7), the cut is guaranteed to lie below the cost-to-go only where that component equals its trial value.
• Non-negative cost-to-go. The cost-to-go of every stage is non-negative. The future-cost variable $\theta$ is bounded below by zero, so the approximation lies below the cost-to-go only where that cost-to-go is non-negative.
• Fixed terminal function. The terminal function is fixed for the whole run: zero, or an imported terminal boundary (Post-Study Boundary & Chained Studies).

Tier 2: Convergence

Under an expectation measure at every stage, $\underline{z}^k$ converges to the optimal value of the model as trained with probability 1. It requires the hypotheses below; §9 states the theorem, which is proved for that case. Under a risk-averse measure at any stage, Tier 1 still bounds the optimal value from below, but the cited theorem does not establish the convergence of $\underline{z}^k$.

• Tier 1 holds, and every node has finitely many openings.
• The forward pass either draws the backward pass’s own scenario paths, each with positive probability, or enumerates them. A forward pass that draws from another distribution, such as out-of-sample noise, historical records or external scenarios, is outside the theorem’s hypotheses.
• The selection preserves the value of the approximation at every visited state, within the tie tolerance of §6: no selection, Level-1, LML1 or Domination evaluated over all visited states, or DCS with an unbounded candidate window, $k_1 = \infty$, whose solves stop before the round cap of §8.3.

Four features of cut selection on this page leave the last hypothesis:

• Periodic pruning (§7) scores the cuts only at the trial points of recent iterations. Under a sampled forward pass, the archive it scores holds the trial points of at most the last two selection intervals of $n_{\text{sel}}$ iterations each; under an enumerated forward pass, each iteration adds one trial point per node, so the same window spans as many times more iterations as the tree has paths, and is still finite.
• A per-stage cap on the number of active cuts deactivates the cuts that were binding least recently once the cap is exceeded, whatever their value at the visited states; only the cuts of the current iteration are exempt.
• With a finite $k_1$ (§8.2), DCS never scores a cut generated $k_1$ or more iterations earlier, so its loop can stop with a violated old cut left out.
• A DCS solve that reaches the round cap (§8.3) ends with a closing solve whose optimum is not checked against the omitted cuts.

Tier 3: Gap Certificate

$\bar{z}^k - \underline{z}^k$ bounds from above the optimality gap of the policy, the difference between the policy’s risk-adjusted cost and the optimal value. It requires Tier 1 and an exact upper bound on the same tree under the same measure: an enumerated forward pass, which evaluates the policy on every path of the tree the backward pass uses, and a measure uniform across stages, either expectation at every stage or one CVaR measure, with the same risk-aversion weight and tail fraction, at every stage; a stage whose risk-aversion weight is zero is the expectation whatever its tail fraction. A sampled, out-of-sample, historical or external estimate is not a certificate: it carries sampling error or evaluates another distribution, and it can fall below $\underline{z}^k$. See Optimality gap for the gap and Upper Bound Evaluation for the exact bound.

5. Cut Growth and Selection Motivation

The number of cuts grows as $\mathcal{O}(\text{iterations} \times N_{\text{forward\_passes}})$. Many older cuts become redundant as newer, tighter cuts are generated. Without selection, the number of cut rows the LP carries grows linearly with iteration count.

Append-only pool with stable slots: Cuts are never deleted. Every cut ever generated is retained for the lifetime of the run at a stable, deterministic slot index — the slot is a fixed function of the iteration and forward-pass index, which is what makes the cut order reproducible across runs and rank counts (see Determinism & Provenance). The pool is never compacted.

Deactivation mechanism (periodic-pruning methods): deactivation is a pool activity flag on a stable slot — it mutates no LP row or bound. A deactivated cut keeps its slot but is excluded from the per-iteration template rebake, so only active cuts are encoded as LP rows on each forward/backward solve. The persistent lower-bound LP is append-only: its cut rows are never removed (so the lower bound stays monotone), and each row keeps constraining once appended. Because the slot index is preserved, reactivation is exact: a cut that selection later restores is re-baked into the template at the same slot, with the coefficients it was generated with.

Two families of selection strategy are available. Periodic-pruning methods (Level-1, LML1, Domination) run a value-evaluation pass after each $n_{\text{sel}}$-th iteration and deactivate redundant cuts from the pool. Dynamic Cut Selection (DCS) takes a different approach: it keeps the pool entirely append-only — never deactivating any cut — and instead controls which cuts are resident in each individual stage LP solve (§8).

6. Cut Activity

Cut selection works from a value-evaluation view of activity. At a visited forward-pass trial point $\hat{x}$, each cut’s value is $\beta_{0,i} + \beta_i^\top \hat{x}$, and the per-state best value is

$$V^*(\hat{x}) = \max_i \left\{ \beta_{0,i} + \beta_i^\top \hat{x} \right\}$$

taken over all populated cuts, active and inactive. A cut is active (near-optimal) at $\hat{x}$ when its value lies within a tolerance band of the best:

$$\text{cut } i \text{ is active at } \hat{x} \iff V^*(\hat{x}) - (\beta_{0,i} + \beta_i^\top \hat{x}) \le \epsilon$$

This is equivalent to the cut being binding (or near-binding) at the LP optimum reached from $\hat{x}$ — a cut at the per-state maximum is the one the future-cost variable $\theta$ rests on. The tolerance $\epsilon$ is the strategy’s tie-breaking band: tie_tolerance for Level-1/LML1, domination_tolerance for Domination (§10).

Tolerance	Effect
0	Only exact-maximum cuts count as active
small	Cuts tied within rounding of the maximum are all kept active
larger	Wider near-optimal band retained
very large	All cuts considered active (no deactivation)

7. Periodic-Pruning Strategies

Three periodic-pruning strategies are available, and all three share one value-evaluation kernel: every populated cut (active and inactive) is evaluated at every visited trial point, the per-state maximum is taken, and a per-state survival rule decides which cuts to keep. The rule decides only over the eligible cuts: every cut except those loaded from a warm-start policy and those generated in the current iteration, which the rule never deactivates. The per-state maximum still runs over all populated cuts. Pruning scores the pool of every node except the first stage’s and the shared terminal pool: periodic pruning never deactivates a first-stage cut, and the backward pass adds no cut to the terminal pool. The kernel treats deactivation and reactivation symmetrically — in a single pass, a selected cut that is currently inactive is reactivated and an active cut not selected anywhere is deactivated. It is bit-deterministic regardless of thread count (see Determinism & Provenance).

Visited-states window: these strategies score cuts against the trial points held in the visited-states archive. To bound memory on long runs, the archive keeps at each node only its most recent trial points, $n_{\text{sel}}$ times as many as there are forward passes per iteration. Under a sampled forward pass, each iteration adds one trial point per forward pass at each node, so the window covers the last $n_{\text{sel}}$ iterations. Under an enumerated forward pass, the forward passes are the paths of the tree and each iteration adds one trial point per node, so the window covers $n_{\text{sel}}$ times as many iterations as the tree has paths. After each selection run the archive is trimmed to that window, so a selection run sees up to about two windows of accumulated states before the trim; older trial points are then evicted. Dynamic Cut Selection (§8) does not use this archive.

7.1 Level-1

At each visited trial point, every cut within tie_tolerance of the per-state maximum value survives; the selected set is the union of these near-maximum cuts across all visited states. A cut is deactivated only if, at every visited state, its value is more than tie_tolerance below the maximum there. This strategy was originally proposed by de Matos, Philpott & Finardi (2015).

Properties:

• Keeps every eligible cut that is within tie_tolerance of the maximum at some visited state
• Preserves the convergence guarantee of section 9 when it scores every visited state; the visited-states window above scores only recent ones (Tier 2)

7.2 Limited Memory Level-1 (LML1)

Like Level-1, but at each visited state only the single oldest eligible cut within tie_tolerance of the maximum survives (oldest = smallest slot index among non-warm-start cuts). The selected set is the union of these oldest-at-maximum cuts across visited states. Bandarra & Guigues (2021).

Properties:

• Keeps at most one cut per visited state, the oldest eligible cut within tie_tolerance of the maximum there; at the same tolerance, over the same pool and visited states, the cuts it keeps are a subset of those Level-1 keeps
• Preserves the convergence guarantee of section 9 when it scores every visited state; the visited-states window above scores only recent ones (Tier 2)

7.3 Domination

A cut is dominated if, at every visited state, the maximum over all populated cuts exceeds its value by more than domination_tolerance. Dominated cuts contribute nothing to the policy at any visited state and are deactivated; inactive cuts within domination_tolerance of the maximum somewhere are reactivated. Formally, cut $i$ is dominated when

$$\max_{i' \neq i} \left\{ \beta_{0,i'} + \beta_{i'}^\top \hat{x} \right\} - \left( \beta_{0,i} + \beta_i^\top \hat{x} \right) > \text{domination\_tolerance} \quad \forall \hat{x} \in \text{visited states}$$

Domination applies the Level-1 survival test with its own tolerance $\epsilon$ (domination_tolerance, §10), so, over the same pool and visited states, the two select the same cuts when the two tolerances are equal.

Properties:

• Cost is $\mathcal{O}(|\text{cuts}| \times |\text{visited states}|)$ per stage per check; the kernel evaluates it as a dense matrix product distributed across threads
• May deactivate cuts that would be active at unvisited states; the convergence argument of §9 uses the approximation only at the visited trial points

8. Dynamic Cut Selection

Dynamic Cut Selection (DCS) is mutually exclusive with the periodic-pruning methods (Level-1, LML1, Domination). DCS is also inadmissible under an enumerated forward pass: the pairing is rejected at study setup with a named validation error, whose reason the Implementation notes tab under Implementation in Novomodelo gives. Unlike the periodic-pruning methods, DCS never deactivates cuts from the pool — it keeps the pool entirely append-only and controls only which cuts are resident in each stage LP at solve time.

Motivation: when a stage’s pool is large, solving each stage LP with every active cut dominates the run time. DCS keeps the whole pool and solves each LP with a small resident subset of it, grown until no omitted cut is violated at the solution or a round cap is reached (§8.3), so a solve that stops on no violation returns the optimum of the solve with the whole pool when every pool cut is a candidate (§8.2). It pairs only with a sampled forward pass, as the setup check above enforces.

8.1 Per-solve procedure

At iteration $k$, the DCS loop for one (stage, solve) is:

1. Seed the resident set with cuts that were active at this stage within the last $k_2$ iterations (the seed window), plus all cuts generated in the current iteration. The seed is derived only from synchronized per-slot pool metadata, the iteration each cut was last active and the iteration it was generated, never from a per-worker solve trace. This makes the seed bit-identical across thread and MPI-rank counts.

2. Solve the stage LP with the current resident set. Let $x^*$ be the optimal state vector and $\theta^*$ the optimal future-cost value.

3. Score the omitted (non-resident) candidate cuts. Cut coefficients are stored in raw (unscaled) space while the LP solves in scaled space, so both $\theta^*$ and each state column must first be unscaled: each scaled value $x_{\text{scaled}}$ is multiplied by its column scaling factor, the $d^{col}$ of §2, to give $x_{\text{raw}}$. For candidate cut $i$ with intercept $\beta_{0,i}$ and slope $\beta_i$, the future-cost floor it would impose at $x^*$ is

   $$f_i = \beta_{0,i} + \beta_i^\top x^*_{\text{raw}}$$

   The candidate is violated iff $f_i - \theta^*_{\text{raw}} > \varepsilon_{\text{viol}}$ (strict). This follows from the cut-row convention $-\beta^\top x + \theta \ge \beta_0$.

4. Add the top $n_{\text{adic}}$ most-violated candidates (sorted by violation magnitude descending, ties broken by ascending slot id). Warm re-solve from the retained basis and return to step 2.

5. Stop when no candidate is violated. At this point the resident-subset optimum equals the full-pool optimum — every omitted cut is satisfied — so the result is exact. Backward duals and forward primals are extracted from this final LP.

8.2 Candidate-recency window

By default every pool cut is a candidate ($k_1 = \infty$), so the window excludes no cut; only the round cap of §8.3 can stop a solve short of the full-pool optimum. A finite $k_1$ restricts candidates to cuts generated within the last $k_1$ iterations. This is a deliberate, inexact speedup: cuts older than the window are never scored or added, even when violated.

8.3 Bounded inner loop and closing solve

The add/re-solve loop is capped at a fixed number of rounds. If the cap is reached with violations remaining, every candidate violated at the last solution is added and one closing solve is performed, with no further scoring. The closing solve’s optimum equals the full-pool optimum only when no omitted cut is violated at it, which it does not check: a candidate satisfied at the last solution can be violated at the new one.

8.4 Pass uniformity and warm-start synergy

DCS applies across the backward pass, the forward pass, and simulation; simulation ignores the window $k_1$ and seeds the resident set with every active cut. Forward and simulation also run the loop to the stop of §8.1 step 5 or the round cap of §8.3 — no earlier stop — to avoid trajectory drift: an earlier stop in the forward pass would shift the states the backward pass visits, producing policy drift.

Each inner re-solve adds only a few rows and restarts from the basis the previous solve left, so the bounded loop stays cheap. The stored basis of LP Warm-Start is not applied to a DCS solve: the first solve of each stage LP starts without a stored basis, and in the backward pass the later openings of a trial point re-solve warm from the LP the previous opening left.

8.5 Zero seed window

A seed window $k_2 = 0$ is valid and meaningful: the resident set is seeded only with cuts generated in the current iteration, with no history (zero-history seeding), and the lazy loop then grows the resident set from scratch each solve. A larger $k_2$ trades a slightly larger initial LP for fewer inner iterations.

8.6 Determinism

The resident-set selection is bit-identical across thread and MPI-rank counts:

• The seed comes from synchronized pool metadata (the iteration each cut was last active and the iteration it was generated), not per-worker traces.
• The optimal state $x^*$ is scenario-deterministic (a function of the LP, not the rank).
• Candidate scoring uses a bit-deterministic batched matrix product.
• The violation sort uses a total ordering with an ascending-slot tie-break, making the top-$n_{\text{adic}}$ selection stable.

See Determinism & Provenance.

9. Convergence Guarantee

Theorem (Bandarra & Guigues, 2021): For an expectation objective at every stage, SDDP with finitely many scenarios and Level-1 or LML1 cut selection evaluated over every visited trial point reaches an optimal first-stage solution after finitely many iterations with probability 1. Domination applies the Level-1 test with its own tolerance (§7.3), so the same argument covers it.

Key insight: Removing cuts that are never active at any visited state does not change the outer approximation at those states, and the convergence argument uses the approximation only there. With finitely many scenarios, only finitely many distinct cuts and trial points can arise, each read from a basic solution of a stage problem, so the argument needs no density of the visited states: convergence is reached after finitely many iterations.

DCS and convergence: a DCS solve that stops at §8.1 step 5 is exact — the optimum it returns equals the full-pool optimum — so such solves do not weaken the convergence argument. That exactness rests on $k_1 = \infty$ (every pool cut remains a candidate); a finite $k_1$ sacrifices it. A solve that reaches the round cap ends with the closing solve of §8.3, whose exactness is not checked.

Tier 2 states the hypotheses on the risk measure, the forward pass and the cut selection that a training run must meet for the theorem to apply, and the selection features that fall outside them.

10. Selection Parameters

The table maps each key of the training.cut_selection object to its symbol on this page, where it has one, and to the methods that read it; training.cut_selection gives each key’s type, default and constraints.

Math symbol	Config key	Applies to
—	row_activity_tolerance	Always-on (top-level)
—	max_active_per_stage	Always-on (top-level)
$\epsilon$	selection.tie_tolerance	level1, lml1
—	selection.check_frequency	level1, lml1, domination
$\epsilon$	selection.domination_tolerance	domination
$k_2$	selection.seed_window	dynamic
$k_1$	selection.candidate_recency	dynamic
$n_{\text{adic}}$	selection.max_added_per_round	dynamic
$\varepsilon_{\text{viol}}$	selection.violation_tolerance	dynamic
—	selection.start_iteration	dynamic

Implementation in Novomodelo

The methodology above defines the complete Benders cut lifecycle; the tabs below cover how Novomodelo’s software surface configures, persists, and manages cuts at runtime.

Configure

Novomodelo’s cut-management settings live in two places: the training.cut_selection block of config.json (row management) and the per-stage state_variables field of stages.json (cut projection). The cut pool itself is generated during training, not authored by the case. This tab shows how each is configured; the selection algorithms themselves stay in the methodology sections above (§6–§9).

training.cut_selection — Row Management Configuration

Row management combines a selection pass, configured by the selection object and off by default, with a per-stage budget pass set by max_active_per_stage. The example runs Level-1 periodic pruning (level1) with a budget of 500 active rows per stage:

{
  "training": {
    "cut_selection": {
      "row_activity_tolerance": 1e-6,
      "max_active_per_stage": 500,
      "selection": {
        "method": "level1",
        "tie_tolerance": 1e-10,
        "check_frequency": 5
      }
    }
  }
}

training.cut_selection lists every field, default and method parameter. Cut Management Pipeline describes the budget pass.

stages[].state_variables — Cut Projection

Each study stage selects which incoming-state dimensions its cuts project onto — the cut-state projection of State Augmentation §7.

Field	Type	Default	Description
storage	boolean	true	Project the cuts onto the storage dimensions.
inflow_lags	boolean	false	Project the cuts onto the inflow-lag dimensions.

With inflow_lags set to true on a stage, the cuts that stage generates also carry the inflow-lag coefficients; with false, they carry no inflow-lag coefficients.

An absent state_variables gives the storage-only default, { "storage": true, "inflow_lags": false }; an unknown field is rejected at load. In-transit buckets and commitment-ring slots are always projected in and have no field.

A study that supplies AR coefficients of order above zero (scenarios/inflow_ar_coefficients.parquet) but has inflow_lags set to false on every study stage, explicitly or by default, draws a ModelQuality validation warning that does not block the run; a PAR model estimated from the inflow history never draws it, because the check runs on the supplied table before estimation. With the lags projected out, the lag columns are still pinned for the AR dynamics, but no cut generated in training carries their coefficients (cuts imported from a boundary policy can).

To keep the inflow lags in the cuts a stage generates, set both fields on that stage:

"state_variables": { "storage": true, "inflow_lags": true }

The full stages[] entry is listed under stages.json.

Inputs & Outputs

This is a topic-scoped index of the files cut management touches. Cuts have no case-directory input file of their own — the only configuration surface is training.cut_selection in config.json (see its configuration entry). The topic’s I/O surface is the policy checkpoint: the FlatBuffers .bin files that persist the cut pool between runs. This tab names that surface and its role; it does not repeat the field-by-field record layout, which is owned by the Reference corpus (Case Format and Output Format pages).

Inputs

There is no case-directory input file for cuts. Two input paths re-read a previous run’s output as cuts:

• Warm-start, resume, and simulation-only — when the run’s policy mode is "warm_start" or "resume", or training is disabled for a simulation-only run, Novomodelo loads policy/cuts/NNN.bin from the checkpoint at policy.path and repopulates the cut pool before training or simulation begins. The load applies the Policy Load Contract, which requires the running novomodelo version to have written the checkpoint (version gate) and leaves out any stored basis that does not fit its stage LP (stored-basis gate). See Implementation notes for how a warm-started cut is tracked once it is back in the pool.
• Boundary source — when policy.boundary.path is set, Novomodelo loads a second checkpoint and injects its terminal cuts as a fixed boundary condition at the study’s terminal stage. The source pool is selected by the study’s terminal boundary date and reconciled onto the current state — lenient by default (surplus source slots dropped and reported), strict-rejectable. The boundary checkpoint must also come from the running novomodelo version (Compatibility requirements lists the check order). See Post-Study Boundary & Chained Studies and Policy Management — Boundary Cuts.

Outputs

File

Role

policy/cuts/NNN.bin

One FlatBuffers binary per pool (NNN is the pool id — on a plain stage chain the 0-based stage position, which is not the declared stage id; on a branching graph the pool id differs from the stage position), root table StageCuts: every cut’s intercept, coefficient vector, and active flag. The coefficient vector is a bare float64[]; each position maps to a state variable via the per-slot entity manifest embedded in the same file (see the Output Format reference). Written every training run and re-read on the next warm-start, resume, or simulation-only run (see Inputs above).

For the complete field-by-field record layout (AffinePiece, StageCuts) and the checkpoint-wide policy/manifest.bin summary, see the Output Format reference page in the Reference corpus. For the schema file itself and per-language flatc codegen recipes (Python, C++, TypeScript, …) to read a checkpoint outside Novomodelo, see the FlatBuffers Policy Schema reference page.

Implementation notes

Non-normative software behavior for cut management — what Novomodelo does at runtime, beyond the equations above. This tab references the methodology body for the derivations rather than restating them.

Reduced-cost unscaling divides by the column scale

Methodology §2 derives each cut coefficient from the reduced cost of a pinned incoming-state column, unscaled by that column’s prescaler factor. In code terms the unscaling step is a division: coefficient = reduced_cost / col_scale[col] (empty col_scale ⇒ the raw reduced cost, unscaled).

Storage-only cut projection

With the inflow lags projected out of the cuts on a stage under a PAR(p > 0) model, $\underline{z}^k$ is not guaranteed to be a lower bound on the optimal value of the model as trained, and the gap is not a certificate (condition 4). Projecting the cuts onto the inflow lags as well, with storage kept, on every stage satisfies condition 4; the remaining hypotheses are those of Tier 1. The projection is chosen per stage: the key and its default are in stages[].state_variables of the Configure tab, and the components each selection projects onto are in State Augmentation §7.

Export writes canonical currency units

Policy export multiplies every cut coefficient and intercept by the writing study’s cost-scale factor, converting the in-memory scaled cost space into canonical currency units at rest. Every load path divides by the loading study’s own factor to bring the values back into that study’s scaled cost space. This is orthogonal to the col_scale reduced-cost unscaling above: col_scale is a per-column LP prescaler applied inside a single solve, while the cost-scale factor is the global objective scaling applied once per study. See Policy Management — Cost-Scale Canonicalization for the load-time rule.

Append-only pool, deterministic slots

Every cut ever generated is retained for the lifetime of the run at a stable slot index — a fixed function of the iteration and forward-pass index that generated it (methodology §5). The pool is never compacted, and nothing is ever deleted from it; “deactivation” always means something narrower than removal (below).

Deactivation excludes a cut from the template; the LB LP is append-only

Novomodelo’s row-management pipeline touches two different LPs, and “deactivating” a cut means something slightly different in each:

• In the per-iteration forward/backward stage LP — rebuilt from the stage template at the start of each solve — a deactivated cut is simply omitted from that iteration’s template rebake. Only active cuts are encoded as LP rows on each forward/backward solve; there is no row to toggle because the row was never emitted.
• In the persistent lower-bound LP the pool is append-only: only active cuts are ever appended, and a cut already present is not re-appended; appended rows are never removed, so the training lower bound stays monotone and every appended row keeps constraining. Deactivation touches no row here; it only changes which cuts the forward/backward template rebake encodes. The only $+\infty$ on a cut row is the ordinary upper bound of the one-sided ≥ cut, present on every active row — not a deactivation sentinel.

Both routes preserve the slot index, which is what makes reactivation exact: a cut that a later selection pass restores is re-baked into the template, at the same slot, with the same coefficients it was generated with.

Selection pass and budget pass, run every iteration

The row-management pipeline runs after each iteration’s backward pass and cut synchronization, in two passes:

1. Selection pass (level1 / lml1 / domination) — gated by check_frequency; runs only at iterations that are a multiple of it. The first stage’s cuts and the terminal pool are always exempt from this pass: the first stage’s cuts are never a backward-pass successor, so their activity is never updated, and the backward pass adds no cut to the terminal pool. Selection runs sequentially across stages; within a stage, trial points are evaluated in parallel blocks. dynamic (DCS) never runs this pass — it has no check_frequency gating and never deactivates pool cuts.
2. Budget pass (max_active_per_stage) — runs every iteration, regardless of check_frequency, as a hard-cap safety net on top of whatever the selection pass (or DCS) leaves active. Stage 2: Budget Enforcement gives the eviction order and the cap’s reach into a terminal pool that holds a loaded boundary policy’s cuts.

DCS is lazy, not a deactivation pass

Dynamic Cut Selection (methodology §8) never deactivates a pool cut. Each stage solve instead starts from a small resident subset — seeded from cuts active at this stage within the last seed_window iterations plus every cut generated this iteration — and grows it by repeatedly scoring the omitted candidates and adding the most-violated ones, up to the bounded inner-loop cap (50 rounds, not user-configurable). The loop stops as soon as no candidate is violated, at which point the resident-subset optimum already equals the full-pool optimum — no extra “final” solve is needed to confirm it. If the cap is hit first, every candidate violated at the last solution is added and one closing solve is performed with no further scoring, so the closing solve is not checked for exactness (methodology §8.3).

DCS is rejected at setup under an enumerated forward pass (methodology §8): the enumerated engine seeds each cut pool at its node-native cut stride, while DCS relies on the eviction keys of sampled selection, which the budget pass reads when it evicts cuts.

A cut loaded into the pool via policy.mode = "warm_start" or "resume" (Inputs & Outputs tab) carries a reserved sentinel iteration_generated value rather than a real iteration number. Under DCS’s candidate_recency window this sentinel saturates to age zero, so a warm-started cut is always inside any finite candidate_recency window — only cuts generated during the current run’s own iterations can age out of it.

Cross-References

• LP Formulation — Benders cut constraints in the LP
• State Augmentation — Column-bound state pinning whose reduced costs give cut coefficients; cut-state projection onto the state components each stage selects
• LP Warm-Start — Stored-basis warm-start of stage solves; a DCS solve does not apply it (§8.4)
• PAR(p) Inflow Model — AR lag state variables that appear in cut coefficients
• SDDP Algorithm — Forward/backward pass structure that drives cut generation
• Scenario Generation — Fixed opening tree that defines backward pass branchings; sampling scheme abstraction
• Penalty System — Recourse slacks that guarantee relatively complete recourse (cut validity condition)
• Stopping Rules — Convergence criteria that depend on cut quality
• Discount Rate Formulation — Discount factor scaling in cut aggregation
• Risk Measures — Risk-averse cut generation (CVaR modifies aggregation weights)
• Block Formulation Variants — Block structure that affects how per-block duals contribute to cut coefficients
• Determinism & Provenance — Bit-identical results across thread and MPI-rank counts, including DCS resident-set seeding
• Running Novomodelo: Policy Management — the software guide for persisting and reloading this cut pool across runs.