用批量一阶方法并行求解多个线性规划，提升混合整数规划效率。
Batched First-Order Methods for Parallel LP Solving in MIP
- 将原对偶混合梯度法扩展为批量处理，利用矩阵-矩阵运算替代重复矩阵-向量运算。
- 在GPU上实现显著加速，特定问题规模下优于传统单纯形法。
- 适合需要高性能并行计算的混合整数规划求解场景。
我们提出一种在GPU上并行求解多个线性规划的批量一阶方法。该方法将原对偶混合梯度算法扩展至批量处理，高效求解混合整数规划中强分支与边界紧化等技术产生的相关线性规划问题。通过采用矩阵-矩阵操作替代重复的矩阵-向量操作，在GPU架构上获得显著计算优势。我们在多个案例研究中验证了该方法的有效性，并确定了在一阶方法优于传统单纯形法的问题规模，具体取决于可用计算环境。这是推动紧耦合利用GPU能力的整数规划算法设计的重要一步，我们认为某些特定操作应完全交由GPU执行，而非在CPU上使用轻量启发式方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。