交通・物流分野等において従来より大規模な順列型組合せ最適化問題を解くための新手法を開発

~モデルサイズの大幅削減等によりイジングマシンや量子アニーラーで解ける問題範囲を拡大~

トピックス

2023年10月13日

株式会社NTTデータグループ

株式会社NTTデータグループ(以下、NTTデータグループ)は国立大学法人広島大学(以下、広島大学)注1と共同で、巡回セールスマン問題注2等の「順列型組合せ最適化問題」を解くために要する順列生成イジングモデル注3のサイズ注4と要求分解能注5を大幅に削減する手法を開発しました。この設計手法は「dual-matrix domain-wall法」注6として特許出願中です(特願2023-125848号「モデル生成装置、モデル生成方法、順列生成システム、およびプログラム」)。
巡回セールスマン問題を例として、無向グラフの頂点数(訪問する都市数)を300とした場合、一般的な「one-hot法」注7に比べてイジングモデルのサイズを25分の1以下に削減できます。本手法の適用により、従来手法ではイジングモデルのサイズが大きく、イジングマシン注8や量子アニーラー注9に投入できなかったような最適化問題も解くことができるようになります。
巡回セールスマン問題など、無駄を最小にし、価値を最大化する最適化問題は、物流、製造、金融、化学などの分野での活用が期待されているだけでなく、サステナブル社会の実現に寄与できる技術です。イノベーションセンタ注10の量子コンピュータ/次世代アーキテクチャ・ラボ注11では、これらを実ビジネスへ活用する検討を実施しています。本手法の開発により、応用分野の開拓がより進むと考えています。

背景

昨今、持続可能な社会の実現が世界共通の認識課題となっています。NTTデータグループにおいても新中期経営計画で「Realizing a Sustainable Future」を掲げ、サステナブル社会の実現を目指しています。持続性を実現するうえで、消費するリソースやエネルギーの無駄を最小化しながら価値を最大化することは、重要な要素の一つです。例えば社会課題の一つとされている物流の2024年問題において、最適な人員配置、最適なルートによる最短時間での配送を実現することは労働環境の改善や温室効果ガス排出量の削減などにつながります。
こうした社会情勢やコンピューティング技術の進歩を背景に、いわゆる「最適化問題」への取り組みが再び注目を集めています。例えば、量子アニーラーと呼ぶ組合せ最適化問題に特化した量子コンピューターが登場し、年々性能を向上させています。しかし、実ビジネスへ応用するには要求性能と実性能にまだ差があることも事実です。
NTTデータグループと広島大学はこうした課題をソフトウエア面で解決する観点から、順列生成イジングモデルのサイズと要求解像度を大幅に削減する「dual-matrix domain-wall法」を開発しました。同じハードウエアでも、より大規模な最適化問題に適用できるようになります。
NTTデータグループは、2023年4月に当社イノベーションセンタによる先進技術導入支援サービス注12においてコンサルティングサービスの提供を開始しています。今回の取り組みは、その一環として実施している広島大学との共同研究成果になります注13

成果概要

順列型組合せ最適化問題は、n!通りある順列の中から最適なものを選ぶ問題で、その代表格が巡回セールスマン問題です。必要とされる範囲は幅広く、例えば製造工程のスケジューリング最適化など、数多くの業務へ応用が可能です。しかし、n!通りの膨大な組合せの中から最適なものを見つけることは容易ではなく、膨⼤な計算時間を要します。
このような順列型組合せ最適化問題を量子アニーラーで解く場合、順列をイジングモデルとして表現する必要があります。同じ順列であっても、その表現方法により、イジングモデルのサイズと要求分解能が異なります。量⼦アニーラーの規模と計算精度には制限があるため、大規模な順列型組合せ最適化問題を解くには、イジングモデルのサイズと要求分解能をハードウエア仕様の制約以下まで小さくする必要があります。
今回開発したdual-matrix domain-wall法では、順列の表現に必要な変数の数は約3倍になりますが、順列生成イジングモデルのサイズをone-hot法の「n3」のオーダーから「n2」のオーダーへ、要求分解能も「n」のオーダーから「定数」へ大幅に削減できます。
効果を定量的に示すために、すべての頂点を一度ずつ訪問する巡回セールスマン問題の無向グラフの頂点数(訪問する都市数)を40/100/200/300と順次増やしてイジングモデルのサイズを計算したところ、グラフの頂点数が多くなるとともに従来のone-hot法ではサイズが急激に増加しますが、今回開発したdual-matrix domain-wall法は、頂点数の増加にともなうサイズの増加が緩やかであり、無向グラフの頂点数が300のときは、従来のone-hot法に比べて25分の1以下に削減できました。

図:無向グラフの巡回セールスマン問題を解くイジングモデルの二次項の個数

図:無向グラフの巡回セールスマン問題を解くイジングモデルの二次項の個数

今後について

NTTデータグループでは、本手法に限らず、量子アニーラーや組合せ最適化問題に対するさまざまな新手法の開発・適用を進めていきます。今後、グローバルにおいて量子コンピュータ/次世代アーキテクチャ・ラボのサービスを展開し、新たな手法によるお客さまの業務改善案件で、2026年までに100件以上の受注を目指します。

注釈

  • 注1 広島大学大学院先進理工系科学研究科コンピューターシステム研究室 中野浩嗣教授
  • 注2 複数の都市が入力として与えられて、それらをすべて⼀度ずつ巡る訪問順で総巡回路⻑が最短のものを求める組合せ最適化問題。
  • 注3 順列生成イジングモデルの定義については、以下を参照ください。
    https://www.hiroshima-u.ac.jp/news/78491
  • 注4 イジングモデルにおける二次項の個数。変数を頂点、二次項を辺としたグラフの辺の個数。
  • 注5 整数係数に限定したイジングモデルにおいての係数の最⼤絶対値。
  • 注6 順列生成イジングモデルの二次項の数と係数の最大絶対値を大幅に削減する新しい順列符号化技術。
  • 注7 one-hot法の定義については、注3の広島大学のニュースリリースを参照ください。
  • 注8 イジングモデルを近似的に解くことに特化したコンピューター。
  • 注9 量子効果に基づいて、特定のグラフ形状をもつイジングモデルの解を求める量⼦コンピューター。
  • 注10 NTTデータグループは、中期経営計画において掲げる技術戦略において、技術の成熟度に応じたEmerging、Growth、Mainstreamの3つの領域における活動を推進しています。2022年8月に設立したイノベーションセンタはEmerging領域の活動であり、量子コンピューター、メタバースなど5~10年先に主流となる先進技術を見極め、お客さまとの共創R&Dを通し新たなビジネス創出に取り組んでいます。大学やスタートアップとも連携することで、各国で先行する技術情報をいち早く収集し世界トップクラスの先進技術活用力の獲得をめざします。
    参考:グローバル6カ国に「イノベーションセンタ」を設立
    https://www.nttdata.com/global/ja/news/release/2022/081900/
  • 注11 量子コンピュータ/次世代アーキテクチャ・ラボのサービス開始
    https://www.nttdata.com/global/ja/news/release/2019/012501/
  • 注12 ブロックチェーン・デジタルツイン・量子アニーリングの導入支援サービスを提供開始 ~イノベーションセンタに事業規模拡大を担うグローバルラボを設置~
    https://www.nttdata.com/global/ja/news/release/2023/042101/
  • 注13 共同研究成果詳細については、注3の広島大学のニュースリリースをご覧ください。

参考発表

広島大学とのこれまでの取り組みに関する発表。
数理最適化によるプリント基板加工の生産効率改善の実現
組合せ最適化問題の計算手法「アダプティブ・バルク・サーチ」の実行環境を無償公開
GPUの計算性能を最大限活用する組合せ最適化問題の新解法を公開

本件に関するお問い合わせ先

株式会社NTTデータグループ
技術開発本部
イノベーションセンタ
矢実、加藤、矢野
E-mail:qcomputer@kits.nttdata.co.jp
TEL:050-5547-0568