NTTデータと広島大学、組合せ最適化問題の高速計算方式を開発
NTTデータ（以下、NTTデータ）は、広島大学大学院先進理工系科学研究科（以下、広島大学）の中野浩嗣教授らの研究チームと共同で、組合せ最適化問題の解を高速に探索する新しい計算方式「アダプティブ・バルク・サーチ」を開発したと発表した。
近年、量子アニーリングやGPU・FPGAを用いて、組合せ最適化問題を高速に解くアーキテクチャーの研究開発が活発に行われている。
組合せ最適化問題はさまざまな分野の問題を表現することができるため、問題を高速に計算することが可能になると、多くの社会課題の解決につながるという。
こうした新たなアーキテクチャーに対する取り組みは、さまざまな組合せ最適化問題をQUBO問題という統一的な問題に帰着させて、QUBO問題を高速に解くことを目的としている。
今回、公開するアダプティブ・バルク・サーチは、「さまざまなQUBO問題に柔軟に対応」し、「大規模計算システムの利用により台数に比例した計算速度の向上が可能」という特長を備えている。
この特長により、柔軟性と拡張性を兼ね備えた計算が可能となり、特定の問題を一定の速度で解くことにとどまらず、同技術領域の可能性を大きく拡張できるものと考えているとのことだ。
この解法は以下のような特長を備えているという。
- 探索手法を柔軟に変化させることで、さまざまなQUBO問題に対応することが可能。
- より大規模な計算機システムやスーパーコンピューターを用いることで台数に比例した計算速度のスピードアップが可能。
- GPUのアーキテクチャーの特性を考慮した解の探索手法を設計し、最新のNVIDIA社製GPUを4基搭載した計算サーバーで1秒間に1兆を超える解を探索する計算速度を達成。
実験では、最大カット問題、巡回セールスマン問題、ランダム問題に対する「アダプティブ・バルク・サーチ」の高速性を示しているという。また、現状では、32,768変数のQUBO問題まで扱うことが可能とのことだ。
同社では、同解法を活用し、流通、金融、製造分野における諸問題ならびにAI・機械学習の高性能化に取り組んでいくとしている。。