量子アニーリングやGPU／FPGAを用いて、組合せ最適化問題を高速に解くアーキテクチャーに注目が集まっています。組合せ最適化問題という言葉は、あまり聞きなれないかもしれませんが、金融、交通、物流、製造、素材開発など様々な分野の裏に潜んでおり、高速化が困難な問題として知られています。そのため、この組合せ最適化の高速計算手法を開発することは、大きな技術革新につながります。 このような背景を受けて、NTTデータと広島大学は「アダプティブ・バルク・サーチ」という手法を公開しました。本稿では、「アダプティブ・バルク・サーチ」に関する3つの特徴を、わかりやすく説明します。
図1：「アダプティブ・バルク・サーチ」の動作イメージ
1秒間に1兆を超える解探索速度
効率的な探索アルゴリズム
どんなに高速な探索速度を実現しても、同じ解を何度も探索したり、最適な解が無さそうな範囲ばかり探索したりしていては、良い解は得られません。「アダプティブ・バルク・サーチ」では、ホストCPUによるグローバルサーチ（俯瞰した視点での探索）と、GPUによるローカルサーチ（より良い解が暫定解の近くにないかつぶさに探索）を組み合わせることで、探索速度を最大限に活かした効率的な求解処理を実現しています。
さらなる計算速度向上を想定した設計
業務要件によっては、非常に複雑な組合せ最適化問題を解く必要があり、先述した1秒間に1兆を超える探索速度でも不十分な可能性があります。「アダプティブ・バルク・サーチ」は、このような厳しい性能要件への対応も考慮して、GPU台数に比例した計算速度の向上が可能な設計となっています。
「アダプティブ・バルク・サーチ」の具体的な評価結果については、論文（※4）で公開しており、最大カット問題、巡回セールスマン問題、ランダム問題に対する高速性を定量的に確認することができます。
最後に
NTTデータでは、今回得られた研究結果を基に、流通、金融、製造分野などの諸問題や、AI・機械学習の高性能化に取り組んでいきます。また、これまで解くことが困難であった問題を効率的に解くことで、エネルギー利用の効率化やスマートな物流網などの、社会課題解決に向けた適用可能性を拡大するとともに、広島大学と共同で本手法のさらなる改善に取り組んでいきます。
（※1）「GPUの計算性能を最大限活用する組合せ最適化問題の新解法を公開」
（※2）NVIDIA GeForce RTX 2080 Ti GPU
（※3）現状の構成では、32,768変数の問題まで扱うことができます。
