LP Warm-Start
Purpose
Seção intitulada “Purpose”This chapter describes how Novomodelo reuses an LP basis to accelerate solves. Two related mechanisms are covered. The per-(scenario, node) basis store holds at most one basis per trial point per policy-graph node, and the forward and backward passes hand bases to one another through it, so that a basis found by one solve can seed the next solve of the same trial point at the same node. Cut-aware basis reconstruction by slot identity maps a stored basis onto a cut pool whose active set has churned through cut selection, which is what lets a reused basis — whether captured earlier in the run or loaded from a saved policy by a warm-start or resume run — align to the current LP.
1. The Repeated-LP Problem
Seção intitulada “1. The Repeated-LP Problem”The SDDP Algorithm backward pass solves, at each stage, one LP per opening per trial point per iteration. Across a training run these LPs are not independent: the LP at stage in iteration differs from the LP at stage in iteration only in two ways — the active cut set has changed (grown by the cuts added during iteration , and possibly changed further by cut selection, which deactivates and reactivates cuts; §3), and the trial point may have shifted. The constraint matrix columns, the objective, the bounds other than those that pin the incoming state, and the majority of constraint rows are identical between consecutive iterations.
A cold start discards this structural similarity. The LP solver begins from scratch each time, choosing an initial basis by its own heuristic (typically Phase-I primal feasibility). On a well-structured LP this wastes simplex pivots whose only purpose is to rediscover a basis that was already known.
A warm start avoids this waste by supplying the solver with the basis from a previous solve at the same stage. The solver checks whether the supplied basis is primal feasible, dual feasible, or both for the new LP; if it is, it can proceed immediately to optimality iterations rather than rebuilding feasibility from scratch. The benefit is proportional to how similar consecutive LPs are — and in the SDDP backward pass, consecutive solves at the same stage are very similar.
2. Per-(Scenario, Node) Basis Store
Seção intitulada “2. Per-(Scenario, Node) Basis Store”Novomodelo keeps a basis store keyed by (scenario, node): the scenario identifies a
trial point, and the node is a node of the policy graph;
on a stage chain (one node per stage) a node is a stage. The store holds at most
one captured basis — the partition of variables and constraints into basic and
non-basic — for each trial point at each node.
Whether a solve starts from the store is set per phase: the forward pass, the backward pass and simulation each either warm-start or start cold (see the implementation notes). A solve of a warm-starting phase starts from its trial point’s slot when the slot holds a basis; a solve of a cold phase starts from no basis at all, neither a stored one nor the one the previous solve left in place. Captures do not depend on that setting.
The forward and backward passes of an iteration hand bases to one another through the store. A forward solve at a node stores its optimal basis in its trial point’s slot. The backward pass runs after the forward pass of the same iteration; when it solves that node’s openings from the same trial point’s incoming state, the slot holds the forward capture, which seeds the first-solved opening when the backward pass warm-starts, and the backward pass stores that opening’s optimal basis in its place. The next iteration’s forward solve at the node starts from that backward capture when the forward pass warm-starts; a cold forward solve leaves it unread and replaces it with its own capture. Either way, the slot the backward pass reads at that node holds the forward capture of its own iteration. One backward scheduling option reads the forward capture without storing its own; under an enumerated forward pass the backward pass uses no stored basis; and while the dynamic method of cut selection is active no solve uses the store (see the implementation notes).
Each seeds arrow applies when that phase warm-starts; each stores arrow applies whichever phases warm-start.
Within each chain of openings that a warm-starting backward pass solves in sequence, the store is read at most once, by the first-solved opening; the remaining openings continue from the basis and factorization the previous opening left in place, since consecutive openings differ only in their realization.
The basis a solve starts from therefore depends on the order in which its chain’s openings are solved. That order is fixed in advance, and it changes the starting basis, never the validity of a cut, since every optimal basis of an opening’s LP yields a valid cut; Determinism & Provenance §3 sets out how the fixed order keeps the run reproducible.
A warm-start or resume run seeds the store from the saved bases, one per trial point at each node, so that, when the forward pass warm-starts, its first iteration’s forward solves at those nodes start from them through the reconstruction of §4. A resume run seeds each trial point from its own saved basis and leaves a trial point without one cold; a warm-start run seeds a trial point without its own saved basis from the node’s lowest-scenario saved basis. A saved basis that does not fit its stage LP is left out, and a node left with none starts its first iteration cold. When the forward pass starts cold, its captures replace the seeded bases of the nodes it visits before the backward pass reads the store. On a stage chain the saved bases then seed no training solve; on a branching graph they seed only the warm-starting backward solves at the successor nodes that a trial point’s first-iteration forward path did not visit.
3. Cut-Set Changes
Seção intitulada “3. Cut-Set Changes”A stored basis stops matching the LP at stage when that LP changes shape. The relevant change is cut-set growth: each iteration adds one new cut per trial point at every stage except the last. The cut pool and the persistent lower-bound LP are append-only, while each iteration’s stage template carries the active cuts only (deactivation is covered at the end of this section; see Cut Management for the append-only monotonicity guarantee). A new cut adds one constraint row to the LP.
Appending a cut row to a previously solved LP, with the new row’s slack basic, keeps that LP’s optimal basis dual feasible: the new row’s dual is zero because its slack is basic, so no reduced cost changes. If the new cut holds at the previous primal solution, the basis stays optimal. If the cut is violated there, the basis is primal infeasible, and the dual simplex, which keeps dual feasibility, restores primal feasibility starting from that basis rather than from cold.
When cut selection leaves the active set untouched, this growth is purely monotone: rows are only ever added, never removed or reordered. The structural relationship between consecutive LP instances is then predictable — the new LP is a proper extension of the previous one, sharing every row of it — so the row-append facts above apply to each new cut row. Cut selection can break that pure-append case, which the next paragraph turns to.
Cut deactivation follows a different route on the backward-pass solve path. A deactivated cut is excluded from the rebaked frozen template rather than left in place with a relaxed bound: at the LP level its row is dropped, not merely slackened, so the active cut set can shrink and reorder from one iteration to the next, not only grow. The cut is not lost — its stable slot is retained in the append-only pool, and reactivation re-bakes the cut at that same slot. Because the active set can change this way, a stored basis cannot be replayed by row position; the slot-identity reconstruction of §4 reconciles it to the current active set, which is what keeps warm-starting valid across deactivation and reactivation. See Cut Management for the full deactivation mechanism, including the separate persistent-lower-bound-LP route, which is append-only — its cut rows are never removed, so deactivation changes nothing there and the lower bound stays monotone.
4. Cut-Aware Basis Reconstruction by Slot Identity
Seção intitulada “4. Cut-Aware Basis Reconstruction by Slot Identity”Between solves, cut selection (see Cut Management) deactivates and reactivates cuts and the backward pass appends new ones, so the set of active cut rows in the stage LP churns from one iteration to the next. A stored basis records a status for each row it contained; if those statuses were replayed by row position, a churned cut set of the same length would misalign — and the solver would warm-start from a corrupted basis or fall back to a cold start.
Novomodelo avoids this by reconciling on slot identity, not position. The cut pool assigns every cut a stable slot index (see Cut Management §5), and a stored basis carries, for each cut row it held, the pool slot that generated it. To reconstruct a basis for the current LP:
- The non-cut (template) row statuses and all column statuses are copied directly.
- Each current cut row is matched to the stored basis by its slot. If the slot was present in the stored basis, its saved status is reused; if the slot is new — a cut that was not in the LP when the basis was captured — the row is set BASIC (slack), the default under which the new row changes no reduced cost (§3); if the cut is violated at the starting point, the dual simplex repairs the resulting primal infeasibility.
- Setting new cut rows BASIC preserves the solver’s basis-count invariant by construction (each new cut adds exactly one row and one basic entry). When selection instead drops a cut whose row was non-basic (binding), the reconstructed basis carries one basic entry too many for each such row, because a basic row leaves together with its basic slack whereas a non-basic row takes no basic entry with it; a final pass demotes the trailing excess of basic cut rows to non-basic until the invariant holds. Under the reconstruction’s premises — a stored basis captured against the same LP shape — the obligation is one-sided: reconstruction can only ever leave an excess. A basic-count deficit therefore proves the stored basis was captured against a differently-shaped LP; it is rejected with a named error reporting the basic-count arithmetic, identically on either solver backend — never repaired, since demotion cannot create the missing basics and promotion would fabricate a basis the stored one never described.
This single mechanism handles all three churn cases — drops, reorders, and additions — and serves both within-run reactivation and the cross-run checkpoint reconstruction used on warm-start/resume (§2).
5. Trade-offs
Seção intitulada “5. Trade-offs”Warm-start benefit degrades with LP change magnitude. The stored basis is most valuable when consecutive LP instances are nearly identical. Early in a training run, when the cut set is growing rapidly and each new cut can shift the active face of the optimal basis substantially, warm-starting provides smaller savings than in the middle and late phases of training when the cut set has largely stabilized and new cuts make only incremental changes to the LP geometry.
Relationship to cut-aware reconstruction. The basis store and the
reconstruction of §4 answer different questions. The store answers “which stored
basis should seed this (scenario, node) subproblem’s first solve?” — supplying
a basis captured for that same slot. Reconstruction answers the narrower
question that arises because the active cut set baked into the current template
may have churned since that basis was captured: “which stored row statuses still
apply, and what status should cut rows new to this LP take?” The store provides
the starting point; reconstruction reconciles it to the current cut set by slot
identity, defaulting cut rows with no stored slot to BASIC.
Implementation in Novomodelo
Seção intitulada “Implementation in Novomodelo”The methodology above defines the basis store, its hand-off and its reconstruction; the tab below covers how Novomodelo’s training and simulation passes use the store at runtime.
Non-normative software behavior for LP warm-start — what Novomodelo does at runtime, beyond the methodology of LP Warm-Start. This tab references the methodology body for the hand-off and the reconstruction rather than restating them.
Which solves start from a stored basis
Seção intitulada “Which solves start from a stored basis”Every phase captures its solves’ bases into the basis store, but whether a
solve starts from the basis it is offered depends on the solver backend. The
HiGHS backend’s phase profiles set use_warm_start to true for the forward and
backward passes and to false for simulation, so by default training solves
warm-start and simulation solves start cold. Under
use_warm_start: false HiGHS ignores the offered basis: it is not installed,
not validated and not counted in basis_offered. A phase that solves cold
builds no basis to offer, so no basis reconstruction runs for it; its captures
still fill the store. A cold HiGHS solve does not
continue from the basis the previous solve left in the solver either, so every
solve of a cold phase starts from scratch. The retry levels 5–11, which
restore HiGHS’s default settings before applying their own, keep the phase’s
use_warm_start. Before HiGHS reports a solve optimal it refactorizes the
basis, so a warm-started solve’s primal solution meets every row within the
primal feasibility tolerance. The CLP backend has no such setting and starts a
solve from the offered basis in every phase. Where the sections below say a
solve starts from a stored basis, that applies under CLP, or under HiGHS when
that phase’s profile has use_warm_start: true (see
Turning warm-start off).
A cold solve can stop at a different optimal vertex from a warm one, with the same optimal value (Determinism & Provenance §3), so a run’s trial points, its cuts, its final lower bound and its simulated duals can differ between the two settings.
Backward work units
Seção intitulada “Backward work units”This section describes the backward pass when the dynamic method of cut selection is inactive; the next section covers the active case. A backward work unit solves a chain of openings in sequence for one trial point at one node. Before the chain, the worker resets the solver’s retained basis and factorization, reloads the node’s frozen LP template, and appends the cuts that the node’s cut pool has gained since the template was built. When the backward phase warm-starts, the chain’s first-solved opening starts from the trial point’s slot in the basis store and the remaining openings continue from the retained factorization; that opening’s basis is the only one the chain stores back into the slot, whatever the phase setting. On a branching graph, each successor node’s openings form a chain of their own, because each successor loads its own LP.
The default by_scenario scheduler solves a trial point’s openings at a
successor node as one chain. The by_node scheduler
(training.parallelism.backward_scheduler; see
By-Node Scheduling) splits them into
opening blocks and solves each block as a chain of its own. Each block’s
first-solved opening reads the basis that the forward pass captured in the slot
(the forward capture). Under by_node the backward pass stores nothing, so the
slot keeps the forward capture, which is the basis the next iteration’s forward
solve is offered.
However, under an enumerated forward pass
(training.selection), the forward
pass solves each node once per iteration and stores that solve’s basis in one
slot for the node, which the next iteration’s forward solve at the node is
offered.
The backward pass reads no stored basis and stores none: each chain’s
first-solved opening starts without a stored basis, and the rest continue from
the retained factorization. Under the default HiGHS profiles an enumerated run
therefore starts only its forward solves from the store.
When a stored basis is reused
Seção intitulada “When a stored basis is reused”A stored basis seeds a solve only when the solve’s phase warm-starts and the basis was captured at the node being solved: each basis carries the node it was captured at, and a basis tagged with another node, or an empty slot, leaves the solve to start cold. A slot is empty until its first capture, so in a fresh run the first iteration’s forward solves start cold whatever the phase setting. An infeasible forward solve clears its slot.
While the dynamic method of cut selection (Cut Management §8) is active, no solve reads or writes the store. The forward pass leaves its slot untouched, and every solve’s initial LP starts without a stored basis; in a warm-starting phase the later openings of a backward chain, and each re-solve after the dynamic method adds violated cuts, continue from the retained basis, while in a cold phase they start cold as well. The store therefore keeps the bases captured in the iterations before the dynamic method started, and those are the bases the end-of-training checkpoint carries.
Warm-start, resume and simulation-only runs
Seção intitulada “Warm-start, resume and simulation-only runs”The end-of-training checkpoint carries one basis per trial point at each node:
the basis held in that trial point’s slot when training ends, recorded with its
scenario and the pool slot of each cut row. A warm-start or resume run seeds
each trial point’s slot from the checkpoint before its first iteration. A
resume run seeds a trial point from its own basis and leaves a trial point
without one to start cold; a warm-start run seeds a trial point without its own
basis from the node’s lowest-scenario basis, since the run that wrote the
checkpoint may have run fewer forward passes. A slot left empty starts its first
solve cold and then reuses its own captures. Outside the dynamic method, the
first iteration’s seeded solves of a warm-starting phase start through the
reconstruction of
§4; a
fresh run has nothing to seed. Under the default HiGHS forward profile the
forward solves warm-start, so on a stage chain, where every trial point visits
every node, the checkpoint bases seed the first iteration’s forward solves, and
each forward capture then replaces the seeded basis of the node it visits
before the backward pass reads that slot. When training.solver.forward sets
"use_warm_start": false, the forward solves start cold and on a stage chain
the checkpoint bases seed no training solve. On a branching graph, a backward
pass that reads the
store also starts from them at the successor nodes that a trial point’s
first-iteration forward path did not visit.
When the simulation phase warm-starts, and outside the dynamic method,
simulation starts each visited node’s solve from that node’s basis, taken from
the preceding training run or, in a simulation-only run, from the node’s
lowest-scenario checkpoint basis for every scenario (a node with none is solved
without its own stored basis); under the dynamic method simulation solves start
without a stored basis. Under the default HiGHS simulation profile every
simulation solve starts cold, so a simulation-only run uses its checkpoint bases
only when simulation.solver sets "use_warm_start": true.
A checkpoint basis is used only when its column count equals the node’s current stage LP’s, its row count equals the LP’s template rows plus its recorded cut rows, its basic count equals its row count, and every cut-row slot it records holds a loaded cut. A basis that fails is left out, and the load reports how many were left out and why the first failed (see Stored-basis gate). An admitted basis keeps the statuses of its recorded cut rows, matched to the loaded pool by slot; a current cut row it does not record starts BASIC. Either way only the basis the warm start begins from changes, never the optimal value of the stage LP.
What persists across solves
Seção intitulada “What persists across solves”Warm-starting does not rest on a resident solver that holds each node’s LP for the lifetime of the run. Each backward work unit resets the solver’s retained state and reloads the node’s frozen LP template before solving, so what carries information from one solve to the next is not a live solver but two persistent data structures:
- The basis store, keyed by
(scenario, node), which a chain’s first-solved opening reads and a capture refreshes. - The per-iteration frozen templates, one per cut pool (one per stage on a stage chain), each baking in the currently active cut set. A template is built once per iteration and loaded into the solver afresh for every trial point it serves; within a chain only the realization’s bounds then change.
Because the template is reloaded rather than mutated in place, LP structural state does not accrue silently inside a long-lived solver. The frozen templates grow over a run, because each iteration’s template bakes in more cuts than the last, and each stored basis grows with them, carrying one status per row. For a study with many nodes and a large state-variable count, the combined footprint of the templates and the basis store can be significant.
When the backward phase warm-starts, as it does by default, a backward-pass solve after the first iteration costs mainly the dual simplex work that restores optimality from the reused basis, once that basis is reconciled to the current cut set (§4), rather than Phase-I feasibility work from a cold start.
Turning warm-start off
Seção intitulada “Turning warm-start off”Each phase’s solver profile — training.solver.backward,
training.solver.forward and simulation.solver — accepts use_warm_start,
which overrides the phase default (true for forward and backward, false for
simulation). Setting it to false forces every solve in that phase cold, and
setting it to true lets simulation solves start from the store;
outside the dynamic method, captures fill the basis store either way. The
forward and backward settings are diagnostic, not production options: comparing
a cold pass with a warm one isolates the warm-start contribution to
training-run performance. Per-phase profile overrides are HiGHS-only; the CLP
backend rejects a set field at setup; see
training.solver.
Cross-References
Seção intitulada “Cross-References”- Cut Management — The append-only cut lifecycle with stable slot indices that drives cut-set changes and underpins slot-identity reconstruction; cut deactivation mechanism and selection strategies that determine how frequently the cut pool changes.
- SDDP Algorithm — The iteration loop in which the forward and backward passes share the basis store; forward and backward pass structure, how each stage’s openings are visited, and the synchronization barriers that separate stages.
- Policy Graphs — The nodes that key the basis store, and the stages they map to.
- Determinism & Provenance — The deterministic pinning of the chain order described in Determinism & Provenance §3, which is what keeps warm-starting compatible with bit-identical reproducibility across runs.