NVIDIA cuOpt mPDLP Solver Scales Linear Programming to 100 Million Variables

NVIDIA cuOpt introduces the Multi-GPU Primal-Dual hybrid gradient for Linear Programming (mPDLP) solver, which distributes large LP problems across NVLink-connected GPUs. The solver targets problems that are impractical to solve within a planner's time window on a single GPU, and it reduces peak memory usage per GPU by up to 6x compared to single-GPU PDLP, with LP problems capped at 2.1 billion nonzeros.

The PDLP algorithm is a first-order method based on gradient descent, making it highly parallelizable and GPU-friendly. Its hot loop is a Sparse Matrix-Vector Multiplication (SpMV) followed by map operations. The iterative algorithm alternates between computing the primal solution x and the dual solution y, each requiring an SpMV with the constraint matrix A or its transpose. These SpMVs are memory-bound, so increasing available bandwidth speeds up the operation. Using more GPUs multiplies the total bandwidth, but introduces communication overhead and load imbalance.

Min-cut partitioning reduces cross-GPU communication

Previous multi-GPU efforts, such as D-PDLP, used 2D partitioning of the constraint matrix, computing each SpMV independently. cuOpt mPDLP instead exploits the shared dependencies between consecutive SpMVs through the x and y vectors. The solver materializes a bipartite dependency graph from the matrix A, then partitions it k-ways for k GPUs to reduce edge cuts. Each GPU owns a subset of rows and columns, so most computation stays local. Communication only occurs on edges that are cut between partitions, which reduces the need for cross-GPU data exchange.

This method's performance depends heavily on the number of edge cuts, which varies with the sparsity pattern of A. NVIDIA reports that benchmarking on over 100 LP instances using DGX B200 GPUs shows speedups that correlate 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. On most large-scale instances, mPDLP achieves 1.2x to 2.5x speedup over the prior D-PDLP approach.

Partner applications show real-world gains

Kinaxis reported a 3.3x speedup on a supply chain model with over 135 million variables using eight NVLink-connected H100 GPUs. PSR demonstrated more than 5x speedup on a stochastic energy expansion model with 185 million variables using eight B200 GPUs. These results highlight the practical benefits for globally constrained supply and production planning, and for large-scale energy-system capacity-expansion models.

NVIDIA provides the communication stack for distributed computation: NVLink and NVSwitch for hardware, and NCCL for software, enabling GPU-direct point-to-point communication and collective operations. The mPDLP solver is available through the cuOpt tutorial, with source code on GitHub for APIs, solver settings, and deployment guidance.