Batched First-Order Methods for Parallel LP Solving in MIP

Nicolas Blin, Stefano Gualandi, Christopher Maes, Andrea Lodi, Bartolomeo Stellato

arXivarxiv/2601.21990Jan 29, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2601.21990
curl -X POST /api/v1/records/arxiv/2601.21990/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.21990/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'