Batched First-Order Methods for Parallel LP Solving in MIP
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911407242477568 |
|---|---|
| author | Blin, Nicolas Gualandi, Stefano Maes, Christopher Lodi, Andrea Stellato, Bartolomeo |
| author_facet | Blin, Nicolas Gualandi, Stefano Maes, Christopher Lodi, Andrea Stellato, Bartolomeo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21990 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Batched First-Order Methods for Parallel LP Solving in MIP Blin, Nicolas Gualandi, Stefano Maes, Christopher Lodi, Andrea Stellato, Bartolomeo Optimization and Control Machine Learning 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. |
| title | Batched First-Order Methods for Parallel LP Solving in MIP |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2601.21990 |