• QUBO(二次無制約二値最適化)問題を解くことにより、資源配置やスケジューリングなどのさまざまな最適化を行えることが知られており、そのため多くの企業・大学がQUBO問題を解くQUBOソルバーの開発を競っています。
• アダプティブ・バルク・サーチは、GPU^(注1)の計算能力を最大限に引き出すように設計されたQUBOソルバーで、さまざまな局所探索手法を同時に実行します。
• QUBO問題によって適した局所探索手法が異なるため、実行経過を観察しながらそのQUBO問題に適した局所探索手法を求め、重点的に実行します。
• アダプティブ・バルク・サーチによるQUBOソルバーの実行環境を、研究評価目的に限り無償公開します。
• 利用者は、QUBO問題の行列を公開GPUサーバーにアップロードすることにより、アダプティブ・バルク・サーチが求めた解を得ることができます。
• 公開GPUサーバーURL：https://qubo.cs.hiroshima-u.ac.jp/

広島大学大学院先進理工系科学研究科の中野浩嗣教授らの研究チームは、株式会社NTTデータと共同で、QUBO問題をGPUで解く新しい計算方式｢アダプティブ・バルク・サーチ｣を開発し、2020年8月に国際会議International Conference on Parallel Processing (ICPP)で発表しました。この計算方式の改良を、発表後も続けてきました。主な改良点は次の通りです。

• さまざまな解探索手法を同時実行して、良解を求めると予想される解探索手法を自動的に選択。
• それまでに発見した良解を保持する解プールを複数個用いて独立に探索し、解プールが互いに近づくように少しずつ探索空間を絞っていくことにより、暫定最良解の近傍をなるべく網羅的に探索する。
• 最大128k(131，072)ビットの大規模全結合QUBO問題に対応可能。

改良の結果、QUBO問題の種類によっては、改良前には1時間実行しても得られなかった最適解が1分程度で得られるようになりました。この改良版QUBOソルバーを、広島大学大学院先進理工系科学研究科コンピュータシステム研究室に設置したGPUサーバー(NVIDIA RTX A6000 GPUを5基搭載)で研究評価目的に限り無償公開します。利用者は、解きたいQUBO問題をこの公開GPUサーバーにアップロードすることができます。QUBOソルバーは5基のGPUをフルに活用してそのQUBO問題の解を探索し、得られた解を利用者に提示します。

(注1) GPU：
　Graphics Processing Unitの略で、グラフィック処理のための集積回路です。計算処理能力の高さから、グラフィック処理以外のさまざまな処理を高速化することができるため、多くのスーパーコンピュータに搭載されています。

• 国際会議名: International Conference on Parallel Processing (ICPP) 2020
• 論文タイトル: Adaptive Bulk Search: Solving Quadratic Unconstrained Binary Optimization Problems on Multiple GPUs
• 著者名: Ryota Yasudo、 Koji Nakano、 Yasuaki Ito、 Masaru Tatekawa、 Ryota Katsuki、 Takashi Yazane、 Yoko Inaba
• DOI: https://doi.org/10.1145/3404397.3404423
• 公開GPUサーバーURL: https://qubo.cs.hiroshima-u.ac.jp/