Linear Programming From Disk: Spending More Compute per Pass Over the Constraint Matrix

Large linear programs (LPs) arise in web-scale ranking, sparse regression and routing, and their constraint matrices can be larger than a machine's memory. First-order LP solvers such as PDLP touch the matrix only through two products, $Ax$ and $A^T y$. Methods that need only these products are called matrix-free, and in principle the matrix could stay on an SSD and be read in pieces. In practice, a primal-dual iteration reads every non-zero of $A$ about once and does almost no arithmetic on it. Thousands of iterations become thousands of full reads from a drive that is roughly an order of magnitude slower than memory.

This proposal changes the unit of progress from one iteration to one pass over the matrix on disk. The plan is to solve LPs with an augmented Lagrangian method, a penalty-plus-multiplier scheme that turns the LP into a sequence of bound-constrained quadratic problems. Each quadratic problem is solved by block coordinate descent over column blocks of $A$ streamed from disk. While one block is in memory, the solver runs as many coordinate updates on that block as it can before the next block arrives. These local updates are exact minimization steps on a single convex objective, so extra work on a loaded block does not risk divergence. That risk is exactly what happens when one naively adds local repeated steps to a primal-dual method. A short warm-started primal-dual phase, also streamed from disk, then supplies the high final accuracy that coordinate methods are known to lack.

Core Claim

For LPs whose sparse constraint matrix lives on secondary storage, block-coordinate augmented Lagrangian sweeps reach moderate accuracy, around $10^{-4}$ relative error in the optimality conditions, in many fewer disk passes than streamed primal-dual iteration. The inner work per loaded block costs nothing in wall-clock time as long as it fits inside the time needed to prefetch the next block.

Global feasibility information also comes almost free. The solver keeps the residual $r = Ax - b$ (size $m$) and the iterate $x$ (size $n$) in memory. The column products $A_j^T y$ that coordinate descent needs anyway yield the dual residual by the end of each pass. Restart and penalty decisions can therefore use exact global quantities once per pass, with no extra reads.

What is new is the combination of three things in an out-of-core setting with general constraints $Ax=b,\ x\ge 0$:

  • an algorithm whose amount of work per resident block can grow without breaking convergence;
  • a stopping rule for that work tied to measured I/O time;
  • a handoff to a primal-dual polishing phase.

Relation to Prior Work

The method is assembled from pieces that exist separately. The closest out-of-core precedent is the block minimization approach of Large Linear Classification When Data Cannot Fit in Memory. It keeps the weight vector in RAM, streams compressed data blocks, and "stays awhile" on each block doing dual coordinate descent. It trained on a 20.8 GB dataset with 1 GB of RAM. It handles only unconstrained or box-constrained classification, and we reuse its streaming and compression design for general linear constraints.

The inner solver comes from Sparse Linear Programming via Primal and Dual Augmented Coordinate Descent (AL-CD) and from A New Alternating Direction Method for Linear Programming (LPADMM). Both solve LP subproblems by coordinate descent at cost proportional to the non-zeros of $A$, and both assume $A$ is in memory. Both papers also constrain the design. AL-CD reports slow convergence at high precision and little gain when the solution is dense, which is why a polishing phase is needed. LPADMM flags subproblem-tolerance management and penalty sensitivity as open problems; our once-per-pass global residuals are a direct way to drive both.

The polishing phase and its target accuracy come from Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient (PDLP) and Faster first-order primal-dual methods for linear programming using restarts and sharpness. These show that restarted primal-dual hybrid gradient (PDHG) reaches $10^{-8}$ with only matrix-vector products. Both keep $A$ in memory. Adding local steps to PDHG would break the step-size and restart guarantees in the second paper, which is why our "stay awhile" work lives in the augmented Lagrangian phase rather than inside PDHG.

Avoiding Communication in Primal and Dual Block Coordinate Descent Methods reduces communication by unrolling coordinate updates across processors on a network. It is a cousin of this idea for unconstrained ridge-type problems, not for disk-resident LPs.

The batched-access loaders Brand: Managing Training Data with Batched Random Access and scDataset motivate the I/O side. They show that random disk access destroys throughput and that block sizes are currently hand-tuned. They rely on freely permuting samples in stochastic gradient descent, which constrained primal-dual coupling does not allow, so we use deterministic cyclic block order instead.

Research Program

The system stores $A$ on NVMe as compressed column blocks sized to a fraction of a fixed RAM budget. It keeps $x$, $y$, $r$, the diagonal scaling vectors and two block buffers in memory, and double-buffers reads so the next block loads while the current one is processed. Diagonal Ruiz scaling, which repeatedly rescales rows and columns by their norms as in PDLP, needs a few preliminary passes; we count them in every reported cost.

The augmented Lagrangian subproblem at outer step $k$ is

$$\min_{x \ge 0}\; c^T x - y_k^T(Ax-b) + \tfrac{\rho}{2}\|Ax-b\|^2,$$

where $y_k$ is the current dual estimate and $\rho>0$ is the penalty. A coordinate update on column $j$ needs only column $A_j$ and the residual $r$, and it updates $r$ in place.

The "stay" rule is simple: keep running coordinate sweeps over the resident block until the prefetch of the next block completes, subject to a cap. Inner work is thus as large as the hardware makes free, with no hand-tuned block parameter. After each full pass, the solver does three things using the exact residuals collected during the pass:

  • checks the subproblem tolerance;
  • updates $y_{k+1} = y_k - \rho r$ when the tolerance is met;
  • rebalances $\rho$ from the ratio of primal to dual residuals.

When relative error in the optimality conditions (the KKT error) stalls above the target, the solver switches to streamed PDHG with PDLP's restarts, warm-started from $(x, y)$.

The streamed PDHG is itself a contribution and doubles as our main baseline. With row-block storage, each loaded block $A_i$ updates its dual slice $y_i$ from the extrapolated primal point. It then immediately adds $A_i^T y_i$ into the next iteration's adjoint product. One PDHG iteration therefore costs one disk pass, not two.

On the analysis side, we will try to bound the decrease of the subproblem objective per pass for cyclic exact block minimization with arbitrary extra inner sweeps. This would show that staying on a block never costs passes. We would combine it with inexact augmented Lagrangian tolerance schedules into a pass-complexity bound to moderate accuracy. A full proof covering the PDLP-style polishing heuristics is out of scope, since the PDLP paper itself lists that as open.

Baselines

The naive reference point is in-memory PDLP run under a RAM cap smaller than $A$ using memory-mapped storage, so the operating system decides what to page. This is what a practitioner gets today. We expect it to thrash, as in-memory LIBLINEAR "essentially stalled due to disk swapping" on webspam in Large Linear Classification When Data Cannot Fit in Memory.

The strongest competitor is our fused one-pass streamed PDLP with the same compressed blocks, prefetching and preconditioning. It keeps every PDLP heuristic and differs only in where $A$ lives, so it isolates whether the augmented Lagrangian phase buys anything beyond good I/O engineering. In memory, PDLP solved 283 of 383 MIPLIB 2017 relaxations to $10^{-8}$ within one hour. It also solved a 10-million-node PageRank LP in 5.4 hours, where Gurobi ran out of memory or failed to finish within 24 hours. These numbers come from Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient. Unconstrained in-memory PDLP on a large-RAM machine also serves as an upper reference on speed. No reported result was found on Lacuna for any LP solver running with the constraint matrix out of core.

The coordinate-method baseline is in-memory AL-CD, which solved the rcv1 L1-SVM LP in 3,155 seconds while CPLEX failed to finish in 48 hours (Sparse Linear Programming via Primal and Dual Augmented Coordinate Descent). LPADMM reports 10% to 85% less clock time than AL-CD (A New Alternating Direction Method for Linear Programming). We run both in memory on instances that fit and in our streaming harness on those that do not.

Two ablations isolate the key ingredient. The first fixes exactly one coordinate sweep per loaded block, which is block augmented Lagrangian without staying. The second removes the PDHG polishing phase.

All methods share the same machine, drive, cgroup-enforced RAM cap, block format and compression, and preconditioning passes. Each gets the same budget for tuning its penalty and step parameters on a held-out subset of instances. The proposal beats streamed PDLP if it reaches $10^{-8}$ KKT error in at least 2x less wall-clock time, or solves more instances within a fixed time limit, at equal RAM. A smaller gain, confined to moderate accuracy, would still be reported as a narrower result.

Why not just…?

Why not just stream PDLP from a fast NVMe drive and accept the bandwidth gap? This is the real threat, and it is why streamed PDLP is our primary baseline rather than a strawman. PDLP is already limited by memory bandwidth in RAM, so a drive several times slower might cost only a constant factor. If fused streamed PDLP matches us in wall-clock time, the honest conclusion is that good I/O engineering suffices. We would then publish the one-pass fused streaming design as the result. The pass-count measurements decide this directly.

Why not just compress $A$ until it fits in RAM and run an in-memory solver? Compression made out-of-core classification practical in Large Linear Classification When Data Cannot Fit in Memory, and moderate memory deficits may be solved this way. We will report the compression ratio of each instance and include "decompress in memory, run PDLP" as a baseline wherever the compressed matrix fits. The claim is restricted to the regime where it does not fit, such as webspam-scale LPs under a 2 GB cap or PageRank LPs well beyond 10^7 nodes.

Why not just rely on the operating system's paging with memory-mapped files? The file shows that this fails for repeated passes. LIBLINEAR stalled on webspam, and scDataset documents massive latency from uncoordinated small disk reads under memory-mapped random access (scDataset). The naive baseline measures how badly this fails for primal-dual LP access patterns, which are sequential but repeated.

Why not just subsample constraints, or use a distributed cluster? Dropping rows of $A$ changes the feasible region, so the answer can be infeasible for the true problem. Out-of-core training on full data also beat in-RAM subsamples in Large Linear Classification When Data Cannot Fit in Memory. Distribution is a valid alternative but trades disk reads for network communication, which Avoiding Communication in Primal and Dual Block Coordinate Descent Methods shows can dominate runtime. Our target is single commodity machines, and we do not claim to beat clusters.

Proposed Experiments

We use three benchmark families, each run under artificial RAM caps.

The first is PageRank LPs on synthetic Barabási-Albert graphs, following PDLP. We reproduce the 10^7-node instance under caps of 25% and 10% of the matrix size, then scale to 10^8 nodes, where no in-memory baseline fits on our machine.

The second is the L1-regularized SVM LP formulation from AL-CD, applied first to rcv1 to check the in-memory baseline. We then apply it to webspam (16.6 million features, 20.8 GB raw) under 1 GB to 4 GB caps. This gives a natively sparse LP far larger than RAM.

The third is the 383 MIPLIB 2017 relaxations, together with the Mittelmann instances qap15 and nug20, under caps set at a fixed fraction of each instance's matrix size. These test robustness on degenerate, poorly conditioned problems, where we expect the coordinate phase to help least.

We report the following metrics:

  • disk passes and bytes read to reach $10^{-4}$ and $10^{-8}$ relative KKT error;
  • wall-clock time;
  • peak resident memory;
  • the fraction of each pass in which I/O, rather than compute, was the bottleneck;
  • on MIPLIB, the number of instances solved within one hour and the geometric mean of solve times.

The decisive check is a plot of KKT error against passes over $A$. On it we compare the proposal, its one-sweep ablation and streamed PDLP. The central claim holds only if the full method needs clearly fewer passes than the ablation and than streamed PDLP to reach $10^{-4}$, and the polishing handoff keeps that advantage at $10^{-8}$.

A second check targets the claim that inner work is free. We vary drive speed by throttling bandwidth and check that the adaptive stay count rises as the drive slows, while wall-clock time per pass stays flat.

A third check targets the known weakness of coordinate methods. On MIPLIB instances with dense optimal solutions, we report where the method loses to streamed PDLP and whether switching to PDLP earlier recovers its performance.