LP Warm-Start

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 seeds 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

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 $t$ in iteration $k+1$ differs from the LP at stage $t$ in iteration $k$ only in two ways — the active cut set has changed (grown by the cuts added during iteration $k$, 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

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.

The forward and backward passes of an iteration hand bases to one another through the store. A forward solve at a node starts from its trial point’s slot when the slot holds a basis, and stores its own optimal basis there. 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, it seeds the first-solved opening from the slot, which then holds the forward capture, and stores that opening’s optimal basis in its place. The next iteration’s forward solve at the node starts from that backward capture. 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 dynamic cut selection is active no solve uses the store (see the implementation notes).

Within each chain of openings solved 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 each saved basis that fits its stage LP, so that its first iteration also warm-starts at those nodes, through the reconstruction of §4; a node whose saved basis does not fit starts its first iteration cold.

3. Cut-Set Changes

A stored basis stops matching the LP at stage $t$ 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

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

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

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.

Implementation notes

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.

Backward work units

This section describes the backward pass when dynamic 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. The chain’s first-solved opening starts from the trial point’s slot in the basis store, and its basis is the only one the chain stores back into that slot; the remaining openings continue from the retained factorization. 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 next iteration’s forward solve starts from the forward capture again.

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

When a stored basis is reused

A stored basis seeds a solve only when it 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. An infeasible forward solve clears its slot.

While dynamic cut selection (Cut Management) 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; the later openings of a backward chain, and each re-solve after dynamic cut selection adds violated cuts, continue from the retained basis. The store therefore keeps the bases captured in the iterations before dynamic cut selection started, and those are the bases the end-of-training checkpoint carries.

Warm-start, resume and simulation-only runs

The end-of-training checkpoint carries one basis per node: the basis held in one trial point’s slot when training ends. A warm-start or resume run copies each node’s checkpoint basis that fits its stage LP into every trial point’s slot on each rank before its first iteration; a node whose basis was left out starts its first solve cold and then reuses its own captures. Outside dynamic cut selection, the first iteration’s forward solves then warm-start through the reconstruction of §4; a fresh run has nothing to copy. Outside dynamic cut selection, 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 checkpoint when that basis fits its stage LP (a node whose checkpoint basis does not fit is solved without its own stored basis); under dynamic cut selection simulation solves start without a stored basis.

A checkpoint basis that does not fit its node’s current stage LP is left out (see Stored-basis gate). The load keeps a checkpoint basis’s cut-row statuses only when the node’s saved cut pool qualifies. The pool qualifies when the pool’s active cuts are exactly its first populated slots, in slot order (a condition that proves no cut has been deactivated since the capture), and when it holds at least as many active cuts as the basis has cut rows. Otherwise the load drops those statuses, and every current cut row starts BASIC while the template rows and the columns keep their stored statuses. Either way only the basis the warm start begins from changes, never the optimal value of the stage LP.

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.

After the first iteration, a backward-pass solve 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

Each phase’s solver profile — training.solver.backward, training.solver.forward and simulation.solver — accepts use_warm_start. Setting it to false forces every solve in that phase cold; outside dynamic cut selection, captures continue to fill the basis store. The setting is diagnostic, not a production option: comparing a cold run with a warm run 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

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