Cut Management
Purpose
Seção intitulada “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 methods are available to control cut pool growth.
For the entity view of this chapter, see Water value and future cost.
1. Cut Definition
Seção intitulada “1. Cut Definition”A Benders cut at stage is a linear inequality that provides a lower bound on the cost-to-go function under the validity conditions of §4:
where:
- is the future cost variable in the stage LP
- is the cut intercept
- is the vector of the state components the cut projects onto, and the vector of their cut coefficients, one per component
- is the storage coefficient for hydro (marginal value of water)
- is the AR lag coefficient for hydro , lag (marginal value of inflow history)
- , are the storage and AR-lag state variables (see State Augmentation §1)
The cut carries a coefficient for each enabled state dimension: the storage and the inflow lags 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.
2. Reduced-Cost Extraction
Seção intitulada “2. Reduced-Cost Extraction”After solving the stage subproblem for trial state and scenario , 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 column | Reduced cost | Cut coefficient | Units |
|---|---|---|---|
| Incoming storage (hydro ) | $/hm³ |
where is the per-column prescaler factor that unscales the reduced cost; a further factor 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 , 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 , in $/(m³/s), is the derivative of 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:
where is the optimal objective value of the stage subproblem and the product 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 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 is convex and piecewise linear in the incoming state, and the vector read at an optimal basis is a subgradient of it at : for every incoming state . Where is differentiable at , ; where the stage LP has several optimal dual solutions, can have a kink at , and is the subgradient the terminating basis gives. For a column pinned at , the reduced cost is that subgradient’s component — equal, by KKT parity, to the multiplier the equivalent equality row 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 (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 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.
Cut dimension: the enabled state subset
Seção intitulada “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
Seção intitulada “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 (Policy Graphs) aggregates over the pairs formed by every child of and every opening of that child, each pair weighted by the product of the transition probability from to and the probability of opening within . Under the expectation, the aggregated cut is the expectation of the per-pair cuts under that joint law:
where and are the intercept and the coefficient vector of the cut read from child ‘s subproblem under opening 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 are replaced by the risk-adjusted probabilities of Risk Measures, computed on that same joint law: the risk measure of node ‘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 , so the pairs are the openings of stage and their weights are the uniform : the aggregation runs over one stage’s openings.
The aggregated cut is added to node ‘s cut pool, which on the stage chain is the cut pool of stage .
4. Cut Validity
Seção intitulada “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:
Here 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:
- 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.
- 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.
- 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)
- 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, is not guaranteed to be a lower bound and the gap is not a certificate.
When Bounds and Certificates Hold
Seção intitulada “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 | 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 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. Convergence | 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; Level 1 selection as Novomodelo runs it; a per-stage cap on active cuts; a finite |
| 3. Gap certificate | 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
Seção intitulada “Tier 1: Valid Lower Bound”At every iteration , 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 of the raw realization , 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 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
Seção intitulada “Tier 2: Convergence”Under an expectation measure at every stage, 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 . 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, , 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 iterations, leaves the first stage’s pool unselected, and, with a window , scores the cuts only at the trial states of the last 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 (§8.2), the dynamic method never scores a cut generated or more iterations earlier, so its loop can stop with a violated old cut left out.
Tier 3: Gap Certificate
Seção intitulada “Tier 3: Gap Certificate”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 . See Optimality gap for the gap and Upper Bound Evaluation for the exact bound.
5. Cut Growth and Selection Motivation
Seção intitulada “5. Cut Growth and Selection Motivation”The number of cuts grows as . 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 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 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 , 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 and are never evicted, and loaded cuts neither count nor are evicted, so a pool can hold more than 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.
6. Cut Activity
Seção intitulada “6. Cut Activity”Level 1 selection works from a value-evaluation view of activity. At a stored trial point of a pool, each cut’s value is , and the per-state best value is
taken over the pool’s live cuts : 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 owns ; when several attain it exactly, the cut at the lowest slot owns it. Values are compared exactly, with no tolerance band:
A cut at the per-state maximum is the one the future-cost variable rests on at , 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.
7. Level 1 Selection
Seção intitulada “7. Level 1 Selection”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 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 iterations, a selection run of iteration keeps only the trial states of the cuts generated after iteration 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 , 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 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.
- The first stage’s pool is never selected.
- Selection runs every iterations, not each time a cut is added.
- 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: 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.
8. The Dynamic Method
Seção intitulada “8. The Dynamic Method”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.
8.1 Per-solve procedure
Seção intitulada “8.1 Per-solve procedure”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.
-
Seed the resident set with the active cuts whose last binding was at most 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.
-
Solve the stage LP with the current resident set. Let be the optimal values of the outgoing-state columns and the optimal future-cost value.
-
Score the omitted (non-resident) candidate cuts. Cut coefficients are stored in raw (unscaled) space while the LP solves in scaled space, so both and each state column must first be unscaled: each scaled value is multiplied by its column scaling factor, the of §2, to give . For candidate cut with right-hand side , which carries its intercept and its inflow-lag terms (PAR(p) Folding §3), and coefficients on the outgoing-state columns, the future-cost floor it would impose at is
The candidate is violated iff
(strict), with a relative tolerance. This follows from the cut-row convention .
-
Add the top most-violated candidates (sorted by 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.
-
Stop when no candidate is violated. The solve returns only then, so its objective and the optimum over the candidate set satisfy , with the objective coefficient of . Backward duals and forward primals are extracted from this final LP.
8.2 Candidate-recency window
Seção intitulada “8.2 Candidate-recency window”By default every active cut is a candidate (), 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 restricts candidates to the cuts generated within the last 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.
8.3 Bounded rounds
Seção intitulada “8.3 Bounded rounds”Rounds that add at most 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.
8.4 Pass uniformity and warm-start synergy
Seção intitulada “8.4 Pass uniformity and warm-start synergy”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 and 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.
8.5 Zero seed window
Seção intitulada “8.5 Zero seed window”A seed window 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 trades a slightly larger initial LP for fewer inner iterations.
8.6 Determinism
Seção intitulada “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 last bound and the iteration it was generated), not per-worker traces.
- The optimal state 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- selection stable.
9. Convergence Guarantee
Seção intitulada “9. Convergence Guarantee”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 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 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 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.
10. Selection Parameters
Seção intitulada “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 | The cap (§5) and dynamic (§8.1) |
max_active_per_stage | No method or level1 | |
selection.check_frequency | level1 | |
selection.lookback_iterations | level1 | |
selection.seed_window | dynamic | |
selection.candidate_recency | dynamic | |
selection.max_added_per_round | dynamic | |
selection.violation_tolerance | dynamic | |
| — | selection.start_iteration | dynamic |
Implementation in Novomodelo
Seção intitulada “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.
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.
stages[].state_variables — Cut Projection
Seção intitulada “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 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.
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 Case Format and Output Format pages.
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 loadspolicy/cuts/NNN.binfrom the checkpoint atpolicy.pathand repopulates the cut pool before training or simulation begins, together with the stored bases (policy/basis/NNN.bin) and, where the run selects or the checkpoint holds them, the stored trial states (policy/states/NNN.bin). 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.pathis 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
Seção intitulada “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 slot, intercept, coefficient vector, active flag, whether its trial state was stored, and its binding counters, with the pool’s cost-scale factor. 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). |
policy/basis/NNN.bin | One per node (NNN is the node position), root table StageBasis: one stored LP basis per forward-pass scenario, each with its column and row statuses and the pool slot of every cut row it holds. Re-read on the next warm-start, resume, or simulation-only run, behind the stored-basis gate. |
policy/states/NNN.bin | One per pool that stores trial states (NNN is the pool id), keyed by the slot of the cut written at each state. Written when the run selects with level1 or sets exports.states; read on resume and warm start. |
For the complete field-by-field record layout (AffinePiece, StageCuts, StageBasis, StageStates) and the
checkpoint-wide policy/manifest.bin summary, see the
Output Format reference page. 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.
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
Seção intitulada “Reduced-cost unscaling divides by the column scale”Methodology §2 derives each storage, bucket and ring-slot 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).
The inflow-lag coefficients have no column. The chain rule
(PAR(p) Folding §4)
reads the dual of each row that reads the realized inflow unscaled by a
multiplication, dual_raw = row_scale[row] * dual (empty row_scale ⇒ the
raw dual), so the lag coefficients it forms need no further unscaling.
Storage-only cut projection
Seção intitulada “Storage-only cut projection”With the inflow lags projected out of the cuts on a stage under a PAR model
with lag terms, 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.
Checkpoints store cuts in the writing study’s scaled units
Seção intitulada “Checkpoints store cuts in the writing study’s scaled units”A checkpoint stores every cut’s intercept and coefficients as the pool holds
them, in the writing study’s scaled cost space, and each pool’s file records the
cost-scale factor of that space. A load uses a pool unchanged when its factor
equals the loading study’s bit for bit, so a same-factor round trip, a resume
included, reproduces the pool exactly. At another factor every value becomes
(value * source) / loading, the multiplication first. 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 of a study. See Policy Management — Cost-Scale
Canonicalization
for the load-time rule.
Append-only pool, deterministic slots
Seção intitulada “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
Seção intitulada “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 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
Seção intitulada “Selection pass and budget pass”The row-management pipeline runs after each iteration’s backward pass and cut synchronization, in two passes over the interior pools — those strictly between the root and the terminal pool:
- Selection pass (
level1) — runs at iterations that are a multiple ofcheck_frequency. It drops the trial states older than thelookback_iterationswindow, records each stored state’s owner, and sets every scored cut’s flag from that record, the current iteration’s cuts included. The root pool is never selected, and the backward pass adds no cut to the terminal pool. Within a pool, trial points are evaluated in parallel blocks.dynamicnever runs this pass and never deactivates a pool cut. - Budget pass (
max_active_per_stage) — runs every iteration after the selection pass. It counts and evicts only the cuts this run generated: a loaded cut neither counts nor is evicted, and a cut of the current iteration counts but is never evicted, so a pool’s active count can exceed the cap by its loaded cuts. Underlevel1an evicted cut that still owns a state is reactivated by the next selection pass, and the cap is applied again in that iteration. The cap is refused at load withdynamic, whose candidates are the active cuts, so an evicted cut would never be a candidate again, and with an enumerated forward pass, whose backward records no binding, so eviction would follow generation order alone. Stage 2: Budget Enforcement gives the eviction order.
The dynamic method is lazy, not a deactivation pass
Seção intitulada “The dynamic method is lazy, not a deactivation pass”The dynamic method (methodology §8) never deactivates a pool cut. Each stage
solve instead starts from a small resident subset — the active cuts that bound
within the last seed_window iterations plus every cut generated this
iteration — and grows it by scoring the omitted candidates and adding the
most-violated ones. After 50 rounds (not user-configurable) the per-round limit
is lifted and every violated candidate is added in each round until none is
left, so a solve always returns the optimum over the candidates up to the
violation tolerance and needs no closing solve. Each solve that reaches the 50th
round with a candidate still violated is counted in the lazy_round_cap_hits
column of training/convergence.parquet.
The simulation seeds every active cut, so its lazy solve adds none.
The dynamic method is refused at setup under an enumerated forward pass (methodology §8): the enumerated backward records no binding activity, so the seed window’s activity clock never advances past each cut’s generating iteration.
A cut loaded into the pool by policy.mode = "warm_start" or "resume"
(Inputs & Outputs tab) keeps the iteration that generated it in its source run.
Under a finite candidate_recency window a loaded cut is always a candidate,
like a boundary cut. Under resume a reloaded cut counts as loaded only when
the run that wrote the checkpoint loaded it; the cuts that run generated are
windowed as they were in it.
Cross-References
Seção intitulada “Cross-References”- 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.