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

著者： Dr. Cara Touretzky and Dr. Robert Luce

Gurobi は、cuOpt の PDLP のオープンソースリリースが、より多くの GPU に適したアルゴリズムを線形計画法にもたらすことに期待を寄せています。また、cuOpt の他の機能が最適化ユーザーにどのように役立つかについても注目しています。

Gurobi と NVIDIA が cuOpt に関してどのように協力しているかを示すため、GPU アクセラレーション最適化における我々の初期の取り組みと、これらのオープンソースツールによる最適化業界の展望についてまとめました。

線形計画法のための一次法：新たな選択肢

数十年にわたり、線形計画法（Linear Programming: LP）の分野では、単体法（Simplex Method）と内点法（Interior Point Methods: IPMs）という 2 つの強力なアルゴリズムが主流でした。これらのアルゴリズムは何十年にもわたって改良され、最適化において強力で信頼性の高い主力ツールであり続けています。しかし、これらの手法に GPU アクセラレーションを適用するには、大きな課題がありました。

そのような中、大規模 LP 問題において、従来のアルゴリズムがうまく機能しない場合の補完的な選択肢として、一次法（First-Oder Methods）という新しいアプローチが登場しました（この論文を参照）。

単体法や内点法が、行列分解、ピボット操作、三角化といった計算量的に重い線形代数演算に依存するのに対し、一次法は勾配ベースの更新を使用し、疎行列ベクトル乗算（Sparse Matrix-Vector Multiplications）のような計算量的に軽量な操作に依存するという異なるアプローチを取ります。このシンプルさこそが、GPU 上での高効率な実装を可能にし、大規模 LP の解き方を変革する道を開くものとなります。

Gurobiの一次法への取り組み

一次法の適用可能性を受けて、Gurobi は実験的な主双対ハイブリッド勾配法（Primal- Dual Hybrid Gradient: PDHG）型アルゴリズムを開発し、最適化エンジンに統合しました。このアルゴリズムは 2 つの形式で実装されています。

• 共有メモリ並列処理を採用した純粋な CPU ベースのアルゴリズム

• NVIDIA cuSparse ライブラリと CUDA フレームワークを使用したGPUアクセラレーションバージョン。（GPU への取り組みとテスト手法の詳細については、こちらをご覧ください。）

我々の内部ベンチマークでは、実世界の特定の大規模問題において、CPU ベースの PDHG アルゴリズムの段階で、高度に開発され最適化された単体法および内点法の実装と競合しうることが示されています。この利点は、GPU ベースの PDHG 実装によってさらに拡大されます。CPU のメモリシステムと比較して、GPU の高いメモリ帯域幅は、パフォーマンスの大幅な向上に直結します。このアルゴリズムを、前処理（Presolve）やクロスオーバー（Crossover）などの他のソルバーコンポーネントと組み合わせることで、一部の大規模インスタンスにおいて、高精度な最適解を比較的短時間で得ることができます。

これらの結果はまだ初期段階であり、概念実証（Proof of Concept）と考えています。しかし、私たちは興奮しています。なぜなら、新しいアルゴリズムの選択肢が現実世界の最適化アプリケーションに新たな機会を開く開発曲線の始まりに過ぎないことを知っているからです。より集中的なエンジニアリング、テストに利用できるより大規模な LP モデル、そしてお客様やコミュニティからのより多くのフィードバックがあれば、一次法の可能性は、最適化アプリケーションのユーザーに具体的な利益をもたらすと考えています。

NVIDIA cuOpt PDLP とオープンソース

GPU アクセラレーションされた一次法への私たちの道のりは、一つの重要な教訓を裏付けました。それは、パフォーマンスはあらゆる実装の詳細に依存するということです。メモリ転送パターンの最適化から CUDA カーネルの効率的な実装まで、エンジニアリングレベルで正しく行うことが、お客様が期待するパフォーマンスを達成するために不可欠です。

そのため、NVIDIA が cuOpt ライブラリの PDLP コンポーネントをオープンソース化する意向であることを大変うれしく思います。CUDA フレームワークの広範さと効率性により、NVIDIA は GPU アクセラレーションコンピューティングライブラリを提供する上で議論の余地のないリーダーであり、PDLP に関するエンジニアリングの専門知識を共有することは、商用ソルバー業界、オープンソース最適化ソルバー、および学術研究グループのすべてが最高クラスの実装から学ぶことができることを意味します。このオープンソース化は、PDLP のような手法に関するさらなる研究を確実に刺激し、次レベルのパフォーマンスのために一次法を洗練させるでしょう。

また、最適化アルゴリズムをオープンソース化することは、最適化ソリューションベンダーと顧客のシステム全体にとって有益であると信じています。これにより、可視性が向上し、より多くの研究者や実践者が関わることを促し、最終的に現実世界の最適化アプリケーションが依存するツールへの信頼を構築します。

今後の展望

NVIDIA の cuOpt の PDLP 実装をオープンソース化するという決定を称賛し、継続的な協力、学習、イノベーションに期待しています。Gurobi と NVIDIA が協力しあうことで、大規模最適化の境界を押し広げ、現実世界の課題に対してより高速で効率的なソリューションを提供できるよう尽力していきます。

Gurobi Optimizer

Gurobiの意思決定インテリジェンス技術により、顧客は数秒で最適なビジネス判断を行うことができます。シフトスケジューリングやポートフォリオ最適化からサプライチェーン設計まで、あらゆることにおいて、Gurobi は数兆の可能性の中から最適解を特定します。

意思決定インテリジェンスのリーダーとして、Gurobi は統合しやすく、フル機能のソフトウェアと業界最高レベルのサポートを提供し、業界トップの98%の顧客満足度を誇っています。

2008 年に設立された Gurobi は、南北アメリカ、ヨーロッパ、アジアで事業を展開しています。SAP、エールフランス、NFL（ナショナルフットボールリーグ）などの組織を含む、ほぼすべての業界の顧客にサービスを提供しています。詳細については、https://www.gurobi.com/ をご覧ください。

最適な評価ライセンスを選択し、技術トランスファーとサポートのために我々のエキスパートチームとの作業を開始してください。無料試用ライセンスをリクエストして、クラウド上でモデルがどれほど迅速かつ簡単に解決できるかをご確認ください。