Decayed Active-Set Memory for Exact Finishing of Batched GPU Linear Programs

Solvers for mixed-integer programs (optimization problems where some variables must be whole numbers) spend much of their time solving thousands of closely related linear programs (LPs). Recent work moved these LPs onto GPUs by solving hundreds at once with a first-order method, meaning one that uses only gradient-like matrix-vector products and never factorizes a matrix. This is fast, but first-order methods slow down sharply near the exact answer. Their answers are therefore slightly inexact, and inexact answers can make a solver's bound-tightening step unsound. Our proposal targets that gap. The LPs arrive as a stream, and the set of constraints that end up tight at the optimum (the "active set") changes slowly from one LP to the next. We keep a small, exponentially discounted record of which constraints were recently active, store it on the GPU, and use it to guess each new LP's active set early. A cheap exact finishing step then solves only the square linear system defined by that guess. The result is a certified, basis-exact solution without paying for the slow tail of the first-order method.

In two sentences: stop the GPU first-order solver as soon as a recency-weighted memory of past solutions lets you predict which constraints are tight, then solve that small system exactly. The memory is one number per constraint and the finishing step ships only index vectors across the CPU-GPU bus. Precision is recovered without long iteration tails and without large data transfers.

Core Claim

Batched First-Order Methods for Parallel LP Solving in MIP (BATCHLP) runs a batched Primal-Dual Hybrid Gradient method with reflected Halpern iterations. It stacks LPs that share a constraint matrix $A$ into sparse-dense matrix products $AX$, removes converged LPs from the active work area, and synchronizes restarts across the batch. It reports 12x to 488x speedups over 64-thread CPU dual simplex in full strong branching. It also leaves two things open. First, it cannot match simplex precision, so bound tightening needs conservative dual-feasibility checks and safety margins. Second, it treats each batch as a static, freshly collected set with no memory of earlier solves.

We claim these two gaps are linked. In a mixed-integer solve, the history of past LPs contains information about the optimal active set. A first-order iterate alone cannot reveal that set until the method is deep in its slow tail. If the history is weighted by recency, it can predict the active set well enough to finish exactly several orders of magnitude of tolerance earlier. The weighting is needed because the LP stream drifts: bounds tighten, tree depth grows, and the search backtracks. Uniform history is biased and last-solve-only history is noisy, the same bias-variance tension that discounting resolves in non-stationary bandits (Yoan Russac et al.; Baekjin Kim and Ambuj Tewari).

Why This Combination, and What Each Direction Contributes

The high-precision bottleneck is the core problem. First-order iteration counts grow polynomially in $1/\varepsilon$, roughly tenfold work per extra digit, as Revisiting Area Convexity observes. Composite convex optimization with global and local inexact oracles and A Semismooth Newton Method for Fast, Generic Convex Programming show that curvature-using steps reach $10^{-10}$-level gaps faster despite costlier iterations. These papers motivate a finishing step. For LPs, the natural "second-order" finish is simply solving the basis system once the active set is known, which is quadratic convergence taken to its limit.

Temporal weighting is the mechanism. Moise Blanchard et al. show that retaining past constraint information buys query complexity at tight tolerances (Memory-Constrained Algorithms for Convex Optimization). The research file's Gap 4 notes that plain exponential forgetting can destroy exactly this information. We therefore keep the memory small and decayed, but not memoryless.

Data transfer latency is a design constraint and part of the evaluation. Yao et al. show that overlapping transfer with compute depends on the ratio of bus bandwidth to compute. A naive second-order finish that moves curvature or full solution state across the bus would trade an iteration stall for a transfer stall (the file's Gap 5). Our design avoids this. The finishing step needs only the predicted active index set and a few bound deltas. The CPU already holds $A$ for the mixed-integer solver and can factorize the basis there, or the GPU can do it when the basis is small.

Research Program

We maintain, on the GPU, a score for every constraint and variable bound $i$:

$$s_i \leftarrow \gamma\, s_i + (1-\gamma)\,\mathbb{1}[i \text{ active in the latest solve}],$$

Here $\gamma \in (0,1)$ is the discount factor and "active" means tight at the certified optimum of a completed LP. We also keep a small time-decayed reservoir of recent dual solutions, in the spirit of the time-weighted reservoirs of Anthony Dick and Miles Osborne et al.; these duals serve as warm starts.

A fixed $\gamma$ assumes a fixed rate of drift, which is the known weakness of discounting. To address it, we run a handful of discount values in parallel and select online the one whose scores best predicted recent active sets. This is cheap because each candidate is just another vector.

Search backtracking means the tree can return to earlier regions. To handle that recurrence, we optionally add a component that weights history by tree proximity to the current node rather than by time alone. This is analogous to the periodic-plus-decay kernels of Fredrik Johansson et al.

Each LP in a BATCHLP batch runs as usual. At each restart checkpoint we form a candidate active set by combining two signals: the memory score $s_i$ and the current iterate's slack and dual magnitudes. We then attempt a finish, which consists of three steps. We extract the square basis implied by the candidate set, solve it exactly, and check primal and dual feasibility. If the check passes, the LP is certified and its column is retired early, reusing BATCHLP's dynamic column removal. If the check fails, the LP continues iterating and we try again at the next checkpoint. A small number of dual-simplex pivots from the guessed basis can repair near-misses.

Certification is exact, so a wrong guess costs time but never soundness. This is the property that lets us drop BATCHLP's safety margins in bound tightening. For every finish attempt we log the tolerance at which it succeeded, the bytes moved across the bus, and the finishing time.

Baselines

The naive reference point is BATCHLP run as published. We solve each batch from scratch to a fixed tolerance, using its dual-feasibility checks and safety margins for bound tightening, with its adaptive batch sizing. Every configuration uses the same GPU (an RTX 4500, as in the paper), the same batches, and the same wall-clock accounting, including host-device transfer. The reported strongest numbers are 12x to 488x over 64-thread CPU dual simplex in full strong branching, 2.18 seconds versus over 612 seconds on facility location, and 25.7x over sequential Gurobi on neural-network-verification bound tightening (Batched First-Order Methods for Parallel LP Solving in MIP). Beating BATCHLP means matching its time while certifying basis-exact solutions. Alternatively, it means reaching the same certified precision faster than BATCHLP run to a tolerance tight enough ($10^{-9}$ relative gap) to make its margins negligible.

The strongest exact competitor is multi-thread CPU dual simplex warm-started from the parent or previous basis. Warm-started simplex is the incumbent practice inside branch-and-bound. It is precise by construction and moves no data across the bus. We run it with 64 threads on the same instances and give it the same basis-reuse information our memory has. Beating it means lower time-to-certified-solution on batches where BATCHLP already wins. We also report honestly the tall-and-skinny and small-batch regimes where BATCHLP loses to simplex.

Two ablations isolate the key ingredient. The first is a memoryless finish: the same finishing machinery, but the active set is guessed only from the current iterate ($\gamma = 0$ history, no reservoir). The second is uniform memory, meaning an undiscounted count ($\gamma \to 1$). A hard sliding window of the last $K$ solves serves as a third reference. We tune each variant's single hyperparameter (threshold, $K$, or $\gamma$ grid) on the same held-out instances and give each the same budget.

Why not just…?

Why not just polish from the current iterate, with no history? This is the real threat. If first-order iterates identify the active set early on these LPs, the memory adds nothing beyond warm starting. The memoryless-finish ablation settles the question directly. We compare the distribution of tolerances at which the first finish attempt succeeds under each variant. If memory does not move that distribution by at least an order of magnitude on some benchmark family, we will report the method as a finishing technique for BATCHLP with warm starts, and the temporal-weighting claim will be refuted.

Why not just use warm-started CPU dual simplex? It is exact, needs no GPU, and exploits basis reuse. The file's evidence is that on large shared-$A$ batches the CPU approach is dominated by up to 488x, because simplex parallelizes poorly across many LPs. That speedup, however, was measured against pure simplex, not against first-order speed plus exact finishing. We report both methods per instance family, so readers can see where exactness on the GPU path is worth its overhead.

Why not just run BATCHLP longer, or stop early and keep the safety margins? Running longer pays roughly tenfold per digit (Revisiting Area Convexity). Stopping early is fine for strong-branching scores, which tolerate noise. For bound tightening, margins loosen the bounds, and looser bounds weaken the downstream verification relaxation. We measure bound tightness with and without margins to quantify what the margins cost.

Why not a hard sliding window instead of decay? A window is simpler and fits fixed buffers. However, it forgets constraints that recur after backtracking, and it makes the prediction jump at window edges (Fan Dong et al. report this kind of instability from sharp cuts). It is included as a baseline. If it matches decay, we adopt it.

Proposed Experiments and Decisive Checks

We evaluate on the benchmarks BATCHLP used: MIPLIB 2017 full strong branching, set covering and facility location families, and neural-network-verification bound tightening. Bound tightening is the primary target because it is where soundness matters. Its LP stream drifts naturally as layer bounds tighten, and many LPs share $A$ while differing only in objective.

We report five metrics:

  • time to a certified basis-exact solution;
  • the fraction of LPs certified per batch;
  • the tolerance at first successful finish;
  • active-set prediction precision and recall over time;
  • bytes transferred across the bus per LP.

For bound tightening we additionally report final bound widths and downstream verification outcome. For strong branching we report branch-and-bound nodes and total solve time.

The first decisive check is the memoryless-versus-decayed comparison of finish tolerance described above. The second is a drift stress test: we artificially reorder the LP stream (depth-first versus best-first node selection) and check that the adaptive discount tracks the change while any fixed $\gamma$ does not. The third tests the latency claim. Finishing traffic should stay a small fraction of BATCHLP's own per-batch transfer. If factorizing on the CPU forces full-state transfers that erase the gain, we move factorization onto the GPU and report the crossover basis size.

We found no reported result on Lacuna for exact-finish or active-set-prediction accuracy in batched first-order LP solving, so all such numbers will be new measurements.