Skip to content

PAR(p) Folding

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).

The expanded formulation writes the inflow model inside the stage LP. For each hydro hh it has:

  • one column per incoming inflow lag ah,ℓa_{h,\ell}, ℓ=1,…,Pmax⁡\ell = 1, \ldots, P^{\max}, pinned at the trial value a^h,ℓ\hat{a}_{h,\ell} by its column bounds;
  • one free, zero-cost column zhz_h for the realized inflow, defined by the row zh−∑ℓψm(t),ℓ ah,ℓ=bh,m(t)+σm(t) εtz_h - \sum_{\ell} \psi_{m(t),\ell} \, a_{h,\ell} = b_{h,m(t)} + \sigma_{m(t)} \, \varepsilon_t;
  • the column zhz_h in the water-balance rows and in the generic-constraint rows that read the inflow;
  • in each cut row, the lag-1 coefficient on zhz_h and the lag-ℓ\ell coefficient on ah,ℓ−1a_{h,\ell-1}; 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,

z^h=bh,m(t)+∑ℓ=1Pmax⁡ψm(t),ℓ a^h,ℓ+σm(t) εt\hat{z}_h = b_{h,m(t)} + \sum_{\ell=1}^{P^{\max}} \psi_{m(t),\ell} \, \hat{a}_{h,\ell} + \sigma_{m(t)} \, \varepsilon_t

where ψm(t),ℓ\psi_{m(t),\ell} is zero for a lag the model of hydro hh does not use. The compact LP has no lag column, no realized-inflow column and no realized-inflow row. z^h\hat{z}_h 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 z^\hat{z} and a^\hat{a}, 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.

Expanded LPCompact LPPAR(p), outside the LP:ẑ = b + ψ·â + σεOperation columnsLag and z columnsRight-hand sideOperation rowsz in the water balanceBounds PAR(p) rows:z − ψ·ab + σεCuts: θ and storageCuts: z and lagsβ₀Operation columnsRight-hand sideOperation rowsBounds − Γ·ẑCuts: θ and storageβ₀ + lag terms PAR(p) rowstaken out of the LPẑ and â as numbersz fixed at ẑand eliminated

The compact LP is the expanded LP with each column zhz_h fixed at z^h\hat{z}_h 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 00, so the optimal value QtQ_t of every solve is the same in both formulations. With N=∣H∣N = \lvert\mathcal{H}\rvert hydros, the compact LP has N(Pmax⁡+1)N (P^{\max} + 1) fewer columns and NN 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.

The realized inflow splits into a part fixed by the trial point and a part fixed by the opening:

z^h=bh,m(t)+∑ℓ=1Pmax⁡ψm(t),ℓ a^h,ℓ⏟z^hx+σm(t) εt⏟z^hε\hat{z}_h = \underbrace{b_{h,m(t)} + \sum_{\ell=1}^{P^{\max}} \psi_{m(t),\ell} \, \hat{a}_{h,\ell}}_{\hat{z}^{x}_h} + \underbrace{\sigma_{m(t)} \, \varepsilon_t}_{\hat{z}^{\varepsilon}_h}
  • z^hx\hat{z}^{x}_h is computed once per trial point, and z^h\hat{z}_h once per solve. The terms are summed in a fixed order (the base, the lag terms in ascending ℓ\ell, then the noise term), so z^h\hat{z}_h has the same bits however its parts are reused.
  • ψm(t),ℓ\psi_{m(t),\ell} 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 Γr,h\Gamma_{r,h} be the coefficient of the realized inflow of hydro hh in row rr of the expanded LP, and 00 where the row does not read it:

In the compact LP each finite bound brb_r of row rr becomes

br−∑h∈HΓr,h z^hb_r - \sum_{h \in \mathcal{H}} \Gamma_{r,h} \, \hat{z}_h

Γ\Gamma is the only route by which a row of the compact LP reads the realized inflow, and no matrix coefficient depends on z^\hat{z} 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 z^h\hat{z}_h is the realized inflow everywhere else in the solve:

  • the truncation amount ah−=max⁡(0,−z^h)a^-_h = \max(0, -\hat{z}_h) that bounds the inflow non-negativity slack (Inflow Non-Negativity §2);
  • the outgoing inflow-lag state, which the lag accumulation forms from z^\hat{z} 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.

Cut ii of the stage-tt LP bounds Vt+1V_{t+1}, whose incoming lags are the outgoing lags of stage tt: at a stage that completes a lag period that begins at it, the realized inflow of stage tt (lag 11) and the incoming lags of stage tt shifted by one (lag ℓ≥2\ell \ge 2) (LP Formulation §11); the end of this section gives the other forms. In the compact LP these are numbers, so the cut row is

θ−∑h∈Hβi,hv vh−⋯≥Ri\theta - \sum_{h \in \mathcal{H}} \beta^v_{i,h} \, v_h - \cdots \ge R_i Ri=β0,i+∑h∈H(βi,h,1lag z^h+∑ℓ=2Pmax⁡βi,h,ℓlag a^h,ℓ−1)R_i = \beta_{0,i} + \sum_{h \in \mathcal{H}} \Big( \beta^{lag}_{i,h,1} \, \hat{z}_h + \sum_{\ell=2}^{P^{\max}} \beta^{lag}_{i,h,\ell} \, \hat{a}_{h,\ell-1} \Big)

where ⋯\cdots stands for the terms on the outgoing bucket and ring-slot columns (State Augmentation §3). The right-hand side splits like the realized inflow:

Ri=Rix+RiεR_i = R^{x}_i + R^{\varepsilon}_i Rix=β0,i+∑h∈H(∑ℓ=2Pmax⁡βi,h,ℓlag a^h,ℓ−1+βi,h,1lag z^hx),Riε=∑h∈Hβi,h,1lag z^hεR^{x}_i = \beta_{0,i} + \sum_{h \in \mathcal{H}} \Big( \sum_{\ell=2}^{P^{\max}} \beta^{lag}_{i,h,\ell} \, \hat{a}_{h,\ell-1} + \beta^{lag}_{i,h,1} \, \hat{z}^{x}_h \Big), \qquad R^{\varepsilon}_i = \sum_{h \in \mathcal{H}} \beta^{lag}_{i,h,1} \, \hat{z}^{\varepsilon}_h
  • 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: Ri=Rix+RiεR_i = R^{x}_i + R^{\varepsilon}_i.

The figure shows the reuse at one trial point of the backward pass.

Trial point x̂Opening noises εof the nodeState part, once per trial point:β₀ + lag terms + β₁·ẑˣNoise part, once per opening:β₁·σε, for every trial pointBackward openings at x̂Each opening's cut right-hand side:state part + noise part12…Ω sharedper opening

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 βi,h,ℓlag a^h,ℓ\beta^{lag}_{i,h,\ell} \, \hat{a}_{h,\ell}, 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 bh+ch z^hb_h + c_h \, \hat{z}_h, with

bh=Sh,tWh,t+wt,W,ch=wt,WWh,t+wt,Wb_h = \frac{S_{h,t}}{W_{h,t} + w_{t,\mathcal{W}}}, \qquad c_h = \frac{w_{t,\mathcal{W}}}{W_{h,t} + w_{t,\mathcal{W}}}

so its term puts βi,h,1lag(bh+ch z^hx)\beta^{lag}_{i,h,1} (b_h + c_h \, \hat{z}^{x}_h) in the state part and βi,h,1lag ch z^hε\beta^{lag}_{i,h,1} \, c_h \, \hat{z}^{\varepsilon}_h in the noise part. bhb_h depends on the trial point through the partial sum, and chc_h on neither the trial point nor the opening, so each part keeps its reuse.

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 QtQ_t depends on the incoming lag a^h,ℓ\hat{a}_{h,\ell} through two routes:

  1. through z^hx\hat{z}^{x}_h, with derivative ψm(t),ℓ\psi_{m(t),\ell}, and from z^h\hat{z}_h through the shifted row bounds (§2) and the lag-1 terms of the cut rows (§3);
  2. through the term at lag ℓ+1\ell+1 of every cut row, which evaluates the successor cut at a^h,ℓ\hat{a}_{h,\ell}.

With πr\pi_r the dual of row rr and πicut\pi^{cut}_i the dual of cut row ii, the value of the realized inflow of hydro hh is

πhz=−∑rΓr,h πr+∑iπicut βi,h,1lag\pi^z_h = -\sum_{r} \Gamma_{r,h} \, \pi_r + \sum_{i} \pi^{cut}_i \, \beta^{lag}_{i,h,1}

and the lag coefficients of the new cut are

βh,ℓlag=ψm(t),ℓ πhz+∑iπicut βi,h,ℓ+1lag(ℓ<Pmax⁡),βh,Pmax⁡lag=ψm(t),Pmax⁡ πhz\beta^{lag}_{h,\ell} = \psi_{m(t),\ell} \, \pi^z_h + \sum_{i} \pi^{cut}_i \, \beta^{lag}_{i,h,\ell+1} \quad (\ell < P^{\max}), \qquad \beta^{lag}_{h,P^{\max}} = \psi_{m(t),P^{\max}} \, \pi^z_h

πhz\pi^z_h equals the dual of the realized-inflow definition row of hh in the expanded LP. Γ\Gamma 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.

Duals of the solveValue of the realized inflow π(z)Successor cuts at lag ℓ+1:Σ π(cut)·β(ℓ+1)New cutRows that readthe inflow: −Σ Γ·πSuccessor cuts at lag 1:Σ π(cut)·β₁Lag 1: ψ₁·π(z) + Σ π(cut)·β₂Lag 2: ψ₂·π(z) + Σ π(cut)·β₃…Deepest lag P: ψ(P)·π(z) × ψ(ℓ), lag by lag+, at lag ℓ
  • 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, β0=Qt−β⊤x^\beta_0 = Q_t - \beta^{\top} \hat{x} 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 ℓ+1\ell+1 adds no term at lag ℓ\ell, 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 ah−a^-_h is a column bound computed from z^h\hat{z}_h, 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 ψ\psi; 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 z^h\hat{z}_h, and each cut row evaluates the successor cut at lag ℓ\ell on a^h,ℓ\hat{a}_{h,\ell} itself:

πhz=−∑rΓr,h πr,βh,ℓlag=ψm(t),ℓ πhz+∑iπicut βi,h,ℓlag(ℓ≤Pmax⁡)\pi^z_h = -\sum_{r} \Gamma_{r,h} \, \pi_r, \qquad \beta^{lag}_{h,\ell} = \psi_{m(t),\ell} \, \pi^z_h + \sum_{i} \pi^{cut}_i \, \beta^{lag}_{i,h,\ell} \quad (\ell \le P^{\max})

At a stage that completes a period begun earlier, the cut rows read z^h\hat{z}_h through ch z^hc_h \, \hat{z}_h, so the cut term of πhz\pi^z_h is scaled by chc_h, the partial sum Sh,tS_{h,t} is held fixed, and the lag coefficients take the form given for a stage that completes a period that begins at it:

πhz=−∑rΓr,h πr+ch∑iπicut βi,h,1lag\pi^z_h = -\sum_{r} \Gamma_{r,h} \, \pi_r + c_h \sum_{i} \pi^{cut}_i \, \beta^{lag}_{i,h,1}

The cut is exact only where Sh,tS_{h,t} is the same on every path (Multi-Resolution Studies §2.1).

Identical in exact arithmetic: the feasible set projected on the kept columns and θ\theta; the optimal value QtQ_t; 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 ψm(t),ℓ\psi_{m(t),\ell} times the reduced cost of the column zhz_h, 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 zhz_h 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 Γ\Gamma. 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 ψ\psi), whose rows must all read the inflow through one route.