Many optimization pipelines do not solve one big linear program (LP). They solve thousands of small-to-medium ones. Examples include the root relaxations of every instance drawn from a problem family, the relaxations at many branch-and-bound nodes after different cutting planes have been added, and bound-tightening subproblems for different networks. On a GPU, the natural move is to stack these problems and run a first-order method, one that needs only matrix-vector products and no matrix factorizations. Batched First-Order Methods for Parallel LP Solving in MIP showed this can be 12x to 488x faster than 64-thread CPU dual simplex. It only works, however, when every problem in the batch shares the same constraint matrix. Once the matrices differ, one has to choose how to lay the problems out in memory. The obvious layouts are chosen by counting arithmetic, and on GPUs arithmetic is a poor guide to runtime.
This note proposes a batched solver for heterogeneous LPs, where the constraint matrices differ in size and sparsity pattern. It has two ideas. The first concerns convergence. Each problem in the batch gets its own step sizes, restart schedule, and primal weight, stored as vectors and applied inside a fused kernel. The second concerns hardware. Problems are grouped into buckets, and converged problems are periodically removed from the working set. Both decisions are made by a small calibrated model of memory traffic and kernel launches, not by counting nonzeros. The claim to test is that both ingredients are needed. Stacking with a single shared step size lets the worst-conditioned problem slow down all the others. Choosing layouts by floating-point operation count (FLOPs) picks layouts that are slower in wall-clock time.
Core Claim
Place $K$ heterogeneous LPs $\min_{x_i \in X_i} c_i^\top x_i$ subject to $A_i x_i = b_i$ on the diagonal of one sparse matrix. Here $x_i$ are the variables of problem $i$, $X_i$ are its variable bounds, and $A_i, b_i, c_i$ are its data. One sparse matrix-vector product then computes every $A_i x_i$ at once. The rest of a PDHG iteration is purely element-wise: gradient steps, projections onto bounds, and residual and restart bookkeeping. PDHG (primal-dual hybrid gradient) alternates a gradient step on the primal variables with one on the dual variables. The same element-wise part can carry per-problem scalars at no extra matrix cost:
$$x_i^{+} = \mathrm{proj}_{X_i}\big(x_i - \tau_i (c_i - A_i^\top y_i)\big), \qquad y_i^{+} = y_i + \sigma_i\big(b_i - A_i(2x_i^{+} - x_i)\big).$$
Here $y_i$ are the dual variables and $\tau_i, \sigma_i$ are the primal and dual step sizes of problem $i$. They are gathered by a segment index, so each problem uses its own values.
The convergence argument for per-problem control comes from Faster first-order primal-dual methods for linear programming using restarts and sharpness. That paper proves LPs satisfy a "sharpness" condition, a lower bound on how fast the error grows away from the solution. It also shows that restarted PDHG converges linearly at a rate set by the sharpness constant. For a block-diagonal problem, we expect the combined sharpness to be no better than that of the worst block, because the problem separates across blocks. We will verify this expectation rather than assume it. If it holds, a global restart schedule tuned to the stacked problem is paced by the hardest instance.
The hardware argument comes from the literature on why FLOP counts mispredict latency. ShuffleNet V2 shows that low-FLOP element-wise operations are dominated by memory access cost, and that splitting work into many small operations hurts parallelism. The element-wise part of PDHG is exactly such a chain. Polyline Path Masked Attention shows kernel launch latency dominating when work is split into many small operations, which is what happens when each small LP is solved separately. Structural Pruning via Latency-Saliency Knapsack documents a staircase effect: latency drops only when sizes cross tile boundaries. This implies that padding a bucket up to an aligned size can cost almost nothing, while cutting away work that does not cross a boundary saves nothing.
Research Program
The solver builds on the PDLP recipe from Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient: adaptive steps, restarts based on the normalized duality gap, primal weighting, and diagonal preconditioning. Every scalar in that recipe becomes a per-block vector. Restart decisions and convergence tests become per-block reductions over segments, computed in the same fused kernel as the projection and residual updates. This avoids a separate kernel launch and a host synchronization for each check.
On top of the solver sits a scheduler that makes two decisions. The first is bucketing: which instances go into which block-diagonal matrix, and whether to pad a bucket's dimensions to tile multiples. The second is compaction: when to rebuild the matrix without the blocks that have already converged. Compaction generalizes the dynamic column removal of BATCHLP to matrices that differ across problems. Rebuilding has a real cost, so it is worth doing only when the wasted work on finished blocks exceeds that cost.
Both decisions use a per-iteration time model:
$$T \approx \max\!\Big(\tfrac{B}{\beta}, \tfrac{F}{\pi}\Big) + L\,\lambda.$$
Here $B$ is the bytes moved per iteration, $F$ the FLOPs, $\beta$ and $\pi$ the device's measured memory bandwidth and peak arithmetic rate, $L$ the number of kernel launches, and $\lambda$ the per-launch overhead. This is a roofline-style form: whichever of memory or arithmetic is slower sets the time, plus fixed launch costs. HALP relies on a per-device lookup table that must be rebuilt for each platform. Our model instead has three constants, calibrated with microbenchmarks on each device, so we can test whether it transfers across GPUs. The model deliberately ignores tile quantization. Tile alignment is instead handled by explicitly evaluating padded bucket sizes, and we measure how much the model's residual error matters.
The analysis side asks two questions. First, does the sharpness of the stacked problem actually track the worst block, and how much slower does global-scalar PDHG become as the spread of conditioning within a batch grows? Second, how far apart are the layouts that minimize FLOPs and the layouts that minimize measured time?
Baselines
The do-nothing reference is sequential per-instance PDLP on the same GPU, with each LP solved to the same tolerance using the same preconditioning and restart settings. This isolates what batching buys.
The strongest existing competitor for throughput is multi-threaded CPU dual simplex. The comparison in Batched First-Order Methods for Parallel LP Solving in MIP reports the GPU batch solver at 2.18 seconds versus over 612 seconds for 64 CPU threads on facility location. It also reports 12x to 488x speedups on full strong branching, and 25.7x over sequential Gurobi on OBBT (optimization-based bound tightening). All of these numbers are for shared-matrix batches. No reported result was found on Lacuna for any GPU solver on heterogeneous-matrix LP batches. We will run CPU simplex with 64 threads, one instance per thread. Because simplex reaches high precision and PDHG does not, we will report time to a matched tolerance and time to simplex-level precision separately. We will also report the crossover batch size and problem shape below which the CPU wins. BATCHLP itself notes that tall and skinny matrices and small batches favor the CPU.
The main ablations isolate each ingredient. The first stacks all problems into one block-diagonal LP solved with global PDLP scalars; this tests per-block control. The second pads every instance to the largest one in the batch and runs a shared-structure batched solver; this is the closest analogue of BATCHLP. The third uses bucketing and compaction chosen by minimizing nonzeros processed; this tests the latency model. The fourth runs the same per-block solver without kernel fusion, using torch.compile or CUDA Graphs; this tests whether hand-written fused kernels matter. Every variant gets the same GPU, the same instances, the same tolerance, and a hyperparameter search of equal size on a held-out set of distributions.
The method wins if it reaches a relative KKT error of $10^{-4}$ (and separately $10^{-6}$) on every instance in the batch in less total wall-clock time than every ablation, on the heterogeneous distributions. KKT error measures how far a candidate is from satisfying the optimality conditions. The latency-aware scheduler must also beat nonzero-minimizing scheduling by a margin larger than run-to-run variance.
Why not just…?
Why not just stack everything block-diagonally and run PDLP as one big LP? This is the most serious threat. On a family of near-identical instances it may be essentially as good as the full method. Our prediction is that it degrades as the spread of conditioning grows, because a single step size and restart schedule are paced by the hardest block. We will test this directly by sorting batches by the spread of estimated per-instance iteration counts and plotting the slowdown of global-scalar PDLP against that spread. If the slowdown stays near 1x even on mixed batches, per-block control is not worth its complexity, and we will say so.
Why not just launch one PDLP solve per instance on concurrent CUDA streams? This avoids all layout decisions. However, launch overhead and fragmentation are known to dominate small operations, as the ShuffleNet V2 and Polyline Path results above show. Each PDHG iteration involves several small kernels per instance. The sequential and stream-based variants of the reference baseline will measure this, and we expect them to be competitive only for large instances.
Why not just pad every problem to the largest one and reuse BATCHLP? Padding recovers a regular structure, but differing sparsity patterns cannot share one matrix without taking their union. On varied batches this inflates both memory and FLOPs. The padded ablation measures exactly this cost. The staircase effect means modest padding within buckets can be free, which is why our scheduler considers padding rather than rejecting it.
Why not just use multi-threaded Gurobi, CPLEX, or SCIP simplex? For small batches and for precision-critical use it may well win. We therefore report the crossover explicitly instead of claiming dominance everywhere.
Why not let a learned model predict solutions and skip the solver? Distributional MIPLIB reports that calling a graph network inside the solver worsened the primal-dual integral on OTS (easy) from 20.0 to 27.9. Divide, Harmonize, Then Conquer It reaches within 8% of optimal but runs large multimodal-model forward passes for every node. Neither approach produces the certified tolerances we target, so we do not pursue it here.
Proposed Experiments
The primary benchmark is Distributional MIPLIB. We take the LP root relaxations of all instances in each of its 35+ distributions and solve them as one batch per distribution. This setting has naturally heterogeneous matrices with controlled similarity, and its five hardness levels let us vary the conditioning spread. The stress test is MIPLIB 2017: its 383 relaxations are batched together, which gives maximal heterogeneity in size and structure. The PDLP paper's single-instance results there (283 solved versus 50 for plain PDHG within one hour) serve as a sanity check for our per-instance solver.
The third setting is a cutting-plane loop on the facility location family from the BATCHLP paper. Different nodes carry different cut sets, and we compare against the reported 2.18-second shared-matrix time to measure the cost of heterogeneity. The fourth is OBBT bound tightening for neural network verification across different networks. This connects to Beta-CROWN, which solves LP duals on GPU through gradient-based bound propagation, but only for ReLU network structure.
Metrics are wall-clock time until all instances in a batch reach the target KKT tolerance, instances per second, the fraction of achieved memory bandwidth, the fraction of wasted FLOPs from padding and inactive blocks, and peak memory.
Four checks decide the outcome. First, measure the time-model's prediction error on two different GPUs after calibrating on only one of them. Second, compare wall-clock time for FLOP-optimal and latency-optimal schedules. If the two schedules coincide, the hardware half of the claim fails. Third, plot global-scalar slowdown against conditioning spread. If it is flat, the convergence half fails. Fourth, estimate the sharpness of the stacked problem against the minimum per-block sharpness on small instances, where both can be estimated by restarting from near-optimal points.
References
- Batched First-Order Methods for Parallel LP Solving in MIP
- Faster first-order primal-dual methods for linear programming using restarts and sharpness
- ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design
- Polyline Path Masked Attention for Vision Transformer
- Structural Pruning via Latency-Saliency Knapsack
- Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
- Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods
- Divide, Harmonize, Then Conquer It: Shooting Multi-Commodity Flow Problems with Multimodal Language Models
- Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification