Skip to content

LP Layout and Scaling

This chapter states the column and row layout of the stage LP and its numerical conditioning: the order of its column regions and row families, the cost scaling, the geometric-mean column and row prescaling, and the unscaling of row duals and of the reduced costs that give the cut coefficients.

Reading order: Cut Management → this chapter → LP Warm-Start

The figure lists the column regions of the stage LP in their order on the left and its row families in their order on the right. The columns open with the outgoing storage, the outgoing in-transit buckets and the outgoing commitment-ring slots; the pinned incoming storage, in-transit buckets and ring slots, and θ\theta follow, and the equipment and slack columns close the layout. The inflow lags and the realized inflow have no column: the realized inflow is computed before the solve and enters the rows that read it through their right-hand sides (LP Formulation §5, PAR(p) Folding). The rows open with the water balance and close with the Benders cuts, appended after the stage’s own rows. The edge marks where the storage, bucket and ring-slot cut coefficients come from: the reduced cost of a pinned incoming column. The inflow-lag coefficients come from the duals by the chain rule (PAR(p) Folding §4).

Columns, in orderRow families, in orderOutgoing storageOutgoing bucketsOutgoing ring slotsPinned incoming storage,buckets and ring slotsθEquipment and slacksWater balanceIn-transit bucket definitionLoad balanceFPHA planesEvaporationOperational floors and capFilling and dead-volume floorsCommitment fish · deposit · carryGeneric constraintsBenders cuts reduced cost →cut coefficient

The stage LP uses a fixed column and row layout that places state variables first, followed by auxiliary and equipment columns. Storage, in-transit buckets and commitment-ring slots are pinned by column bounds on the incoming-state columns (State Augmentation §2, §5, §6), and their cut coefficients are read as the reduced costs of those columns — so the fixed column order, not a fixed row order, is what enables contiguous coefficient extraction. With N=∣H∣N = |\mathcal{H}| hydros and BB = total in-transit bucket count (the sum, over receiving plants, of each plant’s maturity-lag depth — State Augmentation §6):

Column layout:

RegionCountDescription
storageNNOutgoing storage volumes (state) — first
transit_buckets_outBBOutgoing in-transit bucket volumes (state, plant-major lag-minor) — after storage
commit_outone per commitment-ring slot (State Augmentation §1)Outgoing commitment-ring slots (state, slot-major plant-minor) — after the outgoing buckets
storage_inNNIncoming storage volumes (pinned, State Augmentation §2) — after the outgoing ring slots
transit_buckets_inBBIncoming in-transit bucket volumes (pinned, State Augmentation §6) — after storage_in
commit_inone per commitment-ring slot (State Augmentation §1)Incoming commitment-ring slots (pinned, State Augmentation §5) — after the incoming buckets
theta11Future cost variable — last of the state prefix

Equipment and slack columns follow immediately after θ\theta, in this order: on a chronological stage, the storage at the end of every block but the last; turbined flow, spillage and diversion; thermal generation; the anticipated-thermal decisions; line flows in each direction; deficit and excess; the inflow non-negativity slacks, under every inflow method except none; FPHA generation; evaporation and its slacks; the withdrawal slacks; the operational-violation slacks; non-controllable generation; pumped flow; import and export contracts; the generic-constraint slacks; and the filling-floor and soft dead-volume-floor slacks. The turbined-flow column family, and the FPHA generation column family, are indexed by (hydro, bus) cell rather than by plant — one column per cell (LP Formulation §3, §6) — while every other hydro equipment column (spillage, diversion) stays indexed by plant. Like the outgoing storage and ring slots, the outgoing bucket block sits at the columns of its own state indices: it holds the volume still in transit on each cascade arc, defined by in-LP bucket definition rows (State Augmentation §6) rather than pinned, and the incoming bucket block is the matching pinned incoming copy read for the delayed-arrival water-balance entry and the cut coefficient (State Augmentation §6). One equipment block serves anticipated thermals: one decision column per anticipated thermal, carrying the commitment decided at this stage for its delivery stage (State Augmentation §5).

The inflow-lag state has no column: the incoming lags and the noise of the opening give the realized inflow z^h\hat{z}_h before the solve, and it enters the rows that read it as a right-hand-side constant (LP Formulation §5).

Row layout:

Because state is pinned by column bounds (State Augmentation §2, §5, §6) rather than by equality rows, the LP has no state-fixing rows, and the inflow model has no definition rows (PAR(p) Folding §1). The row families come in this order: water balance, in-transit bucket definition (State Augmentation §6), load balance, FPHA planes, evaporation, the operational rows (minimum outflow, maximum outflow, minimum turbined flow, minimum generation, then the plant minimum turbined-flow and generation rows and the plant maximum turbined-flow and generation rows of a hydro with several cells, LP Formulation — Plant Minimum and Maximum), the filling floor and the soft dead-volume floor, the commitment fish, deposit and carry rows (State Augmentation §5), and the generic constraints; Stage LP at a Glance counts each family. The Benders cut rows are appended after them (LP Formulation §11).

Each storage, in-transit bucket and commitment-ring slot coordinate of the incoming state is pinned on its own LP column — the incoming storage column, the incoming bucket column, the incoming ring-slot column — and its cut coefficient is the reduced cost of that column (State Augmentation §2, Cut Management). The map from a state coordinate to its pinned column is fixed, and each of these incoming-state column regions is contiguous, so the storage, in-transit bucket and commitment-ring slot coefficients are gathered by reading a few contiguous slices of the reduced-cost vector. The incoming inflow lags are not LP columns: their trial values enter the realized inflow and the cut right-hand sides, and their cut coefficients come from the row and cut duals by the chain rule (PAR(p) Folding §4).

Worked example (N=3N = 3, an inflow-lag depth Pmax⁡=2P^{\max} = 2, no anticipated thermal and no travel-time arc): the storage region holds 3 columns and the incoming-storage region holds 3, so θ\theta is the 7th column. The state count (storage + inflow lags) is N(1+Pmax⁡)=9N(1 + P^{\max}) = 9, of which only the 3 storage coordinates have LP columns.

The stage LP is numerically conditioned via a three-step scaling procedure applied once at template construction time. Scaling narrows the spread of coefficient magnitudes in the constraint matrix, which usually improves the numerical behaviour of the simplex method, without changing the optimization argmin; it carries no guarantee on the matrix’s condition number.

All objective coefficients (except the future cost variable θ\theta) are divided by a fixed positive constant KK, chosen once per study. KK scales the cost domain uniformly and leaves the constraint matrix and feasible region untouched, so the LP argmin is invariant to it and any two choices of KK agree in exact arithmetic:

c~j=cjKfor all j≠θ\tilde{c}_j = \frac{c_j}{K} \quad \text{for all } j \neq \theta

The θ\theta variable keeps an unscaled coefficient, the one-step discount factor dt→t+1d_{t \to t+1}: each cut row is θ≥Rscaled+∑jβjscaledxj\theta \geq R^{scaled} + \sum_j \beta_j^{scaled} x_j over the outgoing-state columns jj, its right-hand side (LP Formulation §11) and every coefficient being the original-unit value divided by KK, so θ\theta is already in scaled cost space. The LP objective is ∑jc~jxj+dt→t+1 θ\sum_j \tilde{c}_j x_j + d_{t \to t+1} \, \theta, and the total scaled objective equals (Cstage+dt→t+1 Cfuture)/K(C_{stage} + d_{t \to t+1} \, C_{future}) / K. Each stage’s factor carries every later stage’s cost to stage 1 exactly once (Discount Rate Formulation). All cost-domain outputs (objective values, duals, cost breakdowns) are multiplied by KK at the reporting boundary to recover original units.

After cost scaling, each column jj is assigned a scale factor by one pass of geometric-mean scaling (Tomlin, 1975; Elble & Sahinidis, 2012), which makes the largest and smallest nonzero magnitudes of the column reciprocals of each other:

djcol=1max⁡i∣Aij∣⋅min⁡i∣Aij∣d_j^{col} = \frac{1}{\sqrt{\max_i |A_{ij}| \cdot \min_i |A_{ij}|}}

where the max and min are taken over nonzero entries in column jj. Columns with no nonzero entries, and the commitment-ring slot columns, receive djcol=1d_j^{col} = 1. The transformation replaces:

  • Matrix entries: A~ij=Aij⋅djcol\tilde{A}_{ij} = A_{ij} \cdot d_j^{col}
  • Objective coefficients: c~j=cj⋅djcol\tilde{c}_j = c_j \cdot d_j^{col}
  • Column bounds: l~j=lj/djcol\tilde{l}_j = l_j / d_j^{col}, u~j=uj/djcol\tilde{u}_j = u_j / d_j^{col}

After column scaling, each row ii is assigned a scale factor using the same geometric-mean formula applied to the already column-scaled matrix:

dirow=1max⁡j∣A~ij∣⋅min⁡j∣A~ij∣d_i^{row} = \frac{1}{\sqrt{\max_j |\tilde{A}_{ij}| \cdot \min_j |\tilde{A}_{ij}|}}

The transformation replaces:

  • Matrix entries: Aˇij=A~ij⋅dirow\check{A}_{ij} = \tilde{A}_{ij} \cdot d_i^{row}
  • Row bounds: lˇirow=lirow⋅dirow\check{l}_i^{row} = l_i^{row} \cdot d_i^{row}, uˇirow=uirow⋅dirow\check{u}_i^{row} = u_i^{row} \cdot d_i^{row}

Column bounds and objective coefficients are not modified by row scaling.

The combined scaling produces the standard Dr⋅A⋅DcD_r \cdot A \cdot D_c form where DrD_r and DcD_c are diagonal scaling matrices.