PAR(p) Folding
Purpose
Seção intitulada “Purpose”Each stage LP depends on the PAR(p) inflow model (PAR(p) Inflow Model) through the realized inflow of each hydro: the model gives it from the incoming inflow lags and the noise of the opening, and the water balance and the rows that read the inflow use it. This chapter describes how Novomodelo keeps the inflow model outside the stage LP, folding its terms into the right-hand side of the rows, and how it computes the cut coefficients on the inflow lags, which the LP does not give in this form. The stage LP keeps its optimal value at every solve, and the attainable cuts stay the same (§5).
1. Two Formulations of the Same LP
Seção intitulada “1. Two Formulations of the Same LP”The expanded formulation writes the inflow model inside the stage LP. For each hydro it has:
- one column per incoming inflow lag , , pinned at the trial value by its column bounds;
- one free, zero-cost column for the realized inflow, defined by the row ;
- the column in the water-balance rows and in the generic-constraint rows that read the inflow;
- in each cut row, the lag-1 coefficient on and the lag- coefficient on ; the lag coefficients of a new cut are the reduced costs of the pinned lag columns.
The compact formulation, which Novomodelo builds and solves at every stage of training and simulation, rests on one observation: before the solve, the incoming lags are the trial state and the noise is the opening’s, so the realized inflow is a known number,
where is zero for a lag the model of hydro does not use. The compact LP has no lag column, no realized-inflow column and no realized-inflow row. enters every row that reads it as a constant on the right-hand side (§2). Each cut row keeps its terms on the columns of the LP (storage, in-transit buckets and commitment-ring slots), and its lag terms, evaluated at and , join its right-hand side (§3).
The figure draws the stage LP of each formulation in blocks, not to scale: columns across, rows down, the right-hand side on the right. The blocks drawn in blue are the ones the inflow model fills. In the expanded LP they are the lag and realized-inflow columns, the definition rows and the lag terms of the cuts. In the compact LP the same quantities reach the right-hand side as numbers, computed outside the LP.
The compact LP is the expanded LP with each column fixed at and eliminated into the bounds of the rows it touches, and with the definition rows and the pinned lag columns dropped: the elimination a presolve would perform, done when the LP is built. The lag and realized-inflow columns have objective coefficient , so the optimal value of every solve is the same in both formulations. With hydros, the compact LP has fewer columns and fewer rows per stage, and no cut row has an entry on the inflow lags.
The cuts themselves are the same in both formulations: a cut keeps one coefficient per state component it projects onto, the inflow lags included when the stage’s projection keeps them (Cut Management §1, State Augmentation §7). Only the cut’s row in the LP is shorter.
2. The Realized Inflow Outside the LP
Seção intitulada “2. The Realized Inflow Outside the LP”The realized inflow splits into a part fixed by the trial point and a part fixed by the opening:
- is computed once per trial point, and once per solve. The terms are summed in a fixed order (the base, the lag terms in ascending , then the noise term), so has the same bits however its parts are reused.
- are the original-unit coefficients of PAR(p) Inflow Model §2.3; for a hydro with the annual component they also carry the annual term (PAR(p) Inflow Model §7.4).
Let be the coefficient of the realized inflow of hydro in row of the expanded LP, and where the row does not read it:
- on the water-balance row of on a parallel stage, and on the row of block on a chronological stage (LP Formulation §4); for a PreFilling hydro, on the rows of its short-circuit target (LP Formulation — PreFilling Pass-Through);
- the coefficient of each generic-constraint term that reads the inflow of (LP Formulation — Hydro Inflow).
In the compact LP each finite bound of row becomes
is the only route by which a row of the compact LP reads the realized inflow, and no matrix coefficient depends on or on the incoming state: the FPHA planes, the evaporation slopes and the filling targets are fixed for the stage (Hydro Production Function Models, LP Formulation — Evaporation Row). The incoming state enters the compact LP only through right-hand sides and column bounds.
The same is the realized inflow everywhere else in the solve:
- the truncation amount that bounds the inflow non-negativity slack (Inflow Non-Negativity §2);
- the outgoing inflow-lag state, which the lag accumulation forms from and the incoming lags (Multi-Resolution Studies §2), while the outgoing storage, buckets and ring slots are read from the LP solution (State Augmentation §3);
- the realized inflow the simulation reports.
3. The Cut Right-Hand Side
Seção intitulada “3. The Cut Right-Hand Side”Cut of the stage- LP bounds , whose incoming lags are the outgoing lags of stage : at a stage that completes a lag period that begins at it, the realized inflow of stage (lag ) and the incoming lags of stage shifted by one (lag ) (LP Formulation §11); the end of this section gives the other forms. In the compact LP these are numbers, so the cut row is
where stands for the terms on the outgoing bucket and ring-slot columns (State Augmentation §3). The right-hand side splits like the realized inflow:
- The state part depends on the trial point, the child node and the cut, not on the opening. It is computed once per trial point and child, and every backward opening at that point shares it; the backward pass can take it from the forward pass at the same trial point instead of computing it again. The incoming-state pins are also set once per trial point, not once per opening.
- The noise part depends on the opening and the cut, not on the trial point. It is computed once per node and opening, for every trial point at the node.
- At each opening, one sum remains: .
The figure shows the reuse at one trial point of the backward pass.
Each part is summed in a fixed order, and a stored part is the value the same arithmetic gives in place, so the reuse changes no bit: the result is the same with or without it, at any thread and MPI rank count (Determinism & Provenance). The dynamic method checks an omitted cut against the same right-hand side (Cut Management §8).
Lag periods split over stages. At a stage that leaves its lag period open, the outgoing lags are the incoming ones (Multi-Resolution Studies §2.1), so every lag term of a cut is , in the state part, and the noise part is zero. At a stage that completes a period begun earlier, lag 1 is the period mean , with
so its term puts in the state part and in the noise part. depends on the trial point through the partial sum, and on neither the trial point nor the opening, so each part keeps its reuse.
4. The Inflow-Lag Coefficients by the Chain Rule
Seção intitulada “4. The Inflow-Lag Coefficients by the Chain Rule”In the expanded LP, the lag coefficients of a new cut are the reduced costs of the pinned lag columns (Cut Management §2). The compact LP has no such column, so Novomodelo computes the coefficients after the solve, from its duals, by the chain rule. The optimal value depends on the incoming lag through two routes:
- through , with derivative , and from through the shifted row bounds (§2) and the lag-1 terms of the cut rows (§3);
- through the term at lag of every cut row, which evaluates the successor cut at .
With the dual of row and the dual of cut row , the value of the realized inflow of hydro is
and the lag coefficients of the new cut are
equals the dual of the realized-inflow definition row of in the expanded LP. and the duals are taken in unscaled units (LP Layout and Scaling §2), so the coefficients need no further unscaling. The figure follows the rule for one hydro.
- Storage, bucket and ring-slot coefficients are the reduced costs of the pinned incoming columns, as in the expanded LP (Cut Management §2).
- The intercept is computed after the lag coefficients, over every component the cut projects onto (Cut Management §2).
- Projection. A component a cut projects out carries no coefficient (State Augmentation §7): a successor cut without lag adds no term at lag , and the new cut keeps the lag coefficients its own stage’s projection selects.
- Completeness. The incoming state enters the compact LP only through right-hand sides and column bounds (§2), so the two routes are the only ones and the rule differentiates the LP that is solved. The truncation amount is a column bound computed from , and the rule does not differentiate it; neither does the expanded LP, where it is a column bound too, so the limitation of Inflow Non-Negativity §7 holds in both formulations.
- Aggregation. The rule is linear in the duals, and the weights of Cut Management §3, under the expectation or a risk measure, depend on the opening objectives only. Novomodelo aggregates the duals of each child’s openings under those weights and applies the rule once per child, with that child’s coefficients ; in exact arithmetic the result is the aggregate of the per-opening cuts.
Lag periods split over stages. The rule differentiates the lag terms of the cut rows as §3 evaluates them (Multi-Resolution Studies §2.1). At a stage that leaves its lag period open, no cut row reads , and each cut row evaluates the successor cut at lag on itself:
At a stage that completes a period begun earlier, the cut rows read through , so the cut term of is scaled by , the partial sum is held fixed, and the lag coefficients take the form given for a stage that completes a period that begins at it:
The cut is exact only where is the same on every path (Multi-Resolution Studies §2.1).
5. Exactness and Limits
Seção intitulada “5. Exactness and Limits”Identical in exact arithmetic: the feasible set projected on the kept columns and ; the optimal value ; the optimal dual face on the kept rows, in unscaled units; hence the set of attainable cuts; the storage, bucket and ring-slot coefficients at a given vertex; and the intercept given the coefficients. The lag coefficient the expanded LP gives as a reduced cost differs from the chain-rule value by times the reduced cost of the column , which the solver leaves within its dual tolerance; the chain rule carries no such residual.
Not identical:
- At a degenerate optimum the simplex can stop at another optimal vertex. The compact LP is smaller, and the rows that read the inflow lose their entry and can take a different row scale (LP Layout and Scaling §2), so the pivot path differs. Another vertex gives another cut of the same optimal face, and every later iterate follows from it.
- Every computed value differs at rounding level.
A compact-LP run and an expanded-LP run therefore agree on the optimal value of each solve and on the attainable cuts, not bit for bit.
The flexibility trade-off. The two formulations divide the work differently:
- Expanded. The LP itself gives the cut of any inflow model whose realized inflow is linear in the state: the model is written as rows, and the reduced costs of the pinned columns give the lag coefficients with no step specific to the model.
- Compact. Each inflow model needs its own chain rule, the derivative of the realized inflow and of the cut’s lag terms with respect to each incoming lag, and every row that reads the realized inflow reads it through . A row that read it any other way would define a different LP, whose cuts the rule would not match.
Novomodelo solves the compact formulation: a smaller LP at every stage, cut rows without lag entries, and a cut right-hand side that splits into a part per trial point and a part per opening. The price is a method specialized to the PAR(p) family (PAR(p) and PAR(p)-A, linear in the lags through ), whose rows must all read the inflow through one route.
Cross-References
Seção intitulada “Cross-References”- PAR(p) Inflow Model — the inflow model whose realization the compact LP takes as a number
- LP Formulation — the rows that read the realized inflow and the cut rows of the stage LP
- LP Layout and Scaling — the column and row layout of the compact LP and the row scales of the rows that read the inflow
- State Augmentation — the state vector, its pinning by column bounds and the outgoing state
- Cut Management — the cut definition, the reduced-cost extraction of the other coefficients and the aggregation
- Inflow Non-Negativity Solution Methods — the inflow slack bounded by the truncation amount of
- Multi-Resolution Studies — the lag accumulation that forms the outgoing lags from
- Determinism & Provenance — bit-identical results across thread and MPI rank counts, with or without the reuse of §3