[市場動向]

NTTデータ、GPUで組み合わせ最適化問題を高速に解く「アダプティブ・バルク・サーチ」を開発

2020年8月17日(月)日川 佳三(IT Leaders編集部)

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

 NTTデータが広島大学と共同で開発した「アダプティブ・バルク・サーチ」は、組み合わせ最適化問題の解を高速に探索する新しい計算方式である。複数のアルゴリズムを用いる大量の解から、コストが最小となる最適解を、GPUを用いて並列に探索する仕組み(図1)。

図1:アダプティブ・バルク・サーチの動作イメージ(出典:NTTデータ)図1:アダプティブ・バルク・サーチの動作イメージ(出典:NTTデータ)
拡大画像表示

 NVIDIA製GPUを4基搭載したサーバーを使って、1秒間に1兆を超える解を探索できる。実験では、最大カット問題、巡回セールスマン問題、ランダム問題、――の各問題において高速性を示した。より大規模な計算機システムやスーパーコンピュータを用いれば、台数に比例して計算速度を高められる。

 探索手法は、柔軟に変化させられる。これにより、各種の組み合わせ最適化問題を解ける。現状では、3万2768変数(15ビット)のQUBO(2次無制約2値最適化、2次形式で表現でき、各変数が0か1を取る無制約最適化)問題まで扱える。

 NTTデータでは、2019年1月から量子コンピュータ/次世代アーキテクチャ・ラボのサービスを開始し、各種分野における量子コンピュータをはじめとする次世代アーキテクチャの適用検証を進めてきた。今回発表した新解法は、これらの活動から見えた適用事例や評価方法および現状の課題をNTTデータが示し、広島大学の専門性によって解決したものである。

関連キーワード

NTTデータ / 広島大学 / 組み合わせ最適化問題

関連記事

トピックス

[Sponsored]

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

PAGE TOP