NTTデータと広島大、組合せ最適化問題をGPUで高速解決する技術

アダプティブ・バルク・サーチの動作イメージ

　株式会社NTTデータおよび広島大学大学院先進理工系科学研究科による研究チームは17日、GPUを利用して組合せ最適化問題の解を高速で見つけ出す計算手法「アダプティブ・バルク・サーチ」を開発した。

　組合せ最適化問題は、複数の要素のなかからもっと優れた選択肢を求めるというもので、物流の効率化などさまざまな分野の問題に応用が可能だとされている。量子アニーリングやGPU、FPGAなどを用いたアーキテクチャの研究開発が進められており、組合せ最適化問題をQUBO(Quadratic Unconstrained Binary Optimization)問題に帰着させた上で、これを高速に解決していく。

　今回研究グループが開発したアダプティブ・バルク・サーチは、解の探索手法を問題にあわせて柔軟に変化させられる点に加え、計算機の規模や台数に比例した計算速度の向上が可能な点が特徴。GPUのアーキテクチャ特性を考慮し、解を並列で探索できる設計を採用し、GeForce RTX 2080 Tiを4基搭載した計算サーバーにおいて1秒間に1兆以上の解を探索できたという。

　実験では、最大カット問題や巡回セールスマン問題、ランダム問題における高速性が示せており、現時点で32,768までの変数をもつQUBO問題が扱えるとしている。研究グループでは、今回開発した手法を活用して流通や金融分野、エネルギー利用の効率化やマシンラーニングの高速化など、さまざまな社会課題の解決に取り組むとともに、計算手法自体のさらなる改善も進めていくとしている。