The evolution of linear programming (LP) solvers has been marked by significant milestones over the past century, from
Simplex
to the
interior point method (IPM)
. The introduction of
primal-dual linear programming (PDLP)
has brought another significant advancement.
NVIDIA cuOpt
has now implemented PDLP with GPU acceleration. Using cutting-edge algorithms, NVIDIA hardware, dedicated CUDA features, and NVIDIA GPU libraries, the cuOpt LP solver achieves over 5,000x faster performance compared to CPU-based solvers.
This post examines the key components of LP solver algorithms, GPU acceleration in LP, and cuOpt performance on
Mittelmann’s benchmark
and
Min Cost Flow problem
instances.
Harnessing cutting-edge innovations for large-scale LP
LP is a method that involves optimizing a linear objective function, subject to a set of linear constraints.
Consider this scenario: A farmer must decide which vegetables to grow and in what quantities to maximize profit, given limitations on land, seeds, and fertilizer. The goal is to determine the optimal revenue while respecting all constraints, as quickly as possible.
NVIDIA developed an LLM agent
example that helps model the problem and solve it using an LP solver. LP is an essential tool for optimization and has applications in resource allocation, production planning, supply chain, and, as a backbone for
mixed-integer programming
(MIP) solvers. Solving mathematical problems with millions of variables and constraints in seconds is challenging, if not impossible, in some cases.
There are three requirements to solve LP problems efficiently on GPUs:
Efficient and massively parallel algorithms
NVIDIA GPU libraries and CUDA features
Cutting-edge NVIDIA GPUs
Efficient and massively parallel algorithms
Simplex
, introduced by Dantzig in 1947, remains a core component of most LP and MIP solvers. It works by following the edges of the feasible region to find the optimum.
Figure 1. Simplex method
(Source:
Visually Explained – What is Linear Programming (LP)?
)
The next major advancement came with the
interior point method (IPM)
, discovered by I. I. Dikin in 1967. IPM, which moves through the interior of the polytope towards the optimum, is now considered state-of-the-art for solving large-scale LPs on CPUs. However, both techniques face limitations in massive parallelization.
Figure 2. Interior Point Method
(Source:
Visually Explained – What is Linear Programming (LP)?
)
In 2021, a new groundbreaking technique to solve large LPs was introduced by the Google Research team:
PDLP
. It is a first-order method (FOM) that uses the derivative of the problem to iteratively optimize the objective and minimize constraint violation.
Figure 3. Gradient descent
PDLP enhances
primal-dual hybrid gradient (PDHG)
algorithm by introducing tools to improve convergence, including a presolver, diagonal preconditioning, adaptive restarting, and dynamic primal-dual step size selection. Presolving and preconditioning make the input problem simpler and improves numerical stability while restarting and dynamic step size computation enables the solver to adapt itself during optimization.
A key advantage of FOM over previous methods is its ease of massive parallelization, making it well-suited for GPU implementation.
PDLP employs two highly parallelizable computational patterns: Map operations and sparse matrix-vector multiplications (SpMV). This approach enables PDLP to efficiently handle millions of variables and constraints in parallel, making it extremely effective on GPUs.
Map is extensively used in PDLP to perform additions, subtractions, and so on for all the variables and constraints that can span millions of elements. It is extremely parallel and efficient on GPUs.
SpMV corresponds to multiplying a sparse matrix (containing many zeros) and a vector. While this matrix size can reach tens of billions, it contains far fewer useful values. For instance, in a vegetable planting problem, a constraint such as, “I can’t plant more than 3.5 kg of potatoes” would contain only one useful value among millions of variables.
SpMV algorithms have been extensively optimized for GPUs, making them orders of magnitude faster than CPU implementations.
NVIDIA GPU libraries and CUDA features
To have the best performance, our GPU PDLP implementation uses cutting-edge CUDA features and the following NVIDIA libraries:
cuSparse
Thrust
RMM
cuSparse
is the NVIDIA GPU-accelerated library for sparse linear algebra. It efficiently performs SpMVs, a challenging task on GPUs. cuSparse employs unique algorithms designed to fully leverage the NVIDIA massively parallel architecture.
Thrust is part of the
NVIDIA CUDA Core Compute Libraries
(CCCL) and provides high-level C++ parallel algorithms. It simplifies the expression of complex algorithms using patterns and iterators for GPU execution. I used Thrust for map operations and the restart process, which entails sorting values by key. This is a task that can be demanding on the GPU but is efficiently optimized by Thrust.
RMM
is the fast and flexible NVIDIA memory management system that enables the safe and efficient handling of GPU memory through the use of a memory pool.
Finally, I took advantage of advanced CUDA features. One of the most significant challenges in parallelizing PDLP on GPUs is the restart procedure, which is inherently iterative and not suited for parallel execution. To address this, I used
CUDA Cooperative Groups
, which enable you to define GPU algorithms at various levels, with the largest being the grid that encompasses all workers. By implementing a cooperative kernel launch and using grid synchronization, you can efficiently and elegantly express the iterative restart procedure on the GPU.
Cutting-edge NVIDIA GPUs
GPUs achieve fast computation by using thousands of threads to solve many problems in parallel. However, before processing, the GPU must first transfer the data from the main memory to its worker threads.
Memory bandwidth
refers to the amount of data that can be transferred per second. While CPUs can usually handle hundreds of GB/s, the latest GPU,
NVIDIA HGX B100
, has a bandwidth of eight TB/s, two orders of magnitude larger.
The performance of this PDLP implementation scales directly with increased memory bandwidth due to its heavy reliance on memory-intensive computational patterns like Map and SpMV. With future NVIDIA GPU bandwidth increases, PDLP will automatically become faster, unlike other CPU-based LP solvers.
cuOpt outperforms state-of-the-art CPU LP solvers on Mittelmann’s benchmark
The industry standard to benchmark the speed of LP solvers is
Mittelmann’s benchmark
. The objective is to determine the optimal value of the LP function while adhering to the constraints in the shortest time possible. The benchmark problems represent various scenarios and contain between hundreds of thousands to tens of millions of values.
For the comparison, I ran a state-of-the-art CPU LP solver and compared it to this GPU LP solver. I used the same threshold of 10
-4
and disabled crossover. For more information, see the
Potential for PDLP refinement
section later in this post.
Both solvers operated under
float64
precision.
For the CPU LP solver, I used a recommended CPU setup: AMD EPYC 7313P servers with 16 cores and 256 GB of DDR4 memory.
For the cuOpt LP solver, I used an NVIDIA H100 SXM Tensor Core GPU to benefit from the high bandwidth and ran without presolve.
I considered the full solve time without I/O, including scaling for both solvers and presolving for the CPU LP solver. Only instances that have converged for both solvers with a correct objective value are showcased in Figure 4. cuOpt is faster on 60% of the instances and more than 10x faster in 20% of the instances. The biggest speed-up is 5000x on one instance of a large multi-commodity flow optimization problem.
Figure 4. cuOpt acceleration compared to CPU LP on Mittelmann’s benchmark
I also compared cuOpt against a state-of-the-art CPU PDLP implementation using the same setup and conditions. cuOpt is consistently faster and between 10x to 3000x faster.
Figure 5. cuOpt acceleration compared to a CPU PDLP implementation on Mittelmann’s benchmark
The multi-commodity flow problem (MCF) involves finding the most efficient way to route multiple different types of goods through a network from various starting points to their respective destinations, ensuring that the network’s capacity constraints are not exceeded. One way to solve an MCF problem is to convert it to an LP. On a set of large MCF instances, PDLP is consistently faster, between 10x and 300x.
Figure 6. cuOpt acceleration compared to the CPU LP solver on a set of MCF instances
Potential for PDLP refinement
The NVIDIA cuOpt LP solver delivers incredible performance, but there’s potential for future enhancements:
Handling higher accuracy
Requiring high bandwidth
Convergence issues on some problems
Limited benefit for small LPs
Handling higher accuracy
To decide whether you’ve solved an LP, you measure two things:
Optimality gap:
Measures how far you are from finding the optimum of the objective function.
Feasibility:
Measures how far you are from respecting the constraints.
An LP is considered solved when both quantities are zero. Reaching an exact value of zero can be challenging and often unnecessary, so LP solvers use a threshold that enables faster convergence while maintaining accuracy. Both quantities are now only required to be below this threshold, which is relative to the magnitude of the values of the problem.
Most LP solvers use a threshold, especially for large problems that are extremely challenging to solve. The industry standard so far was to use 10
-8.
While PDLP can solve problems using 10
-8
, it is then usually significantly slower. This can be an issue if you require high accuracy. In practice, many find 10
-4
accurate enough and sometimes even lower. This heavily benefits PDLP while not being a big differentiator for other LP-solving algorithms.
Requiring high bandwidth
PDLP’s performance scales linearly with memory bandwidth, making it more efficient on new GPU architectures. It requires a recent server-grade GPU to reproduce the results shown in the performance analysis section.
Convergence issues on some problems
While PDLP can solve most LPs quickly, it sometimes needs a significant number of steps to converge, resulting in higher runtimes. On Mittelmann’s benchmark, cuOpt LP Solver times out after one hour on 8 of the 49 public instances, due to a slow convergence rate.
Limited benefit for small LPs
Small LPs benefit less from the GPU’s high bandwidth, which doesn’t enable PDLP to scale as well compared to CPU solvers. The cuOpt LP solver offers a batch mode for this scenario where you can provide and solve hundreds of small LPs in parallel.
Conclusion
The cuOpt LP solver uses CUDA programming, NVIDIA GPU libraries, and cutting-edge NVIDIA GPUs to solve LPs, potentially orders of magnitude faster than CPU and scaling to over a billion coefficients. As a result, it’s particularly beneficial for tackling large-scale problems, where its advantages become even more prominent.
Some use cases will still work better with traditional Simplex or IPM and I expect the future solvers to be a combination of GPU and CPU techniques.
Sign up to be notified when you can
try the cuOpt LP
. Try NVIDIA
cuOpt Vehicle Routing Problem (VRP
) today with
NVIDIA-hosted NIM
microservices for the latest AI models for free on the
NVIDIA API Catalog
.
Reading Time:
3
minutes
線形計画法 (LP: Linear Programming) ソルバーの進化は、
シンプレックス法
から
内点法 (IPM: Interior Point Method)
まで、過去 1 世紀にわたってに重要な節目で特徴づけられてきました。
主双対線形計画法 (PDLP: Primal-dual Linear Programming)
の導入は、さらなる大きな進歩をもたらしました。
NVIDIA cuOpt
は現在、GPU アクセラレーションで PDLP を実装しています。最先端のアルゴリズム、NVIDIA ハードウェア、専用の CUDA 機能、NVIDIA GPU ライブラリを使用して、cuOpt LP ソルバーは、CPU ベースのソルバーと比較して 5,000 倍以上の高速パフォーマンスを実現しています。
この投稿では、LP ソルバー アルゴリズムの主要コンポーネント、LP における GPU アクセラレーション、
Mittelmann のベンチマーク
と
最小費用フロー問題
のインスタンスにおける cuOpt 性能を検証します。
最先端のイノベーションを大規模な LP に活用
LP は、一連の線形制約の対象となる線形目的関数を最適化する手法です。
例えば、こんなシナリオを考えてみてください。農家は、土地、種、肥料に制約がある中で、利益を最大限に高めるために、どの野菜をどれくらい栽培するかを決めなければなりません。目標は、あらゆる制約を満たしながら、できるだけ迅速に最適な収益を決定することです。
NVIDIA が開発した LLM エージェント
の例は、LP ソルバーを使用して問題をモデル化し、解決するのに役立ちます。LP は最適化に不可欠なツールであり、リソースの配分、生産計画、サプライチェーン、
混合整数計画問題
(MIP: Mixed-integer Programming) ソルバーのバックボーンとして応用されています。数百万もの変数や制約がある数学的問題を数秒で解くことは、不可能ではないにせよ、難しい場合もあります。
GPU で効率的に LP 問題を解決するには、以下の 3 つの要件があります。
効率的で大規模な並列アルゴリズム
NVIDIA GPU ライブラリと CUDA 機能
最新鋭の NVIDIA GPU
効率的で大規模な並列アルゴリズム
1947 年に Dantz 氏によって導入された
シンプレックス法
は、現在でもほとんどの LP と MIP ソルバーの中核をなしています。これは、実現可能な領域の端を追って最適値をを求めるものです。
図 1. シンプレックス法 (出典:
Visually Explained – What is Linear Programming (LP)?
)
次の大きな進歩は、1967 年に I. I. Dikin 氏が発見した
内点法 (IPM: Interior Point Method)
でした。多面体の内部を最適値の方向に移動する IPM は、現在では CPU 上で大規模な LP を解く最先端技術だと考えられています。しかしながら、いずれの手法も大規模な並列化には限界があります。
図 2. 内点法 (出典:
Visually Explained – What is Linear Programming (LP)?
)
2021 年に、大規模 LP を解く新しい画期的な技術として、Google Research チームによって発表されましたのが、
PDLP
です。PDLP は、問題の導関数を使用して、目的を繰り返し最適化し、制約違反を最小限に抑える一次法 (FOM: First-order Method) です。
図3. 勾配降下
PDLP は、プレソルバー、対角線の前提条件、適応的なリスタート、動的な主双対ステップ サイズ選択など、収束を改善するツールを導入することで、
主双対ハイブリッド勾配 (PDHG: Primal-dual Hybrid Gradient)
アルゴリズムを強化します。プレソルバーと前提条件により、入力問題がより簡素化され、数値安定性が向上します。一方、リスタートと動的ステップ サイズ計算により、ソルバーは最適化中に適応することができます。
FOM が従来の手法よりも優れている点として、大規模な並列化が容易であり、GPU の実装に適しています。
PDLP は、Map 演算と疎行列ベクトル積 (SpMV: Sparse Matrix-Vector Multiplications) の 2 つの高度に並列化可能な計算パターンを採用しています。このアプローチにより、PDLP は数百万もの変数と制約を効率的に並列処理することができ、GPU に対して非常に効果的になります。
Map は、PDLP で広く使用されており、数百万の要素に及ぶすべての変数と制約に対して加算や減算などを行います。これは、GPU 上では極めて並列処理が可能でかつ効率的です。
SpMV は、疎行列 (多くのゼロを含む) とベクトルの乗算に相当します。この行列のサイズは数百億に達しますが、有用な値ははるかに少なくなります。例えば、野菜の植え付け問題では、「3.5 kg 以上のジャガイモを植えることができない」といった制約には、数百万の変数の中で有用な値が 1 つしか含まれないことになります。
SpMV アルゴリズムは、GPU 向けに広範囲に最適化されており、CPU 実装よりも桁違いに高速です。
NVIDIA GPU ライブラリと CUDA 機能
最高のパフォーマンスを得るために、NVIDIA の GPU PDLP 実装では、最先端の CUDA 機能と以下の NVIDIA ライブラリを使用しています。
cuSparse
Thrust
RMM
cuSparse
は、疎線形代数の NVIDIA GPU 対応ライブラリです。これは、GPU では難しいとされる SpMV を効率的に実行します。cuSparse は、NVIDIA の巨大な並列アーキテクチャをフル活用するように設計された独自のアルゴリズムを採用しています。
Thrust は、
NVIDIA CUDA コア コンピューティング ライブラリ
(CCCL) の一部であり、高いレベルの C++ 並列アルゴリズムを提供します。GPU の実行にパターンとイテレーターを使用して、複雑なアルゴリズムの表現を簡素化します。私は、Map 演算とキーで値をソートするリスタートのプロセスに Thrust を使用しました。これは、GPU に負荷がかかる作業ですが、Thrust で効率的に最適化できます。
RMM
は、高速かつ柔軟な NVIDIA メモリ管理システムで、メモリ プールを使用することで、GPU メモリの安全で効率的な処理を実現します。
最後に、高度な CUDA の機能を利用しました。GPU 上で PDLP を並列化する際の最も重要な課題の 1 つは、本来反復的であり、並列実行には適していないリスタート手順です。これに対処するために、私は
CUDA Cooperative Groups
を使用しました。これは、さまざまなレベルで GPU アルゴリズムを定義でき、最も大きなのものはすべてのワーカーを網羅するグリッドになります。協調的なカーネル起動を実装し、グリッド同期を利用することで、GPU 上で反復的なリスタート手順を効率的かつエレガントに表現できます。
最先端の NVIDIA GPU
GPU は、数千ものスレッドを使用して多くの問題を同時に解決することで、高速計算を実現します。しかし、処理する前に、GPU はまずメイン メモリからワーカー スレッドにデータを転送する必要があります。
メモリ帯域幅
とは、1 秒間に転送できるデータ量のことです。CPU では通常、数百 GB/秒を処理できますが、最新の GPU である
NVIDIA HGX B100
の帯域幅は 8 TB/秒で、2 桁も大きい値です。
この PDLP 実装のパフォーマンスは、Map や SpMV のようなメモリ負荷の高い計算パターンに大きく依存しているため、メモリ帯域幅の増加に応じて、直線的に拡大します。将来的に NVIDIA GPU の帯域幅が増加すれば、他の CPU ベースの LP ソルバーとは異なり、PDLP は自動的に高速化されます。
cuOpt は、Mittelmann のベンチマークで最先端の CPU LP ソルバーを上回る性能を発揮
LP ソルバーの速度を評価する業界標準が、
Mittelmann のベンチマーク
です。その目的は、制約を満たしながら LP 関数の最適値を可能な限り最短時間で決定することです。ベンチマークの問題は、さまざまなシナリオを示しており、数十万から数千万の値を含んでいます。
比較のために、私は最新の CPU LP ソルバーを実行し、この GPU LP ソルバーと比較しました。同じ閾値である 10
-4
を用いて、クロスオーバーを無効にしました。詳細については、この投稿の後半にある
PDLP 改良の可能性
のセクションを参照してください。
どちらのソルバーも
float64
の精度で動作しました。
CPU LP ソルバーの場合、推奨される CPU 設定である、16 コアと 256 GB の DDR4 メモリを備えた AMD EPYC 7313P サーバーを使用しました。
cuOpt LP ソルバーの場合、高帯域幅のメリットを活用するため、NVIDIA H100 SXM Tensor コア GPU を使用し、プレソルバーなしで実行しました。
両方のソルバーのスケーリングと CPU LP ソルバーのプレソルバーなど、I/O なしの完全な解決時間を考慮しました。正しい目標値を持つ両方のソルバーの場合、収束したインスタンスのみを図 4 で示しています。cuOpt は、60% のインスタンスで高速化し、20% のインスタンスで 10 倍以上高速化しました。最大の高速化は、大規模な多品種流問題の最適化のうちの 1 つのインスタンスで 5,000 倍の高速化が達成されました。
図 4. Mittelman のベンチマークで CPU LP と比較した cuOpt の高速化
また同じ設定と条件を使用して、最新の CPU PDLP の実装と cuOpt を比較しました。cuOpt は常に高速化し、10 倍～ 3000 倍も高速化します。
図 5. Mittelman のベンチマークで CPU PDLP 実装と比較した cuOpt の高速化
多品種流問題 (MCF: Multi-commodity Flow Problem) では、ネットワークの容量制約を超えないように、さまざまな出発点からそれぞれの目的地までネットワークを介して複数のさまざまな物をルーティングする最も効率的な方法を見つけることができます。MCF 問題を解決する 1 つの方法は、LP に変換することです。一連の大規模な MCF インスタンスでは、PDLP は一貫して 10 倍から 300 倍の間で高速になります。
図 6. 一連の MCF インスタンスで CPU LP ソルバーと比較した cuOpt の高速化
PDLP 改良の可能性
NVIDIA cuOpt LP ソルバーは、驚異的なパフォーマンスを発揮しますが、将来的に強化される余地もあります。
より高い精度への対応
高帯域幅の必要性
一部の問題に対する収束問題
小規模な LP に対する限定的な効果
より高い精度への対応
LP を解決したかどうかを判断するには、以下の 2 点を測定します。
最適性のギャップ
: 目的関数の最適値からの距離を測定します。
実現可能性
: 制約をどのくらい満たしているかを測定します。
LP は、両方の値がゼロになった時、解決したとみなされます。厳密にゼロの値に到達することは困難であり、不要なことも多いため、LP ソルバーは精度を維持しながら収束をより高速化する閾値を使用します。両方の値が、この閾値以下であることが要求されるため、問題の値の大きさに対して相対的なものになります。
ほとんどの LP ソルバーは、特に解決するのが非常に困難な大きな問題に対して、閾値を使用します。これまでの業界標準では、10
-8
を使用していました。PDLP は 10
-8
を使用して問題を解決することもできますが、通常はかなり時間がかかります。高い精度が求められる場合、これは問題になります。実際には、多くの場合 10
-4
で十分な精度であると考える人も多く、場合によってはそれよりも低い値でも十分であると考える人もいます。これは、PDLP には大きな利点となりますが、他の LP 解決アルゴリズムの大きな差別化要因にはなりません。
高帯域幅の必要性
PDLP のパフォーマンスはメモリ帯域幅に比例して拡張し、新しい GPU アーキテクチャではより効率的になります。前述したパフォーマンス分析のセクションで示した結果を再現するには、最近のサーバー グレードの GPU が必要です。
一部の問題に対する収束問題
PDLP は、ほとんどの LP を迅速に解決できますが、収束するまでにかなりのステップ数が必要になることがあり、その結果、実行時間が長くなることがあります。Mittelman のベンチマークでは、cuOpt LP ソルバーは、49 の公開インスタンスのうち 8 つで、収束率が遅いため、1 時間後にタイムアウトしました。
小規模な LP に対する限定的な効果
小規模な LP が、GPU の高帯域幅から利益を得ることは少なく、CPU ソルバーと比較して PDLP を拡張できません。cuOpt LP ソルバーは、このようなシナリオに対応するバッチモードを用意しており、数百もの小規模な LP を並行して提供し、解決できます。
まとめ
cuOpt LP ソルバーは、CUDA プログラミング、NVIDIA GPU ライブラリ、および最新鋭の NVIDIA GPU を使用して、LP を解決します。これは、CPU よりも桁違いに高速で、10 億を超える係数にまで拡大される可能性があります。その結果、大規模な問題に取り組む上で特に有益であり、その利点はさらに顕著になります。
GTC セッション:
Advances in Optimization AI (最適化 AI の進歩)
NGC コンテナー:
cuOpt
SDK:
cuOpt
SDK:
cuSOLVERMp
SDK:
cuSOLVER
従来のシンプレックス法や IPM を用いたほうが上手くいくユース ケースもありますが、将来的には、GPU と CPU の技術を組み合わせたソルバーが主流になるでしょう。
登録すると、
cuOpt LP を試せるように
なった際に、通知を受け取ることができます。
NVIDIA API カタログ
で、
NVIDIA が提供する
最新の AI モデル向けの NIM マイクロサービスを使用して、NVIDIA の
cuOpt 車両経路問題 (VPR: Vehicle Routing Problem
) を今すぐ無料でお試しください。
関連情報