Batched First-Order Methods for Parallel LP Solving in MIP

We present a batched first-order method for solving multiple linear programs in parallel on GPUs. Our approach extends the primal-dual hybrid gradient algorithm to efficiently solve batches of related linear programming problems that arise in mixed-integer programming techniques such as strong branching and bound tightening. By leveraging matrix-matrix operations instead of repeated matrix-vector operations, we obtain significant computational advantages on GPU architectures. We demonstrate the effectiveness of our approach on various case studies and identify the problem sizes where first-order methods outperform traditional simplex-based solvers, depending on the computational environment. This is a significant step toward integer programming algorithms that tightly exploit GPU capabilities. We argue that some specific operations should be allocated to GPUs and performed in full, instead of relying on lightweight heuristic approaches on CPUs.

Mixed-integer programming (MIP) is the technology behind tools that schedule airline crews, plan supply chains, and make other decisions where choices are discrete rather than continuous. An MIP solver repeatedly handles many small linear programs (LPs) that differ in only a few numbers; hundreds of nearly-identical LPs may be solved at one branching step just to pick which variable to fix next. Today this work runs on the CPU, with each LP solved on its own. We built a GPU-friendly LP solver that solves a whole batch of closely related LPs at once, replacing many small matrix-vector products with one large matrix-matrix product that GPUs perform very efficiently. We also added the engineering to make this work in practice: independent stopping for subproblems that finish first, a batch-wide restart rule, and automatic batch sizing. On standard benchmarks our batched GPU solver is 12 to nearly 500 times faster than the CPU baseline for strong branching, and about 25 times faster on a bound-tightening preprocessing task. Today's MIP solvers approximate these subroutines aggressively to limit CPU cost; our result opens the door to MIP solvers that put the GPU to work on the heavy lifting and afford accurate branching decisions.