NVIDIA cuOpt 推出 mPDLP 多 GPU 线性规划求解器

本次变化

根据 NVIDIA 开发者博客（2026 年 10 月 7 日），cuOpt 引入 Multi-GPU Primal-Dual hybrid gradient for Linear Programming（mPDLP）求解器，把大规模线性规划（LP）问题分布到通过 NVLink 互联的多张 GPU 上。

PDLP 属于一阶方法，热循环是稀疏矩阵向量乘（SpMV），适合并行；mPDLP 的要点是：

• 用最小割图划分，利用同一次迭代中两次 SpMV 通过 x、y 向量共享的依赖关系，把关联紧密的变量尽量留在同一张 GPU 上，减少跨 GPU 边割与通信。
• 官方称相比单 GPU PDLP，每 GPU 峰值显存最多降低 6 倍，LP 问题规模上限为 2.1B 非零元。
• 硬件与软件栈依赖 NVLink、NVSwitch 以及 NCCL 完成设备间通信。

基准与适用场景

官方在 100 多个 LP 实例上做了对比（目标容差 1e-6、时限 1 小时），测试环境为 DGX B200 GPU 全互联 NVLink 拓扑。结论包括：

• 加速与问题规模强相关，非零元超过 1e7 后才较明显；仅看 PDLP 步骤，最大问题可达 11.4x，端到端为 4.2x（含预求解、转置、图划分与后求解等不随迭代并行的开销）。
• 在多数非零元大于 1e7 的大规模实例上，相比此前 D-PDLP 有 1.2x 到 2.5x 加速。
• 合作方数据：Kinaxis 在超过 1.35 亿变量的消费品供应链 LP 模型上，用 8 张 NVLink H100 达到 3.3x；PSR 在 1.85 亿变量的随机能源扩展 LP 模型上，用 8 张 B200 达到 5x 以上。

适用场景主要是供应链计划、能源系统容量扩展等大规模且单卡难以在计划窗口内收敛的 LP 问题。

限制与待核实事项

• 官方说明小问题并无收益，迭代同步与传输的固定成本可能超过并行收益；稀疏结构中边割比例高的实例，跨 GPU 通信可能抵消甚至反转加速。
• 三个超大规模实例上 mPDLP 反而慢于 D-PDLP，来源指出样本少、且这些基准未必代表实际业务的稀疏结构。
• 后续计划包括权重感知的最小割与超图划分、通信与计算隐藏、可行性打磨（以最优性换速度）等，均属尚未落地的方向。
• 以上数据来自官方博客的自我基准，未做独立复现；具体安装方式、API 与版本信息请以官方教程和文档为准。