Scaling Decision Optimization to 100 Million Variables and Beyond with mPDLP in NVIDIA cuOpt

NVIDIA introduced the Multi-GPU Primal-Dual hybrid gradient for Linear Programming (mPDLP) solver in its cuOpt decision optimization software. According to NVIDIA, the solver distributes large LP problems across NVLink-connected GPUs to reduce solve time for problems impractical on a single GPU, and achieves up to 6x lower peak memory usage per GPU compared to single-GPU PDLP, with LP problems capped at 2.1B nonzeros.

NVIDIA said mPDLP uses min-cut partitioning that exploits shared dependencies between consecutive sparse matrix-vector multiplications, minimizing cross-GPU communication by reducing edge cuts in a bipartite dependency graph. Benchmarking on more than 100 LP instances using NVIDIA DGX B200 GPUs showed speedups strongly correlating with problem size, becoming noticeable when nonzero entries exceed 10^7 and reaching up to 11.4x on PDLP steps alone for the largest problems, including tsp-gaia-10m. On most large-scale instances above that threshold, mPDLP achieved 1.2x to 2.5x speedup over the prior D-PDLP approach; NVIDIA noted performance varies with sparsity structure and edge-cut ratios, and that on three ultra-large-scale instances mPDLP was slower than D-PDLP.

NVIDIA reported partner results: Kinaxis achieved a 3.3x speedup on a CPG supply chain model with over 135M variables using eight NVLink-connected H100 GPUs on its Maestro platform, and PSR demonstrated more than 5x speedup on a stochastic energy expansion model with 185M variables using eight B200 GPUs.

Planned improvements NVIDIA listed include weight-aware min-cut and hypergraph partitioning, hiding communications by splitting matrices into local and remote components, and feasibility polishing. A cuOpt mPDLP tutorial, source code on the NVIDIA/cuopt GitHub repo, and product documentation are available.