NVIDIAのGPU4基で「1秒間に1兆の解を探索」 広島大学の研究グループが高速探索手法を開発：「巡回セールスマン問題」を1秒以内に解く

広島大学大学院の教授である中野浩嗣氏らの研究チームは、組み合わせ最適化問題の解を高速に探索する新しい計算方式「アダプティブ・バルク・サーチ」を開発した。著名な組み合わせ最適化問題である「最大カット問題」「巡回セールスマン問題」「ランダム問題」について、いずれも1秒以内で最適解が得られたという。

[＠IT]

　広島大学大学院先進理工系科学研究科の教授である中野浩嗣氏らの研究チームは2020年8月17日、NTTデータと共同で組み合わせ最適化問題の解を高速に探索する新しい手法「アダプティブ・バルク・サーチ」を開発したと発表した。同手法は複数のGPUを用いて2次非制約2値最適化（QUBO）問題の解を並列探索する。

アダプティブ・バルク・サーチの概要図（出展：広島大学）

NVIDIAのGPUを4基備えたコンピュータで実験

　QUBO問題とは「nビットの変数を持つ2次式の値が最小になるように各変数に0または1を割り当てる」という組み合わせ最適化問題。「巡回セールスマン問題」などの組み合わせ最適化問題は、QUBO問題に置き換えて考えることができる。このため、多くの大学や企業はQUBO問題を解くシステムや手法を開発している。

　QUBO問題を解くための万能な解法は存在せず、問題の種類によって適したアルゴリズムは異なる。「シミュレーテッドアニーリング」といった従来の最適解探索アルゴリズムは、同じ解を何度も探索するなど効率が悪く、最適解が得られない場合もある。