組合せ最適化問題を解くためのQUBO問題変換ツール「QUBO＋＋」を無償公開

背景

昨今、多くの企業が物流の効率化、エネルギーマネジメント、効果的なスケジューリングなどの「最適化」に力を入れています。多数の選択肢から最適な解を見つける「組合せ最適化問題」を解く取り組みは、コスト削減や時間短縮、人員不足の解決など現場の課題解決に寄与するだけでなく、最小限のエネルギーで最大限の効果を生む観点で持続可能な社会の実現のためにも重要です。
組合せ最適化問題を量子アニーラーやイジングマシンで解く際は、QUBO問題に変換することが一般的であることからNTTデータグループは広島大学と共同でQUBO問題の組合せ最適化を効率よく探索する計算手法「ABS2」の開発と研究評価向けとして無償公開を行ってきました。しかし、その前段のQUBO問題への変換プログラムの開発自体が、一般的な開発者にとって難解で容易ではないこと、また、組合せ最適化問題が大規模になると変換処理に膨大な時間を要することが、ABS2の活用を進めるうえでの課題でした。この課題を解決するために、NTTデータグループと広島大学は、組合せ最適化問題をQUBO問題に変換し、解探索を行うためのC＋＋プログラミング用ツール「QUBO＋＋」を開発しました。

QUBO＋＋の概要

QUBO＋＋はC＋＋で実装されており、マルチスレッドによる並列処理にも対応しているため、QUBO問題への高速な変換処理を実現できます。
本ツールを2024年12月23日から非商用かつ研究評価目的に限り、無償で公開します。
以下のWebページからダウンロード可能です。
https://abs2.cs.hiroshima-u.ac.jp/

また、QUBO＋＋にはQUBO問題変換機能だけではなく、生成したQUBO問題を解くための簡易ソルバー^注5として、単純ながら比較的高い解探索能力を備えた「Easy Solver」と、すべての最適解を列挙できる小規模QUBO問題用のソルバー「Exhaustive Solver」がバンドルされています。このほか、NTTデータグループと広島大学が共同で開発したGPUを用いたソルバー「ABS2」や汎用の数理最適化ソルバーを呼び出すためのAPIも備えています。そのため、本ツールを使用することで、組合せ最適化問題の定式化の実装からQUBO問題への変換、ソルバーの呼び出しによる解探索までの一連の処理を行うプログラムをシームレスに開発できるようになります。

なお、NTTデータグループでは2023年4月からイノベーションセンタによる先進技術導入支援サービス^注6においてコンサルティングサービスの提供を開始しています。今回の取り組みは、その一環として実施している広島大学との共同研究成果です。成果の技術詳細については、広島大学のニュースリリースで確認できます。

今後について

NTTデータグループでは、実社会に存在する組合せ最適化問題の解決に本ツールを活用し、また、ツール自体の改良を進めるとともに、高性能GPUソルバーであるABS2のさらなる性能向上を目指します。今後は海外拠点においても、今回公開するツールを含めた量子コンピュータ／次世代アーキテクチャ・ラボのサービスを展開し、グローバルに連携を行いながら、スマートな物流網の実現やエネルギー利用の効率化などの社会課題解決に向けた適用・検証を進めていきます。

参考発表

広島大学とのこれまでの取り組みに関する発表は以下の通りです。

• 組合せ最適化問題の計算方式「Adaptive Bulk Search 2」のGPUエンジンを無償公開
• 交通・物流分野等において従来より大規模な順列型組合せ最適化問題を解くための新手法を開発
• 数理最適化によるプリント基板加工の生産効率改善の実現
• 組合せ最適化問題の計算手法「アダプティブ・バルク・サーチ」の実行環境を無償公開
• GPUの計算性能を最大限活用する組合せ最適化問題の新解法を公開

• 文章中の商品名、会社名、団体名は、各社の商標または登録商標です。