NVIDIA announced cuOpt Multi‑GPU Primal‑Dual hybrid gradient for Linear Programming (mPDLP), a distributed solver that partitions large sparse LPs across NVLink/NVSwitch‑connected GPUs. The design targets planning problems that exceed a single GPU’s memory or take too long to converge within practical planning windows. NVIDIA highlights two principal benefits: reduced solve times for huge LPs and up to 6x lower peak memory per GPU compared with single‑GPU PDLP (for LPs capped at 2.1 billion nonzeros).
Why multi‑GPU PDLP matters
Supply chains, energy systems and other large planning applications are modeling more SKUs, lanes and constraints, increasing model sizes and uncertainty. While cuOpt on a single GPU already delivers more than 10x speedups over CPU solvers on large LPs, the largest problems can still take hours or overflow a single GPU’s memory. Historically challenging benchmarks such as zib03 (introduced by Thorsten Koch in 2008 with over 104 million nonzeros) illustrate the continuing demand for both algorithmic and hardware advances. mPDLP aims to push those limits further by distributing work across multiple GPUs.
The PDLP algorithm in brief
Primal‑Dual hybrid gradient for LP (PDLP) is a first‑order iterative method that alternates operations on the primal vector x and the dual vector y. Its hot loop is dominated by Sparse Matrix‑Vector Multiplications (SpMV) with A and A^T, interleaved with elementwise projections and arithmetic. Because these operations are highly parallelizable, PDLP is well suited to GPUs, but SpMV is memory‑bound: additional memory bandwidth (for example via multiple GPUs) can speed up the operation — provided communication and load imbalance are controlled.
Stripped to the core SpMV communications, PDLP alternates between computing A^T y and A x, so consecutive SpMVs share dependencies through x and y.
Distribution strategy: min‑cut partitioning
Previous distributed PDLP implementations used 2D partitioning: reorder the matrix for better balance, partition it into row/column blocks, perform SpMV on each subblock and sum partial outputs. cuOpt mPDLP instead constructs the bipartite graph defined by A (linking primal and dual variables) and applies k‑way min‑cut partitioning to reduce cross‑GPU edges. The idea is to keep tightly connected dependencies local so that consecutive SpMVs require minimal inter‑GPU communication.
A partition assigns subsets of rows and columns to GPUs. Edges inside a partition are computed locally; edges cut across partitions cause explicit communication. The fewer edge cuts after partitioning, the less cross‑GPU traffic in each PDLP iteration.
Hardware and software building blocks
NVIDIA relies on NVLink and NVSwitch for high‑bandwidth device interconnect and on NCCL (NVIDIA Collective Communications Library) to provide GPU‑direct point‑to‑point and collective operations (AllReduce, AllGather, Broadcast). Together they let multiple GPUs behave like a fast shared machine with low overhead data movement, so the distributed PDLP steps can remain on the GPU without round trips to host memory.
Benchmarks and limits
NVIDIA benchmarked mPDLP against single‑GPU cuOpt PDLP and a prior multi‑GPU D‑PDLP across more than 100 LP instances from datasets including Hans Mittleman LPFeas, PDLP and D‑PDLP benchmark sets, the Open Energy Benchmark, and partner problems. Targets used: tolerance 10^−6 and a one‑hour time limit. Distributed solvers were measured on a node with NVIDIA DGX B200 GPUs in an all‑to‑all NVLink topology; single‑GPU PDLP used one B200 GPU.
Key results:
- Speedup correlates strongly with problem size. Noticeable multi‑GPU gains appear once nonzero counts exceed ~10^7; above that threshold larger problems benefit more from mPDLP than from single‑GPU PDLP.
- Considering only the PDLP steps, mPDLP reached up to 11.4x speedup on the tsp‑gaia‑10m instance. End‑to‑end speedups are smaller (e.g., 4.2x in some runs) because presolve, host‑side transpose, graph partitioning and postsolve are not distributed.
- Versus D‑PDLP, mPDLP generally achieved 1.2x–2.5x faster runtimes on most large instances (nnz > 10^7). On three ultra‑large benchmark instances, however, mPDLP was slower than D‑PDLP; those instances may have sparsity patterns unlike the real‑world models mPDLP is tuned for.
Limitations and caveats:
- Multi‑GPU PDLP shows gains primarily for sufficiently large problems; for small instances constant per‑iteration synchronization and data transfer costs can outweigh parallelism benefits.
- The sparsity structure matters: high edge‑cut ratios after min‑cut partitioning produce heavy cross‑GPU communication and can erase or reverse speedups.
Industry examples
Two partners demonstrated production‑scale benefits:
- Kinaxis: reported a 3.3x speedup on a CPG supply‑chain LP with over 135 million variables using cuOpt mPDLP on eight NVLink‑connected NVIDIA H100 GPUs on the Maestro platform.
- PSR: reported more than 5x speedup on a stochastic energy expansion LP with 185 million variables using cuOpt mPDLP on eight NVLink‑connected NVIDIA B200 GPUs.
These results indicate that mPDLP can deliver meaningful wall‑clock improvements on very large industrial models.
Ongoing and planned improvements
NVIDIA lists several development directions for cuOpt mPDLP:
- Weight‑aware min‑cut and hypergraph partitioning to make partitions account for per‑GPU computational load, reducing load imbalance and communication overhead.
- Overlapping communication and computation (hiding communications) by splitting the matrix into local and remote components so local work runs in parallel with remote data transfers.
- Feasibility polishing: trading some optimality for faster convergence to feasible solutions, which can make more large problems solvable within practical time limits.
Getting started
NVIDIA provides a cuOpt mPDLP tutorial notebook that walks users through installing cuOpt, configuring the solver and comparing solve times across GPU counts. The cuOpt source is available in the NVIDIA/cuopt GitHub repository, with documentation on APIs and deployment; community discussion is supported via the cuOpt GitHub Discussion Forum.
Conclusion
cuOpt mPDLP extends GPU‑accelerated LP solving to multi‑GPU systems using min‑cut partitioning and NVIDIA interconnect and communication primitives. It achieves significant PDLP‑step speedups on sufficiently large, sparse LPs, reduces per‑GPU memory use in very large problems, and has demonstrated real‑world benefits with industry partners, while further work on partitioning, communication overlap and convergence techniques remains ongoing.
