組合せ最適化

特 集Ⓡ

LASOLV

実世界の事象をデータ化しながら活用するフィジタルデータセントリックコンピューティング

非ノイマン型計算機

イジング型計算機による組合せ最適化のためのハイブリッド計算基盤
LASOLV®はNTTが研究開発に取り組む，新しい原理に基づいた計算装置です．LASOLV®は組合せ最適化問題を極めて高速に解くことが可能であるため，これまでは解くことができなかった課題の解決が期待されています．一方で実世界の問題をLASOLV®で解くためには，LASOLV®が受け付ける形式への問題変換や，従来からあるデジタル計算機との連携などの課題があります．本稿では，このような課題の解決手段を幅広いユーザに提供し，LASOLV®の効果的な利用を可能にするLASOLV®計算システムを紹介します．

あ ら いじゅんやと み た

き ん や

ほりかわ

け い た ろ うや

新井 淳也

ぎ

さ と し

富田 均也

みはやら

かずひろ/八木 哲志/宮原 和大うちやまひろゆき

ともえと く ま/内山 寛之/巴徳瑪

堀川 桂太郎NTTソフトウェアイノベーションセンタ

実世界の課題に広く内包されています．

イジング最適化問題，ひいては組合組合せ最適化のさまざまな問題は，せ最適化問題を効率的に解くため，イジングモデルの基底状態探索（イジD-Wave Systemsの量子アニーリング

ムーアの法則の終焉に伴い，計算機ング最適化）問題に変換可能であるこマシンや富士通のデジタルアニーラのの性能を飛躍的に向上させるのは困難とが知られています．イジングモデル

ようにイジング最適化に特化した計算になりつつあります．一方で，私たちとはスピンのネットワークを表現した機が開発されています．本稿ではそのは今日のデジタル計算機を圧倒するよ

統計力学のモデルです（図 1 ）．スピような計算機をイジング型計算機と呼うな複雑な問題に依然として直面してンσi はアップ（＋ 1 ）またはダウン（−称します．NTTもまたNTT物性科学

います．組合せ最適化問題はそのよう1 ）のいずれかの状態をとります．Jij

基礎研究所において光を用いたイジンな問題の 1 つです．基礎的な組合せ最とhi がそれぞれスピン間相互作用と磁グ型計算機であるLASOLV®の研究開適化問題としては，指定された複数の場の強さを表すとすると，基底状態と発を行っています（図 2 ）．これらの都市をもっとも効率的にめぐる訪問順は次式で定義されるイジングハミルト

計算機の機能は限られた規模のイジンを求める問題（巡回セールスマン問題）

ニアンH が最小化された状態を指しまグ最適化問題を解くことのみですが，や，限られた色数で隣り合う領域が異す．基底状態を満たすスピンの組合せイジング型計算機とデジタル計算機をなる色になるように塗り分ける問題が，基底状態探索問題の解となります．

協調的に利用するハイブリッドアルゴ

ΣJ σ σ −Σh σ .

リズムの使用により複雑な問題も解く

イジング型計算機の利用における課題（グラフ彩色問題）が有名です．
これらの応用の一例としては無線通H ＝−i<jijijiii

ことができます．例えば，大規模なイ

信の品質改善があります．複数の無線アクセスポイントをイベント会場に配置する際，近傍のアクセスポイントがスピン互いに同じ周波数帯を使用していると，電波の干渉により通信が不安定に相互作用なります．ここでグラフ彩色問題を応用することで，近傍のアクセスポイン磁場トがそれぞれ異なる周波数帯となるよ
うな割り当て方を求めることができま

σi ∈｛−1, ＋1｝

図1

Jijhi

イジングモデル

す．このように，組合せ最適化問題はNTT技術ジャーナル 2019.1127

実世界の事象をデータ化しながら活用するフィジタルデータセントリックコンピューティング

ジング最適化問題を解くため，デジタ

グ ラ ム か らWeb API（Application開発に取り組んでいます．本稿ではまル計算機上で小規模な部分問題に分解

Programming Interface）リクエストず，イジング計算プラットフォームにしたうえで，個々の部分問題をイジンを発行することでイジング最適化をそ求められる設計上のポイントを整理

グ型計算機で解くという処理を繰り返のプラットフォームに任せる（オフし，さらにそれらの要求に対する回答す発見的手法が存在します．
そのため，ロードする）ことができます．ところ

として私たちのプラットフォームである

イジング型計算機は実世界の問題に幅が，イジング型計算機は 1 ミリ秒オー

L C S（ L A S O L V ® C o m p u t i n g

広く適用可能です．

ダーの時間で問題を解くため，相対的System：LASOLV®計算システム）を

しかし，イジング型計算機の利用ににインターネット経由の通信はあまり紹介します．LCSの大きな特徴は，利あたってはいくつかの課題がありまにも低速です．特に，ハイブリッドア用者によって定義されたハイブリッドす．例えば，コストや設置場所の問題

ルゴリズムはイジング型計算機とデジアルゴリズムをLASOLV®と併置されで多数のイジング型計算機を用意するタル計算機の間で頻繁に情報をやり取たデジタル計算機上で実行することでことは困難であるため，複数人で少数りするため，通信コストによる性能低す．これによりLASOLV®とデジタルのイジング型計算機を共用する仕組み下が顕著になります．このように，イ計算機の間で効率的な通信が可能となが必要です．
そこでいくつかの企業は，ジング型計算機の利用には依然としてります．さらに，LCSは幅広いユークラウドプラットフォーム上のリモー課題があります．

スケースにおいてイジング最適化問題

トな計算資源としてイジング型計算機（1）（，2）を提供しています．プラット

これらの課題を解決すべく，NTTへの変換を容易にするライブラリを備

ソフトウェアイノベーションセンタでえています．以降ではこれらについて®

フォームの利用者は手元のデジタル計は，LASOLV を簡単かつ効率的に利算機でプログラムを実行し，そのプロ用するためのプラットフォームの研究詳しく説明します．
なお，LASOLV®は以前「量子ニューラルネットワーク」と呼ばれていました．紙面の都合でLASOLV®自体については説明しませんので，詳しくは過去の特集記事（3）を参照ください．

プラットフォーム設計における要求
次にイジング計算プラットフォームに求められる設計上の観点を 3 つ取り上げて説明します．

■効 率 性
前述したように，インターネット経由の通信はイジング最適化と比較して桁違いに長い時間を要します．
さらに，技術の進歩に伴いイジング型計算機が対応するスピン数は増加します．例え
図2LASOLV 外観ⓇばLASOLV®は 現 状 で 最 大2000ス ピンに対応していますが，NTT物性科

28

NTT技術ジャーナル 2019.11

特 集

学基礎研究所ではこれを10万スピン最適化問題へ変換する作業は特殊な技

効 率 的 な 通 信 を 可 能 に す る た め，まで増加させることをめざしていま能を要します．一方で，変換の方法はLASOLV®とデジタル計算機はLCSす．その結果，イジング最適化問題のあまりにも多様であるため，それぞれにおいて 1 つのクラスタに統合されて規模，すなわち Jij とhi のサイズはますの組合せ最適化問題に対応する変換アいます（図 3 ）．LASOLV®が含まれます増大し，通信効率が性能により大ルゴリズムの提供は非現実的です．幅る こ と を 除 け ば，HPC（High-きな影響を及ぼすようになります．し広い利用目的において高い生産性を実Performance Computing：高性能計算）たがって，プラットフォームは通信の現する，利便性と汎用性を兼ね備えた分野において標準的なクラスタの構成オーバーヘッドが最小化されるようにプログラミングインタフェースが求めです．利用者はSSH接続によるコマンド設計されなければなりません．

られます．

操 作，ま た は ブ ラウ ザ 上 のJupyter■拡 張 性LASOLVⓇ計算システム

イジング型計算機は進化の途上にあります．そのため，新しい世代のハーNTTソフトウェアイノベーション®

Notebookからプログラムの実行をジョブと＊して投入することができます（図4）．ジョブスケジューラとライブラリの協調に

ドウェアは従来と異なる仕様を持つ可センタでは，LASOLV のための計算より，プログラムのうちデジタル計算能性があり，必然的にプラットフォープラットフォームとしてLCSの開発機を使用する部分は計算ノードで実行

ムはヘテロジニアス（異種混在）な計に取り組んでいます．具体的には，され，イジング最適化はLASOLV®に算資源を含むことになります．計算資

LCSは独自のPythonライブラリ，おオフロードされます（図 5 ）．計算ノー

源の使い分けは利用の複雑さを増加さ

よびジョブスケジューラなどのミドルドとLASOLV®の間の通信はクラスタせるため，これらの資源を効果的かつウェアを備えた計算機クラスタです．

内に閉じるため，インターネットに比利用しやすい形態で提供する工夫が必

前述した設計上の要求を満たすため，べて広帯域 ・ 低遅延の通信が可能です．

要です．

LCSは次の 3 つの特徴を持ちます．

また，CPUコアおよびLASOLV®を■生 産 性■LASOLVⓇとデジタル計算機の統合

複数のジョブが同時に使用することが®

各種の組合せ最適化問題をイジング

LASOLV とデジタル計算機の間のないように実行されるため，複数ユーザの同時使用が可能です．

■グループディスパッチ
インターネット

LCSはスケールアウト可能な設計ストレージノードとなっています．今後異なる仕様を持つLASOLV®が登場し得ることから，それらを管理しやすくするためLCS
は互換性のあるLASOLV®をグループとして管理します．利用者はイジング

ログインノード

計算ノード

ジョブスケジューラ経由でプログラムを実行

図3LASOLV
グループ A

イジング最適化をオフロード

LCSの構成ⓇLASOLV
グループ BⓇ

最適化のオフロード先をグループ単位で指定することが可能です（図 5 ）．
ジョブスケジューラはそのグループ内＊ 現時点ではNotebook全体が一括でジョブ実行されます．今後の改良でインタラクティブな実行もサポートする予定です．

NTT技術ジャーナル 2019.11

29

実世界の事象をデータ化しながら活用するフィジタルデータセントリックコンピューティング

で処理を振り分けることにより負荷を分散し，効果的にLASOLV®を使用します．なお，与えられたイジング最適化問題の性質（スピン数など）に基づいて必要な仕様を満たすグループを自動的に決定する機能も将来的に実装される予定です．

■階層的な問題変換
利用者は次の 3 層からなるプログ
ラミングインタフェースを用途に応じて使い分けることができます．
① ソルバ層：巡回セールスマン問
題やグラフ彩色問題のような広く知られたNP困難問題を多項式，またはイジング最適化問題として表現された目的関数へ変換するアルゴリズム群② 多項式層：多項式として表現された目的関数をイジング最適化問
図4

題 へ 変 換 す る た め の 内 部DSL

Jupyter Notebookの利用イメージ（domain-specific language：ドメイン特化言語）③ ハミルトニアン層：イジング最利用者のプログラム

ライブラリ
ミドルウェア

ソルバ層

計算資源

多項式層

適化問題（ Jijとhi ）を直接入力する生のインタフェース
この 3 段階は，手でイジング最適化問題へ変換する場合において一般的なプロセスに対応しています．
すなわち，ハミルトニアン層
LASOLV アダプタⓇ

イジング最適化をオフロード

ジョブスケジューラ化問題への変換，イジングハミルトニアンへの変形です．多項式層は解こうとする問題にソルバ層の実装が適さな計算ノード

図5

形式的な問題定義，多項式関数の最小LASOLVⓇLCSスタック

かった場合や，手動でチューニングを行うための柔軟性が必要となる場合に有用です．例として，グラフG に含まれるn 個の頂点を，隣接頂点がそれぞ

30

NTT技術ジャーナル 2019.11

特 集f = su m ( A ( u , v ) * s u m ( x ( u , i ) * x ( v , i ) f or i i n r a n g e ( c ) )for u, v in combinations(range(n), 2))+ p * s u m ( ( s u m ( x ( v , i ) f o r i i n r a n ge ( c ) ) ‑ 1 ) * * 2for v in range(n))
so l u t i o n = P o l y n o m i a l M e t a s o l v e r ( f ) . s o l ve ( )図6多項式層のサンプルコードれ異なる色になるように c 色で塗り分し，LCSライブラリのハミルトニアけるグラフ彩色問題を考えます．A をン層に直接入力することで問題を解く

G の隣接行列，p をハイパーパラメーという使い方も容易に実現できます．

タとし，変数 xv , i ∈{ 0, 1 }を用いると，したがって利用者の自由を制限するこ

グラフ彩色問題は次式の最小化問題にとはありません．また逆にLCSライ（4）ブラリの機能の多くは汎用性があるの変換されます ．

Σ A Σ x x ＋pΣ f Σ x −1p.

で，イジング最適化問題への変換結果

この式を展開すると変数 xv, i に関す機の入力として使用することも可能

f ＝（x）

ncu<vu,v

i=1u,i v,iv=12ci=1v,iる多項式が導出されますが，多項式層のDSLを用いるとPythonプログラマにとって直感的な記述でこの問題を解くことができます（図 6 ）．

をLASOLV®以外のイジング型計算です．

今後の展開
本稿ではまずプラットフォームの設

ま た， ハ ミ ル ト ニ ア ン 層 は計における要求事項を整理し，さらにLASOLV®が対応するスピン数を超えLCSがそれらをどのように達成したて大規模なイジング最適化問題を解くかを紹介しました．

ためのハイブリッドアルゴリズムを搭

現在，LCSは各種機能を兼務する載しています．これはいくつかの既存ハイエンドサーバ 2 台とLASOLV® 1

手法を基に新しく開発された発見的手台を中心とするスモールスタートの構法です．このような研究開発の成果を成で共同研究者に提供されています．

素早く利用者に届けるために私たちはLASOLV®を用いた研究開発を推進す独自のライブラリを開発しており，るため，私たちは利用状況とフィード

ユーザはこのライブラリで動作するプ

バックに基づくLCSの評価と改良をログラムを実装するだけで成果を利用継続的に実施していきます．

可能です．
なお，他のイジング計算ライブラ（5）～（8）リ（3） 武居 ・ 稲垣 ・ 稲葉 ・ 本庄：“複雑な組合せ最適化問題を解く量子ニューラルネットワー
ク，” NTT技 術 ジ ャ ー ナ ル，Vol.29，No.5，pp.11-14，2017．
（4） A．Lucas：“Ising formulations of many NP
problems，” Frontiers in Physics，Vol.2，No.5，pp.1–15，2014．
（5） https://github.com/Blueqat/Wildqat/（6） https://ocean.dwavesys.com/（7） https://github.com/OpenJij/（8） https://github.com/recruit-communications/pyqubo/でイジング最適化問題へ変換■参考文献（1） https://cloud.dwavesys.com/leap/（2） https://www.fujitsu.com/global/digitalannealer/services/（後列左から） 富田 均也/ 巴徳瑪/

新井 淳也/ 内山 寛之（前列左から） 八木 哲志/ 堀川 桂太郎/
宮原 和大
CPUとGPUの 併 用 と 同 じ よ う に，LASOLVⓇ のような新原理に基づく計算機と従来型のデジタル計算機という視点でも適材適所の併用が重要になりつつあります．
そのような研究の一助となるよう，引き続きLCSの改良に取り組みます．

◆問い合わせ先NTTソフトウェアイノベーションセンタ
分散処理基盤技術プロジェクト
TEL 0422-59-6011
FAX 0422-59-3739
E-mail sic-lasolv-p-ml hco.ntt.co.jp

NTT技術ジャーナル 2019.1131