Skip to content

Cut Management

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 methods are available to control cut pool growth.

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

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

θ≥β0+β⊤x\theta \geq \beta_0 + \beta^{\top} x

where:

  • θ\theta is the future cost variable in the stage t−1t-1 LP
  • β0\beta_0 is the cut intercept
  • xx is the vector of the state components the cut projects onto, and β\beta the vector of their cut coefficients, one per component
  • βhv\beta^v_h is the storage coefficient for hydro hh (marginal value of water)
  • βh,ℓlag\beta^{lag}_{h,\ell} is the AR lag coefficient for hydro hh, lag ℓ\ell (marginal value of inflow history)
  • vhv_h, ah,ℓ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 vhv_h and the inflow lags ah,ℓ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, computed from the solve (§2), and a coefficient may be zero. In the stage LP, the cut row carries the storage, bucket and ring-slot terms as entries on the outgoing columns and evaluates the inflow-lag terms on its right-hand side, because the inflow lags are not LP columns (PAR(p) Folding §3); the row omits the entries 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.

After solving the stage tt subproblem for trial state x^t−1\hat{x}_{t-1} and scenario ωt\omega_t, the coefficients on the storage, the in-transit buckets and the commitment-ring slots 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). The inflow lags are not LP columns, and their coefficients come from the duals of the solve by the chain rule (below).

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 columnReduced costCut coefficientUnits
Incoming storage (hydro hh)cˉhin\bar{c}^{in}_hβt,hv=cˉhin/dhcol\beta^v_{t,h} = \bar{c}^{in}_h / d^{col}_h$/hm³

where dcold^{col} is the per-column prescaler factor that unscales the reduced cost; a further factor KK 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).

Inflow-lag coefficients. The incoming inflow lags reach the stage LP only through right-hand sides: through the realized inflow z^h\hat{z}_h, which the water balance and the other rows that read the inflow take as a constant (PAR(p) Folding §2), and through the lag terms of the cut rows. The coefficient βt,h,ℓlag\beta^{lag}_{t,h,\ell}, in $/(m³/s), is the derivative of QtQ_t along both routes, computed from the unscaled row duals by the chain rule (PAR(p) Folding §4). In exact arithmetic it equals the reduced cost of the pinned lag column of the formulation that writes the PAR(p) model as rows of the LP (PAR(p) Folding §5).

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

β0,t=Qt(x^t−1,ωt)−βt⊤x^t−1\beta_{0,t} = Q_t(\hat{x}_{t-1}, \omega_t) - \beta_t^{\top} \hat{x}_{t-1}

where Qt(x^t−1,ωt)Q_t(\hat{x}_{t-1}, \omega_t) is the optimal objective value of the stage tt subproblem and the product βt⊤x^t−1\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 x^t−1\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 LP duality, the optimal value QtQ_t is convex and piecewise linear in the incoming state, and the vector β\beta read at an optimal basis is a subgradient of it at x^\hat{x}: Qt(x)≥Qt(x^)+β⊤(x−x^)Q_t(x) \geq Q_t(\hat{x}) + \beta^\top (x - \hat{x}) for every incoming state xx. Where QtQ_t is differentiable at x^\hat{x}, βj=∂Qt/∂x^j\beta_j = \partial Q_t / \partial \hat{x}_j; where the stage LP has several optimal dual solutions, QtQ_t can have a kink at x^\hat{x}, and β\beta is the subgradient the terminating basis gives. For a column pinned at x‾j=xˉj=x^j\underline{x}_j = \bar{x}_j = \hat{x}_j, the reduced cost is that subgradient’s component jj — equal, by KKT parity, to the multiplier the equivalent equality row xjin=x^jx^{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 vhinv^{in}_h (see LP Formulation). For an inflow lag, the chain rule sums the effects along the two routes by which the lag reaches the LP, the rows that read the realized inflow and the lag terms of the cut rows.

Storage coefficient sign: more incoming storage lowers QtQ_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.

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.

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 nn (Policy Graphs) aggregates over the pairs (n′,ω)(n', \omega) formed by every child n′n' of nn and every opening ω∈Ωn′\omega \in \Omega_{n'} of that child, each pair weighted by the product P(n→n′) pn′(ω)P(n \to n')\, p_{n'}(\omega) of the transition probability from nn to n′n' and the probability of opening ω\omega within n′n'. Under the expectation, the aggregated cut is the expectation of the per-pair cuts under that joint law:

βˉ0=∑(n′,ω)P(n→n′) pn′(ω) β0(n′,ω)\bar{\beta}_0 = \sum_{(n', \omega)} P(n \to n')\, p_{n'}(\omega)\, \beta_0(n', \omega) βˉ=∑(n′,ω)P(n→n′) pn′(ω) β(n′,ω)\bar{\beta} = \sum_{(n', \omega)} P(n \to n')\, p_{n'}(\omega)\, \beta(n', \omega)

where β0(n′,ω)\beta_0(n', \omega) and β(n′,ω)\beta(n', \omega) are the intercept and the coefficient vector of the cut read from child n′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→n′) pn′(ω)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 nn‘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 11, so the pairs are the openings ω∈Ωt\omega \in \Omega_t of stage tt and their weights are the uniform p(ω)p(\omega): the aggregation runs over one stage’s openings.

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

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

β0,i+βi⊤x≤Vt+1(x)∀x∈Xt\beta_{0,i} + \beta_i^\top x \leq V_{t+1}(x) \quad \forall x \in \mathcal{X}_t

Here βi\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, the recourse slack system (Category 1 penalties) provides it for every case that meets the complete-recourse precondition.
  3. Correct sensitivity extraction — the reduced costs and row duals that give the 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 model with lag terms, z‾k\underline{z}^k is not guaranteed to be a lower bound and the gap is not a certificate.

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.

TierWhat holdsRequiresBroken by
1. Valid lower boundz‾k\underline{z}^k is at most the optimal value of the model as trainedA 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 functionA truncation inflow non-negativity method on a PAR model with lag terms; a cut that omits a state component the cost-to-go depends on; a cost-to-go that takes negative values
2. Convergencez‾k\underline{z}^k converges to that optimal value with probability 1 under an expectation measure at every stageTier 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 stateA forward pass that draws from another distribution; Level 1 selection as Novomodelo runs it; a per-stage cap on active cuts; a finite k1k_1
3. Gap certificatezˉk−z‾k\bar{z}^k - \underline{z}^k bounds the optimality gap of the policyTier 1; an exact upper bound on the same tree under the same measure: an enumerated forward pass and a measure uniform across stagesA sampled, out-of-sample, historical or external upper bound; a measure that varies across stages

At every iteration kk, z‾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 and, for the inflow lags, the right-hand sides of the rows that read the realized inflow and of the cut rows. The truncation methods of Inflow Non-Negativity Solution Methods §7 break this in the inflow-lag components under a PAR model with lag terms (an order above zero or an annual component), because the correction they apply, the truncation amount max⁡(0,−ah)\max(0, -a_h) of the raw realization aha_h, is a non-affine function of the realization and so of the trial point’s lags; keeping the lag components in the cut does not restore it. Each cut lies below the stage problem with the correction frozen at its own trial point, but away from that point it can lie above the cost-to-go, and the lower bound can exceed the upper bound. 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 under its complete-recourse precondition.
  • 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. In a study whose lag periods span several stages, the cost-to-go inside an open period also depends on the period’s partial sum, which is not a state component, so the cuts are guaranteed to lie below it only where that partial sum is the same on every path (Multi-Resolution Studies §2.1).
  • 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).

Under an expectation measure at every stage, z‾k\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 z‾k\underline{z}^k. The convergence of risk-averse SDDP without cut selection is proved under the hypotheses of Guigues & Römisch (2012), Philpott, de Matos & Finardi (2013) and Guigues (2016); this page states no convergence result for the risk-averse case.

  • 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 keeps the approximation the theorem of §9 assumes: no selection, or the dynamic method of §8 with every active cut a candidate, k1=∞k_1 = \infty, whose solves return the optimum over the active cuts up to the violation tolerance of §8.1.

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

  • Level 1 selection (§7) as Novomodelo runs it departs from the rule the theorem covers (§9): it runs every nseln_{\text{sel}} iterations, leaves the first stage’s pool unselected, and, with a window ww, scores the cuts only at the trial states of the last ww iterations. No convergence result is claimed for it.
  • A per-stage cap on the number of active cuts (§5) deactivates the cuts that were binding least recently once the cap is exceeded, whatever their value at the stored trial states; only the cuts of the current iteration and the loaded cuts are exempt.
  • With a finite k1k_1 (§8.2), the dynamic method never scores a cut generated k1k_1 or more iterations earlier, so its loop can stop with a violated old cut left out.

zˉk−z‾k\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 z‾k\underline{z}^k. See Optimality gap for the gap and Upper Bound Evaluation for the exact bound.

The number of cuts grows as O(iterations×Nforward_passes)\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 (Level 1 selection and the active-cut cap): 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 selection methods are available. Level 1 selection (§7) runs an ownership pass every nseln_{\text{sel}} iterations: it keeps the cuts that own a stored trial state and deactivates the others. The dynamic method (§8) keeps the pool entirely append-only — never deactivating any cut — and instead controls which cuts are resident in each individual stage LP solve.

Active-cut cap: a cap BB on the number of active cuts that the current run has generated in the pool of each node strictly between the first stage and the last. It applies in every iteration, after that iteration’s cuts are added and after the Level 1 pass when one runs, with or without a selection method. When the count exceeds BB, the excess is evicted from the cuts of earlier iterations, in ascending order of the iteration in which a cut was last binding (a cut that has never bound counts from the iteration that generated it), then of the number of solves in which it was binding, then of slot. The cuts of the current iteration count toward BB and are never evicted, and loaded cuts neither count nor are evicted, so a pool can hold more than BB active cuts. Eviction deactivates a cut and keeps it in the pool; a later Level 1 pass reactivates an evicted cut that owns a stored trial state, and the cap is then applied again in the same iteration. The cap is not admitted with the dynamic method, which never reactivates a cut, nor with an enumerated forward pass, which records no binding activity.

Level 1 selection works from a value-evaluation view of activity. At a stored trial point x^\hat{x} of a pool, each cut’s value is β0,i+βi⊤x^\beta_{0,i} + \beta_i^\top \hat{x}, and the per-state best value is

V∗(x^)=max⁡i∈L{β0,i+βi⊤x^}V^*(\hat{x}) = \max_{i \in \mathcal{L}} \left\{ \beta_{0,i} + \beta_i^\top \hat{x} \right\}

taken over the pool’s live cuts L\mathcal{L}: every scored cut, the cuts whose own trial state the pool stored when they were written, active and inactive, and every loaded cut that carries no stored trial state while it is active. The live cut that attains V∗(x^)V^*(\hat{x}) owns x^\hat{x}; when several attain it exactly, the cut at the lowest slot owns it. Values are compared exactly, with no tolerance band:

owner(x^)=min⁡{i∈L:β0,i+βi⊤x^=V∗(x^)}\text{owner}(\hat{x}) = \min \left\{ i \in \mathcal{L} : \beta_{0,i} + \beta_i^\top \hat{x} = V^*(\hat{x}) \right\}

A cut at the per-state maximum is the one the future-cost variable θ\theta rests on at x^\hat{x}, so a cut that owns a state is the value-evaluation counterpart of a binding cut there. Because slot order follows generation order, the lowest slot is the oldest of the tied cuts: keeping only the oldest of the tied cuts is the Limited-Memory Level 1 (LML1) rule of Guigues (2017).

Binding at an LP solution is a different quantity: a cut row binds in a solve when its dual multiplier exceeds a threshold (§10). That record is read only by the active-cut cap (§5) and by the seed window of the dynamic method (§8.1); it plays no part in ownership.

Level 1 selection follows Level 1 of de Matos, Philpott & Finardi (2015), with the tie rule of Limited-Memory Level 1 (Guigues, 2017): each stored trial state has one owner (§6), and a selection run keeps the cuts that own a state. It scores the pool of every node strictly between the first stage and the last; the first stage’s pool and the shared terminal pool are never selected.

The rule. Every nseln_{\text{sel}} iterations, after the backward pass:

  • A scored cut that owns at least one stored state is active; a scored cut that owns none is deactivated and kept in the pool.
  • An inactive scored cut that owns a state is reactivated, so deactivation and reactivation are symmetric within one pass.
  • A cut of the current iteration is judged like any other: there is no exemption.
  • A loaded cut with no stored trial state keeps the activity it was loaded with; while active it competes for ownership and can keep a tied cut at a higher slot inactive.

No cut value is compared against a tolerance, so the active set after a pass is a function of the stored states and the cut coefficients alone. The pass is bit-deterministic regardless of thread count and rank count (see Determinism & Provenance).

Stored states and the window. Every cut the run generates in a selected pool is scored: the pool stores the trial state the cut was computed at. A loaded cut is scored when the policy it comes from records it so, and it then competes at the stored states, its own stored state included when the policy holds one. By default a run keeps the trial states of the whole run, so the memory they take grows with the cut count. With a window of ww iterations, a selection run of iteration kk keeps only the trial states of the cuts generated after iteration k−wk - w and drops the older ones; a state loaded with a cut from another run counts as one from before the run’s first iteration. The window is at least nseln_{\text{sel}}, so every state is scored at least once before it can be dropped. A window drops states, never cuts: a cut whose state was dropped stays scored and still competes at the states that remain.

Envelope property. Right after a selection run in which the active-cut cap evicts nothing, the owner of every stored state is active, so the active cuts of the pool attain V∗(x^)V^*(\hat{x}) at every stored state. A state stored after the run can be owned by an inactive cut until the next run, and the cap, applied after the pass, can deactivate a cut that owns states; the next pass reactivates it.

Departures from the paper.

  1. The first stage’s pool is never selected.
  2. Selection runs every nseln_{\text{sel}} iterations, not each time a cut is added.
  3. The paper names no rule for an exact tie; the lowest slot, the oldest of the tied cuts, is the rule of LML1 (Guigues, 2017).

Cost: O(∣new cuts∣×∣stored states∣+∣cuts∣×∣new states∣)\mathcal{O}(|\text{new cuts}| \times |\text{stored states}| + |\text{cuts}| \times |\text{new states}|) multiply-adds per pool and pass: the ownership record is updated incrementally, evaluating the cuts and states written since the previous pass against the others as a blocked matrix product.

The dynamic method is Novomodelo’s own lazy row generation; it is not the Dynamic Cut Selection of de Matos, Philpott & Finardi (2015). It is mutually exclusive with Level 1 selection, and it is 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. It 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. The dynamic method keeps the whole pool and solves each LP with a small resident subset of it, grown until no candidate cut is violated at the solution, so a solve returns the optimum over its candidates up to the violation tolerance; when every active cut is a candidate (§8.2), that is the optimum with every active cut. It pairs only with a sampled forward pass, as the setup check above enforces.

From the iteration at which the lazy loop starts, each training solve for one (stage, scenario) runs this loop; before it, solves carry every active cut.

  1. Seed the resident set with the active cuts whose last binding was at most k2k_2 iterations ago (the seed window; a cut that has not yet bound counts from the iteration that generated it), plus every cut generated in the current iteration. The seed is derived only from synchronized per-slot pool metadata, the iteration each cut last bound 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∗x^* be the optimal values of the outgoing-state columns 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 xscaledx_{\text{scaled}} is multiplied by its column scaling factor, the dcold^{col} of §2, to give xrawx_{\text{raw}}. For candidate cut ii with right-hand side RiR_i, which carries its intercept and its inflow-lag terms (PAR(p) Folding §3), and coefficients βi\beta_i on the outgoing-state columns, the future-cost floor it would impose at x∗x^* is

    fi=Ri+βi⊤xraw∗f_i = R_i + \beta_i^\top x^*_{\text{raw}}

    The candidate is violated iff

    fi−θraw∗>εviol⋅max⁡(∣θraw∗∣,∣fi∣)f_i - \theta^*_{\text{raw}} > \varepsilon_{\text{viol}} \cdot \max\left(\lvert \theta^*_{\text{raw}} \rvert, \lvert f_i \rvert\right)

    (strict), with εviol∈(0,1)\varepsilon_{\text{viol}} \in (0, 1) a relative tolerance. This follows from the cut-row convention θ−β⊤x≥Ri\theta - \beta^\top x \ge R_i.

  4. Add the top nadicn_{\text{adic}} most-violated candidates (sorted by fi−θraw∗f_i - \theta^*_{\text{raw}} descending, ties broken by ascending slot id). Re-solve, from the retained basis when the phase warm-starts (§8.4), and return to step 2.

  5. Stop when no candidate is violated. The solve returns only then, so its objective zRz_R and the optimum zCz_C over the candidate set satisfy zR≤zC≤zR+d εviol1−εviol ∣θ∗∣z_R \le z_C \le z_R + d\,\frac{\varepsilon_{\text{viol}}}{1 - \varepsilon_{\text{viol}}}\,\lvert \theta^* \rvert, with dd the objective coefficient of θ\theta. Backward duals and forward primals are extracted from this final LP.

By default every active cut is a candidate (k1=∞k_1 = \infty), so the window excludes no cut and the exit of step 5 is the optimum over every active cut, up to the violation tolerance. A finite k1k_1 restricts candidates to the cuts generated within the last k1k_1 iterations and the loaded cuts. This is a deliberate, inexact speedup: the result is then the optimum over those candidates together with the seed, and an older cut is never scored or added, even when violated.

Rounds that add at most nadicn_{\text{adic}} cuts each run up to a fixed round count. Past it the per-round limit is lifted: every violated candidate is added in each round, and the loop still ends only at the stop of §8.1 step 5. The loop terminates because every reported candidate becomes resident, so each round shrinks the finite set of omitted candidates.

The loop runs in the backward pass and the forward pass of training, and in both it runs to the stop of §8.1 step 5 — 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. A simulation solve seeds the resident set with every active cut, so the windows k1k_1 and k2k_2 apply to training only.

In a phase that warm-starts, each inner re-solve adds only a few rows and restarts from the basis the previous solve left, so the bounded loop stays cheap; in a phase that starts cold, every inner re-solve starts cold as well (LP Warm-Start). The stored basis of LP Warm-Start is not applied to a solve of the dynamic method: the first solve of each stage LP starts without a stored basis, and in a warm-starting backward pass the later openings of a trial point re-solve warm from the LP the previous opening left.

A seed window k2=0k_2 = 0 is valid and meaningful: the resident set is seeded with the cuts generated in the current iteration and those that bound in it, and the lazy loop then grows the resident set from there each solve. A larger k2k_2 trades a slightly larger initial LP for fewer inner iterations.

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

  • The seed comes from synchronized pool metadata (the iteration each cut last bound and the iteration it was generated), not per-worker traces.
  • The optimal state x∗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-nadicn_{\text{adic}} selection stable.

See Determinism & Provenance.

Theorem (Bandarra & Guigues, 2021): For an expectation objective at every stage, SDDP with finitely many scenarios and Level 1 or Limited-Memory Level 1 cut selection, applied at every iteration and evaluated over every trial point, reaches an optimal first-stage solution after finitely many iterations with probability 1.

Key insight: Removing cuts that are never at the maximum at any trial point does not change the outer approximation at those points, 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 trial points: convergence is reached after finitely many iterations.

Level 1 selection as Novomodelo runs it resolves an exact tie as LML1 does, keeping the oldest of the tied cuts (§6), and departs from the rule the theorem covers in three ways: it runs every nseln_{\text{sel}} iterations, leaves the first stage’s pool unselected, and, with a window, scores only the trial states inside it (§7). No convergence result is claimed for it, and de Matos, Philpott & Finardi (2015) state none for their Level 1.

The dynamic method and exactness: a solve of the dynamic method returns, at §8.1 step 5, the optimum over its candidates up to the relative violation tolerance. With k1=∞k_1 = \infty the candidates are every active cut, and since the method deactivates no cut, the active cuts are the pool, bar loaded cuts that a source run left inactive. A finite k1k_1 sacrifices this.

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.

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 symbolConfig keyApplies to
—row_activity_toleranceThe cap (§5) and dynamic (§8.1)
BBmax_active_per_stageNo method or level1
nseln_{\text{sel}}selection.check_frequencylevel1
wwselection.lookback_iterationslevel1
k2k_2selection.seed_windowdynamic
k1k_1selection.candidate_recencydynamic
nadicn_{\text{adic}}selection.max_added_per_rounddynamic
εviol\varepsilon_{\text{viol}}selection.violation_tolerancedynamic
—selection.start_iterationdynamic

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.

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 (§5–§9).

training.cut_selection — Row Management Configuration

Seção intitulada “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 selection (level1) every 5 iterations, keeps the trial states of the last 20 iterations, and caps each interior stage at 500 active rows generated by the run:

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

training.cut_selection lists every field, default and method parameter, and the pairings refused at load; Cut Management Pipeline describes the budget pass. Which rows the post-training simulation loads is a separate key, simulation.cut_set.

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

FieldTypeDefaultDescription
storagebooleantrueProject the cuts onto the storage dimensions.
inflow_lagsbooleanfalseProject 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 lags still give the realized inflow, 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.

  • LP Formulation — Benders cut constraints in the LP
  • State Augmentation — Column-bound state pinning whose reduced costs give the storage, bucket and ring-slot cut coefficients; cut-state projection onto the state components each stage selects
  • LP Warm-Start — Stored-basis warm-start of stage solves; a solve of the dynamic method does not apply it (§8.4)
  • PAR(p) Inflow Model — AR lag state variables that appear in cut coefficients
  • PAR(p) Folding — the inflow-lag terms on the cut right-hand side and their coefficients by the chain rule
  • 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 and the precondition under which they give 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 the resident-set seeding of the dynamic method
  • Running Novomodelo: Policy Management — the software guide for persisting and reloading this cut pool across runs.