Batched First-Order Methods for Parallel LP Solving in MIP

Nicolas Blin, Stefano Gualandi, Christopher Maes, Andrea Lodi, Bartolomeo Stellato
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:8542-8557, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-blin26a, title = {Batched First-Order Methods for Parallel {LP} Solving in {MIP}}, author = {Blin, Nicolas and Gualandi, Stefano and Maes, Christopher and Lodi, Andrea and Stellato, Bartolomeo}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {8542--8557}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/blin26a/blin26a.pdf}, url = {https://proceedings.mlr.press/v306/blin26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Batched First-Order Methods for Parallel LP Solving in MIP %A Nicolas Blin %A Stefano Gualandi %A Christopher Maes %A Andrea Lodi %A Bartolomeo Stellato %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-blin26a %I PMLR %P 8542--8557 %U https://proceedings.mlr.press/v306/blin26a.html %V 306 %X 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.
APA
Blin, N., Gualandi, S., Maes, C., Lodi, A. & Stellato, B.. (2026). Batched First-Order Methods for Parallel LP Solving in MIP. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:8542-8557 Available from https://proceedings.mlr.press/v306/blin26a.html.

Related Material