本記事はGurobi.comに掲載されている下記の記事を日本語訳しています。

Using GPUs to Solve LPs vs. MIPs: What’s the Difference?

著者： Dr. Cara Touretzky, Dr. Robert Luce, Dr. David Torres Sanchez, and Dr. Byron Tasseff

混合整数線形計画法（MILPまたはMIP）モデルは、あらゆる業界の意思決定プロセスにおいて中心的な要素となっています。近年、GPUによる計算能力の向上に伴い、最適化分野の研究者たちが、このハードウェアがMIPモデルを解くためのアルゴリズムにどのような影響を与えるのかに関心を寄せているのは当然のことでしょう。

線形計画問題を解くことは、現代のMIP（混合整数計画法）ソルバーにおける基本的なステップです。したがって、「GPUはMIPアルゴリズムのパフォーマンスをどのように向上させるのか？」という問いに答えるには、「GPUはLPアルゴリズムのパフォーマンスをどのように向上させるのか？」という問いにも答える必要があります。

本稿では、これらの疑問点と将来的な影響について考察していきます。

GPU上でのソルバー性能：重要なポイント

特定のモデルにおけるソルバーの性能は、求解に使用されるアルゴリズムと ハードウェアの両方の能力に依存します。例えば、Gurobiの新しいリリースごとに提供されるアルゴリズムの改良により、ユーザーは新しいハードウェアに投資することなく、パフォーマンスの向上を実現できます。一方で、最新のGPUやCPUといった強力なハードウェアを活用する高度な最適化アルゴリズムによっても、これまで解決不可能と思われていた問題に挑戦できるようになってきています。

ソルバーアルゴリズムとハードウェアの最近の進歩に基づき、LPとMIPに関する重要なポイントを以下に示します。

• 単体法やバリア法（内点法）では解くのが難しい大規模なLP（線形計画問題）は、PDHGアルゴリズムを用いることで良好な性能を発揮する可能性がある。

• ルートノードで多くの時間を費やすMIPモデル（つまり、大規模なLPを解く場合）も、ルートノードでPDHGを使用することでメリットが得られる可能性がある。

• 現在使われているLPやMIPの大半では、確立されたバリア法や単体法を用いる方が、より優れた性能を発揮する可能性が高い。

これまでのGurobiの検証においてLPを解く際にGPU上で一次法（GurobiのPDHGアルゴリズム実装など）を用いることで、非常に大規模なLPモデルインスタンスにおいてパフォーマンスが向上する可能性があることは明らかになってきています。しかしながら、MIPに対する分枝限定法アルゴリズムをGPUを用いて高速化することは、依然として活発な研究分野です。その点について、以下で詳しく説明します。

GPUはLPアルゴリズムのパフォーマンスをどのように向上させるのか？

図1に示す、線形計画問題を解く主な手順を考えてみましょう。以下の点に注目してください。

• 主要な3つのアルゴリズムオプション（単体法、バリア法、PDHG法）はすべてCPU上で実行可能です。（Gurobiは、複数のLPアルゴリズムを並列実行するconcurrent methodも提供しています。）

• バリア法とPDHGでは、基底解を得るためにCrossoverという追加の手順が必要です。基底解は、MIPモデルの分枝限定法の開始点として使用されます。一般的に、Crossoverにかかる時間は、バリア法またはPDHGによる解の質によって異なります。ほとんどのPDHGアルゴリズムは、デフォルトで低品質な解で終了するため、Crossoverにはより多くの時間が必要になる可能性があります。

• PDHGアルゴリズムは、GPUアーキテクチャでの実行に最も適しています。バリア法や単体法とは異なり、疎行列とベクトルの乗算のみに依存しており、GPU上で効率的に実行できます。GurobiのPDHG法は、バージョン13.0で利用可能です。

• Gurobiはまだ一般に利用可能なGPU対応のバリア法を提供していませんが、バリア法で使用される行列分解演算はGPU上で実装できることが知られています

図1. LPのフレームワーク。

*GurobiのGPU向けLPバリア法は、まだ一般公開されていません。

PDHGのような一次法やバリア法を構成する演算はどちらもGPU上で実行できますが、近年特に注目を集めているのはPDHGです。これは、PDHGアルゴリズムの仕組みがGPU上での実装において非常に容易であるためです。主/双対単体法がこの議論に含まれていないのは、これらのアルゴリズムはCPUハードウェア上でも並列化が難しく、GPU上ではさらに困難だからです。

PDHGは、特にGPU上で実行する場合、他の方法と比較して、一部の大規模LPにおいて実行時間の改善をもたらす可能性があります。そのような問題の多くは、PDHGが高品質な解を達成できる巨大なLPモデルであり、Crossoverステップによってフレームワークの実行時間が大幅に増加することは無いという特徴を持ちます。Crossoverに関するこの報告は、すでに並行Crossover手法の分野における新たな研究を促しています。また、基底解が不要なケースでは、十分な精度で計算されていれば、PDHG単独による解でも許容される場合があります。

Gurobiでは、GPU上でLPのベンチマークを行う際、通常はCrossoverにかかる時間を考慮します。これは、お客様が通常体験するアプリケーション全体の実行時間を把握する必要があるためです。最適化アプリケーションの関係者は、この違いを認識しておく必要があります。なぜなら、他のベンチマークではCrossoverステップが考慮されず、代わりに非基底解に到達するまでの時間を比較している場合があるからです。また、他のベンチマークではPDHGの収束許容誤差を緩く設定している場合があり、これにより非基底解に到達するまでの実行時間が短縮されます。

GPUはMIP（混合整数計画問題）の分枝限定法フレームワークにどのような影響を与えるのか？

図2. 非常に簡略化された分枝限定法のフレームワーク。

*GurobiのGPU向けLPバリア法は、まだ一般公開されていません。

LPによる解法は、今日のMIPアルゴリズムの根幹を成しています。図2の簡略化されたフレームワークは、MIPを解く際に用いられる分枝限定法による探索を示しています。GPUはこのワークフローにおいて様々な分野で活用できます。

• 分枝限定法ツリーのルートノードで発生する最初のLP：Gurobi 13.0のPDHGを使用して、GPU上でルートノードのLP緩和問題を解くことが可能

• 一部のヒューリスティックや前処理コンポーネントはGPUアクセラレーションに適している可能性があり、Gurobiはこれらのコンポーネントの実装について積極的に研究を進めている

現時点では、GPU上でPDHGを使用してノード緩和LP（分枝限定法の探索木内のステップにおけるLP緩和問題）を解くことは推奨されません。単体法の優れたウォームスタート機能と、分枝限定法フレームワークへの広範な統合を考慮すると、一次法を使用してノード緩和LPのパフォーマンスを向上させることは困難です。PDHG（および追加されたCrossoverステップ）によって、このステップの全体的な実行時間が増加する可能性があります。これらの理由から、ほとんどのモデルでは、単体法が依然としてノード緩和LPの標準アルゴリズムとなっています。

MIPに関して現在可能なこととして、解決時間の大部分が最初のLPルート緩和に費やされるケースでは、分枝限定法フレームワークのそのステップでGPUを使用することでメリットが得られる可能性があります（例えば、このページの例2のrmine25モデル）。図3はこの概念を示しており、モデルBはモデルAよりも最適解到達時間の改善が大きいことがわかります。これは、LPフェーズが全体の実行時間の大部分を占めているためです。モデルBと同様の挙動を示すモデルを扱っている場合は、最初のLPステップでGPU上のPDHGを使用することで全体的なパフォーマンスが向上するかどうかを評価する価値は十分にあります。

図3は、LP緩和ステップが困難なMIPモデルにおける実行時間の改善例。この図では、バリア法からPDHG法に変更してもCrossover時間が大幅に増加しないことを前提としています。これは単純化した例であり、実際にはCrossover時間が長くなる可能性があり、その場合は最適解到達時間の改善効果が低下する可能性があります。

アルゴリズムはGPUとCPUをどのように連携して利用するのか？

ソルバーフレームワークはGPUハードウェアのみで動作することはできないという点に留意してください。CPUは多くの計算タスクとソルバーのオーケストレーションを担います。特定のアルゴリズムの主要コンポーネントのみがGPUを利用できるため、CPUとGPUの連携はハードウェア選定において不可欠な考慮事項となります。

図2に示すように、ソルバーフレームワークには依然としてCPU上で実行されるステップが多数存在します。現在、ノード選択、前処理、カットの追加、ヒューリスティックなどのアルゴリズムコンポーネントは、不規則な制御フローと動的なデータ操作を必要とし、これらはCPUに適した特性です。これらのアルゴリズムコンポーネントは、ノード緩和LPの解法と相まって、MIPモデル全体の実行時間の大部分を占めており（図3のモデルAの例を参照）、すべてがGPUに対応しているわけではありません。そのため、現時点では、MIPをGPU上で実行しても、CPU上で実行した場合と比べてパフォーマンスが大幅に向上するとは限りません。

しかし、特定のヒューリスティックや前処理がGPU上で有効化可能となってきているため、これらのコンポーネントを使用するMIP問題はGPUアクセラレーションの恩恵を受けることが期待されます。ただし、現時点では、GPU上でMIPを解くことが有効なのは、ルートLP緩和が全体の実行時間の大部分を占める場合に限られます。

基盤となるアルゴリズムとハードウェアが進化し続けるにつれて、これらの結論も変化する可能性があります。しかし我々がこれらの結論に至った根拠を共有することは、最適化コミュニティにとって有益であると考えています。MIPのパフォーマンスに関する見通しが個々のモデルにどのような影響を与えるかを理解することで、最適化技術スタックにおけるGPUの将来的な導入計画をより効果的に立てることができます。

私たちの研究は続く

要約すると、MIP（混合整数計画問題）の分枝限定法フレームワークには、数十もの異なる構成要素が関わっています（図2は大幅に簡略化されています）。これらの各ステップの基盤となるアルゴリズムを改善することで、実行されるハードウェアの種類に関わらず、パフォーマンスが向上します。

現時点では、分枝限定法フレームワーク以外のLPコンポーネントはGPUアクセラレーションに対応しており、巨大LP（およびルートLP緩和が困難なMIP）の全体的なパフォーマンス向上に貢献しています。分枝限定法フレームワークのより多くのコンポーネントがGPUで有効化されるにつれて、より多くのMIPモデルがGPUアクセラレーションの恩恵を受ける可能性があります。

CPUとGPUのハードウェアを評価する際の鍵は、これらのコンポーネント間の相互作用を理解することです。特定のモデルインスタンスにおける全体的なパフォーマンスへの影響を予測することは困難であるため、どのハードウェアで実行するかを決定する際には、必ずベンチマークテストを実施し、特定のモデルに合わせて調整することをお勧めします。

これは依然として刺激的で活発な研究分野であり、Gurobiは急速に進化するこの分野において、GPU上で有望な新しいアルゴリズムの評価と採用を継続的に行っています。Gurobi Optimizerの動作（GPUアクセラレーションを含む）をご覧になりたい場合は、今すぐ無料評価ライセンスをお申し込みいただくか、ベンチマーク用のモデルをお送りください。