LP Layout and Scaling
Purpose
Seção intitulada “Purpose”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
1. Column and Row Layout
Seção intitulada “1. Column and Row Layout”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 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).
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 hydros and = total in-transit bucket count (the sum, over receiving plants, of each plant’s maturity-lag depth — State Augmentation §6):
Column layout:
| Region | Count | Description |
|---|---|---|
storage | Outgoing storage volumes (state) — first | |
transit_buckets_out | Outgoing in-transit bucket volumes (state, plant-major lag-minor) — after storage | |
commit_out | one per commitment-ring slot (State Augmentation §1) | Outgoing commitment-ring slots (state, slot-major plant-minor) — after the outgoing buckets |
storage_in | Incoming storage volumes (pinned, State Augmentation §2) — after the outgoing ring slots | |
transit_buckets_in | Incoming in-transit bucket volumes (pinned, State Augmentation §6) — after storage_in | |
commit_in | one per commitment-ring slot (State Augmentation §1) | Incoming commitment-ring slots (pinned, State Augmentation §5) — after the incoming buckets |
theta | Future cost variable — last of the state prefix |
Equipment and slack columns follow immediately after , 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 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 (, an inflow-lag depth , no anticipated thermal and no travel-time arc): the storage region holds 3 columns and the incoming-storage region holds 3, so is the 7th column. The state count (storage + inflow lags) is , of which only the 3 storage coordinates have LP columns.
2. LP Scaling
Seção intitulada “2. LP Scaling”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.
2.1 Cost Scaling
Seção intitulada “2.1 Cost Scaling”All objective coefficients (except the future cost variable ) are divided by a fixed positive constant , chosen once per study. 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 agree in exact arithmetic:
The variable keeps an unscaled coefficient, the one-step discount factor : each cut row is over the outgoing-state columns , its right-hand side (LP Formulation §11) and every coefficient being the original-unit value divided by , so is already in scaled cost space. The LP objective is , and the total scaled objective equals . 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 at the reporting boundary to recover original units.
2.2 Column Scaling (Geometric Mean)
Seção intitulada “2.2 Column Scaling (Geometric Mean)”After cost scaling, each column 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:
where the max and min are taken over nonzero entries in column . Columns with no nonzero entries, and the commitment-ring slot columns, receive . The transformation replaces:
- Matrix entries:
- Objective coefficients:
- Column bounds: ,
2.3 Row Scaling (Geometric Mean)
Seção intitulada “2.3 Row Scaling (Geometric Mean)”After column scaling, each row is assigned a scale factor using the same geometric-mean formula applied to the already column-scaled matrix:
The transformation replaces:
- Matrix entries:
- Row bounds: ,
Column bounds and objective coefficients are not modified by row scaling.
The combined scaling produces the standard form where and are diagonal scaling matrices.
Cross-References
Seção intitulada “Cross-References”- LP Formulation — the stage LP whose columns and rows this chapter orders
- State Augmentation — the state vector, its pinning by column bounds and the cut row over the outgoing state
- Cut Management — cut coefficients, aggregation and selection
- Discount Rate Formulation — the one-step discount factor that is the coefficient of
- LP Warm-Start — basis reuse across the solves of the stage LP
- Notation Conventions — symbols and the canonical entity order