• QUBO問題の解を効率的に探索するABS2 QUBOソルバーを利用するためのC++プログラミング言語用APIを開発しました。
• このAPIを通じて、ユーザーはC++プログラムからABS2のGPUエンジンにアクセスでき、GPUを活用してQUBO問題の解を迅速に探索できます。
• 非商用かつ評価研究目的に限り、ABS2のGPUエンジン実行バイナリとC++APIを無償かつ無保証で公開・提供します。

　広島大学大学院先進理工系科学研究科の中野浩嗣教授らの研究チームは、株式会社NTTデータグループと共同で、組合せ最適化問題の効率よく探索する計算方式｢ABS(Adaptive Bulk Search)｣の開発・改良に取り組んできました。ABSは、複数のGPU(Graphics Processing Unit、＊1)を用いてQUBO(Quadratic Unconstrained Binary Optimization)問題の解を並列探索します。QUBO問題を介した組合せ最適化分野の研究に貢献するため、開発したQUBOソルバーのGPUエンジンの実行バイナリとそれにアクセスするためのC++言語API(Application Programming Interface、＊2)を非商用かつ評価研究目的に限り、無償かつ無保証で提供します。提供するのは、ABSに探索アルゴリズムの動的自動選択機能が追加されたABS2 QUBOソルバーのGPUエンジンです(発表文献[1] を参照)。
　ユーザーは、GPUを搭載した計算機にABS2のGPUエンジンをインストールすることで、C++言語APIを介してQUBO問題の解探索を自由に行えます。組合せ最適化問題をQUBO問題に変換する部分は、ユーザー自身がC++言語を用いて開発します。これにより、C++言語APIを呼び出し、高速な並列解探索を実現できます。さらに、ユーザーはGPUエンジンの各種パラメータを調整したり、コールバック関数を設定することで、解きたいQUBO問題に合わせたABS2のチューニングや他のQUBOソルバーとの連携処理も可能です。

　社会に存在する多くの解決すべき問題は、数多くの選択肢から最適なものを見つける組合せ最適化問題として捉えられます。例えば、最短経路の探索や画像の最適化など、さまざまな組合せ最適化問題を効率的に解くことが要求されています。しかしながら、個々の課題に合わせた専用のソルバーを開発するのは専門知識と莫大な開発コストが必要であり、困難を伴います。一方で、多くの組合せ最適化問題がQUBO問題に変換可能であることが知られています。この性質を利用し、図1のように、解きたい組合せ最適化問題をQUBO問題に変換し、QUBOソルバーで解を見つけ、その解を元の問題の解となるよう逆変換することで、元の問題の解を導き出すことが可能となります。高性能なQUBOソルバーを利用すれば、組合せ問題をQUBO問題に変換する処理と解を元の問題の解に変換する処理のみを開発することで、その組合せ最適化問題の高精度な解を得ることができます。このため、多くの大学や企業でGPUだけでなく、専用の集積回路や量子デバイスを活用したQUBOソルバーが開発され、その性能競争が繰り広げられています。

　QUBO問題は、複数の2値変数に対する2次式を目的関数とし、その関数値を最小化するための0または1への割り当てを求める問題です。例えば、変数a、b、cの2次式f(a, b, c)=2ab-2ac-bc+a-bを目的関数とするQUBO問題では、a=0、b=c=1のとき、f(0,1,1)=-2となり、これが最小値となる最適解です。 
　QUBO問題の応用例として、視覚的にわかりやすいグレースケール画像の2値化処理を題材に説明します(参考文献[2])。グレースケール画像は、ピクセルの2次元配列で表現され、各ピクセルは0(黒)から1(白)までの連続した明るさを持ちます。例えば、0.5は中間の灰色を表します。このグレースケール画像を、0(黒)と1(白)の2値だけを持つピクセルの2次元配列、つまり2値画像に変換するのが2値化処理です。印刷時には、紙の各座標にインクやトナーを｢着ける｣か｢着けない｣か(黒か白か)の2通りしか扱えません。そのため、印刷時には、グレースケール画像を直接印刷可能な2値画像に変換する2値化処理が行われます。2値画像では、元のグレースケール画像のトーンや細部をできるだけ再現することが求められます。また、フルカラー印刷においても、インキCMYKに対応する4つのグレースケール画像ごとに2値化処理が行われます。
　人間の視覚特性により、2値画像を目視した際、網膜にはぼかし処理された画像が投影されます。このため、入力されたグレースケール画像とそのぼかし画像との差が小さいほど、2値画像がより正確にグレースケール画像を再現していると考えられます。このぼかし画像とグレースケール画像の差は、2値画像のピクセル値の2次式として表現することができます。具体的には、グレースケール画像のピクセル値の2次元配列P=(p_i,j)、ぼかしフィルタ係数の2次元配列B=(b_k,l)、2値画像のピクセル値の2次元配列X=(x_i,j)に対して、グレースケール画像とぼかし画像の差を表す目的関数は次の式f(X)で示されます。各ピクセル座標(i,j)における明るさの差の2乗、つまり2乗差の合計がf(X)となります。

　ABS2 QUBOソルバーのGPUエンジンの実行バイナリと、C++言語用のAPIを非商用で評価研究目的に限り無償・無保証で提供します。ユーザーは、GPUを搭載したLinux OSの計算機にABS2 QUBOソルバーをインストールし、C++言語のAPIを利用してGPUを最大限に活用しながらQUBO問題を解くことができます。

さらに、ABS2はコールバック機能(＊3)を用いて他のQUBOソルバーと連携することも可能です。たとえば、商用の数理最適化ソルバーであるGurobi Optimizerは2次の目的関数をサポートしており、QUBO問題を解くことができます。ABS2 GPUエンジンとGurobi Optimizerのコールバック機能を組み合わせることで、両者が探索中に得た良い解を共有し合うことができます。これにより、それぞれのソルバーが持つ長所を生かした解探索が可能となります。
　図2の2値化処理における2乗差の合計f(X)を最小化するQUBO問題を例に説明します。図3では、ABS2ソルバーとGurobi Optimizerそれぞれを単独で使用した場合と、両方を同時に利用した場合の、得られた最良解の時間推移が示されています。ABS2ソルバーを利用すると、探索の過程でf(X)の値がより小さな解Xを発見し、解が徐々に改善されていく様子が見られます。一方で、Gurobi Optimizerを使用すると、比較的良い解が十数秒で得られますが、約960秒後に少しの改善した解を見つけた後、さらなる良い解を得ることができませんでした。この結果から、このQUBO問題において、短時間での実行ではGurobiの解探索性能が優れている一方で、長時間の解改善においてはABS2ソルバーの方が優れていると言えます。そこで、両方のソルバーを同時に実行し、それぞれのコールバックを利用して得られた解を共有することで、Gurobiが短時間で得た良い解を基にABS2ソルバーが探索を行い、良い解をより効率的に探索できるようになりました。

　ABS2 QUBOソルバーの性能向上を継続的に行うとともに、他のソルバーとの連携や、さまざまな組合せ最適化問題や実アプリケーションへの適用を目指します。

＊1 GPU(Graphics Processing Unit)
　グラフィクス処理のための専用集積回路であるが、汎用計算が可能なように拡張されており、多数のプロセッサコアを用いた並列処理を行うことができるため、現在の多くのスーパーコンピュータに搭載されている。
＊2 API(Application Programming Interface)
　アプリケーションが他のソフトウエアと情報をやり取りするときに外部に提供する機能やデータへのアクセス方法を規定する仕様。
＊3 コールバック機能
　実行中に特定の条件を満たしたときにユーザーの設定した処理を行う機能。

• [1] Diverse Adaptive Bulk Search: A Framework for Solving QUBO Problems on Multiple GPUs. IPDPS Workshops 2023: 314-325
   https://doi.org/10.1109/IPDPSW59300.2023.00060
   
• [2] A benchmark QUBO problem inspired by digital halftoning based on the human visual system. CANDAR 2022: 56-65
  https://doi.org/10.1109/CANDAR57322.2022.00015

ABS2 QUBO Solver: https://abs2.cs.hiroshima-u.ac.jp/