用 mPDLP 把决策优化扩展到 1 亿变量以上
来自 NVIDIA Developer · 期号 2026-10-07
摘要
线性规划问题规模一大，单张 GPU 就装不下或算不完。NVIDIA cuOpt 新出的 mPDLP 求解器把问题拆到多张 NVLink 互联的 GPU 上一起算。 核心技巧是「最小割图分区」：把约束矩阵 A 对应的二分图切成 k 份（k 等于 GPU 数），让紧密相关的变量留在同一张卡上，跨卡通信只发生在被切断的边上。这样每次迭代里的两次稀疏矩阵向量乘（SpMV）大部分都在本地完成。 在 DGX B200 上的基准测试：非零元超过 10^7 的问题，mPDLP 的 PDLP 步本身最高加速 11.4 倍；相比上一代 D-PDLP 方案，加速 1.2 到 2.5 倍（具体取决于稀疏结构和边切率）。每张 GPU 的峰值内存最多降低 6 倍。 两个合作伙伴的实测：Kinaxis 用 8 张 H100 在 1.35 亿变量的供应链模型上拿到 3.3 倍加速；PSR 用 8 张 B200 在 1.85 亿变量的随机能源扩展模型上超过 5 倍。 本文是技术详解，附了教程和 GitHub 源码链接。