# Batched First-Order Methods for Parallel LP Solving in MIP

arXiv: https://arxiv.org/abs/2601.21990 · HTML: https://mlsanity.com/paper/2601.21990/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 32 references that are in the map.
- First posted on arXiv 29 Jan 2026.

## Builds on (most cited first, 22 of 22)

- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [Operator splitting for a homogeneous embedding of the linear complementarity problem](https://mlsanity.com/paper/2004.02177/) (2020)
- [GPU Acceleration of ADMM for Large-Scale Quadratic Programming](https://mlsanity.com/paper/1912.04263/) (2019)
- [Flexible Differentiable Optimization via Model Transformations](https://mlsanity.com/paper/2206.06135/) (2022)
- [Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness](https://mlsanity.com/paper/2105.12715/) (2021)
- [cuPDLP.jl: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for Linear Programming in Julia](https://mlsanity.com/paper/2311.12180/) (2023)
- [MPAX: Mathematical Programming in JAX](https://mlsanity.com/paper/2412.09734/) (2024)
- [Restarted Halpern PDHG for Linear Programming](https://mlsanity.com/paper/2407.16144/) (2024)
- [cuPDLPx: A Further Enhanced GPU-Based First-Order Solver for Linear Programming](https://mlsanity.com/paper/2507.14051/) (2025)
- [PDLP: A Practical First-Order Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2501.07018/) (2025)
- [HPR-LP: An implementation of an HPR method for solving linear programming](https://mlsanity.com/paper/2408.12179/) (2024)
- [Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming](https://mlsanity.com/paper/2102.04592/) (2021)
- [Stochastic Primal Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes](https://mlsanity.com/paper/2301.02511/) (2023)
- [Accelerated Infeasibility Detection of Constrained Optimization and Fixed-Point Iterations](https://mlsanity.com/paper/2303.15876/) (2023)
- [The Role of Level-Set Geometry on the Performance of PDHG for Conic Linear Optimization](https://mlsanity.com/paper/2406.01942/) (2024)
- [A New Crossover Algorithm for LP Inspired by the Spiral Dynamic of PDHG](https://mlsanity.com/paper/2409.14715/) (2024)

## Built on by (most cited first, 1 of 1)

- [From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs](https://mlsanity.com/paper/2605.22188/) (2026)

## Abstract (arXiv)

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 one can use. This is a significant step for the design and development of integer programming algorithms tightly exploiting GPU capabilities where we argue that some specific operations should be allocated to GPUs and performed in full instead of using light-weight heuristic approaches on CPUs.