JP7461482B2

JP7461482B2 - 割当問題を解くことを支援する情報処理システム及び方法

Info

Publication number: JP7461482B2
Application number: JP2022542566A
Authority: JP
Inventors: 晶子加藤; 地尋吉村; 拓哉奥山
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2020-08-14
Filing date: 2020-08-14
Publication date: 2024-04-03
Anticipated expiration: 2040-08-14
Also published as: AU2020462915A1; JPWO2022034687A1; WO2022034687A1; AU2020462915B2

Description

本発明は、概して、割当問題を解くことを支援する技術に関する。

複数の割当対象を複数の割当先へと割当る割当問題の一つとして、資源割当問題がある。特許文献１は、資源割当問題を表現する方法と解く方法を開示する。

特開2002-133052号公報

汎用コンピュータを用いて割当問題の数理モデルを解くこと、すなわち、全通りの割当の評価をすることが考えられる。しかし、割当対象の数、割当先の数、及び、割当先の許容量（一つの割当先に割当可能な割当対象の数の上限）の少なくとも一つの要素によって、演算量が膨大となり、結果として、現実的な時間内に割当問題を解くことができないことがある。

そこで、全通りの割当の評価を避け現実的な時間内に最適解を得るために、割当問題の数理モデルをアニーリングマシン向けに相互作用モデル（典型的には、イジングモデルのようなアニーリング処理モデル）に変換し、当該相互作用モデルの演算をアニーリングマシンにより行うことが検討される。最適解を得るためには、アニーリングマシン向けの相互作用モデルを最適化する必要がある。

システムが、割当対象の数α（αは自然数）を表す情報割当対象数情報と、割当先の数β（βは自然数）を表す割当先数情報と、一つの割当先に割り当て可能な割当対象の数の上限である許容数Ｌ（Ｌは自然数）とを受け付ける。システムが、αの割当対象をβの割当先に割り当てる割当問題の数理モデルの次数に該当しＬに従うＭ（Ｍは自然数）が所定値以下か否かの判定である次数判定を行う。システムが、次数判定の結果と、α及びβとを基に、相互作用モデルを演算することで割当問題を解くためのアクセラレータであるアニーリングマシン向けの相互作用モデルを決定する。システムが、決定された相互作用モデルを提供する。

本発明によれば、アニーリングマシン向けの相互作用モデルを最適化することができる。

実施形態に係る情報処理システムの構成例を示す。処理支援部の構成例を示す。詳細情報に含まれ得る情報であって割当対象と割当先間の関係性を表す情報の一例を示す。詳細情報に含まれ得る情報であって割当対象間の関係性を表す情報の一例を示す。情報処理システムが行う処理の流れの一例を示す。入力ＵＩの一例を示す。出力ＵＩの一例を示す。

以下の説明では、「インターフェース装置」は、一つ以上のインターフェースデバイスでよい。当該一つ以上のインターフェースデバイスは、下記のうちの少なくとも一つでよい。
・一つ以上のＩ／Ｏ（Input/Output）インターフェースデバイス。Ｉ／Ｏ（Input/Output）インターフェースデバイスは、Ｉ／Ｏデバイスと遠隔の表示用計算機とのうちの少なくとも一つに対するインターフェースデバイスである。表示用計算機に対するＩ／Ｏインターフェースデバイスは、通信インターフェースデバイスでよい。少なくとも一つのＩ／Ｏデバイスは、ユーザインターフェースデバイス、例えば、キーボード及びポインティングデバイスのような入力デバイスと、表示デバイスのような出力デバイスとのうちのいずれでもよい。
・一つ以上の通信インターフェースデバイス。一つ以上の通信インターフェースデバイスは、一つ以上の同種の通信インターフェースデバイス（例えば一つ以上のＮＩＣ（Network Interface Card））であってもよいし二つ以上の異種の通信インターフェースデバイス（例えばＮＩＣとＨＢＡ（Host Bus Adapter））であってもよい。

また、以下の説明では、「メモリ」は、一つ以上の記憶デバイスの一例である一つ以上のメモリデバイスであり、典型的には主記憶デバイスでよい。メモリにおける少なくとも一つのメモリデバイスは、揮発性メモリデバイスであってもよいし不揮発性メモリデバイスであってもよい。

また、以下の説明では、「永続記憶装置」は、一つ以上の記憶デバイスの一例である一つ以上の永続記憶デバイスでよい。永続記憶デバイスは、典型的には、不揮発性の記憶デバイス（例えば補助記憶デバイス）でよく、具体的には、例えば、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）、ＮＶＭＥ（Non-Volatile Memory Express）ドライブ、又は、ＳＣＭ（Storage Class Memory）でよい。

また、以下の説明では、「記憶装置」は、メモリと永続記憶装置の少なくともメモリでよい。

また、以下の説明では、「プロセッサ」は、一つ以上のプロセッサデバイスでよい。少なくとも一つのプロセッサデバイスは、典型的には、ＣＰＵ（Central Processing Unit）のようなマイクロプロセッサデバイスでよい。

また、以下の説明では、「ｙｙｙ部」の表現にて機能を説明することがあるが、機能は、一つ以上のコンピュータプログラムがプロセッサによって実行されることで実現されてもよいし、一つ以上のハードウェア回路（例えばＦＰＧＡ又はＡＳＩＣ）によって実現されてもよいし、それらの組合せによって実現されてもよい。プログラムがプロセッサによって実行されることで機能が実現される場合、定められた処理が、適宜に記憶装置及び／又はインターフェース装置等を用いながら行われるため、機能はプロセッサの少なくとも一部とされてもよい。機能を主語として説明された処理は、プロセッサあるいはそのプロセッサを有する装置が行う処理としてもよい。プログラムは、プログラムソースからインストールされてもよい。プログラムソースは、例えば、プログラム配布計算機又は計算機が読み取り可能な記録媒体（例えば非一時的な記録媒体）であってもよい。各機能の説明は一例であり、複数の機能が一つの機能にまとめられたり、一つの機能が複数の機能に分割されたりしてもよい。

図１は、実施形態に係る情報処理システムの構成例を示す。

情報処理システム５０は、一つ以上の物理的な計算機を備えた計算機システムでよい。情報処理システム５０は、インターフェース装置１３０、記憶装置１４０、アニーリングマシン１００、及びそれらに接続されたプロセッサ１５０を備える。なお、情報処理システム５０は、一つ以上の物理的な計算機を備えた計算機システムに代えて、他種のシステム、例えば、物理的な計算リソース群（例えば、クラウド基盤）上に実現されたシステム（例えば、クラウドコンピューティングシステム）でもよい。

インターフェース装置１３０を介して、情報処理システム５０に対する情報の入出力が行われる。

アニーリングマシン１００は、並列処理デバイス（並列処理が可能なデバイス）の一例であり、相互作用モデル（典型的には、イジングモデルのようなアニーリング処理モデル）を演算することで割当問題を解くためのアクセラレータである。アニーリングマシン１００は、複数の物理的な又は仮想的なコアを有するＣＰＵ（Central Processing Unit）により実現されてもよいが、典型的には、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field-Programmable Gate Array）又はＧＰＵ（Graphics Processing Unit）のようなハードウェア回路である。アニーリングマシン１００は、例えば、半導体回路（例えばＣＭＯＳ（Complementary Metal Oxide Semiconductor）回路）でイジングモデルの動作を疑似的に再現した半導体コンピュータ（例えばＣＭＯＳアニーリングマシン）でよい。

記憶装置１４０に格納されているコンピュータプログラムをプロセッサ１５０が実行することにより処理支援部１２５が実現される。

情報処理システム５０では、例えば図示の白色矢印の通りの入力及び処理が行われる。すなわち、処理支援部１２５が、割当問題入力情報１６０を受け付け、記憶装置１４０に格納する。割当問題入力情報１６０は、割当対象の数α（αは２以上の整数）を表す情報と、割当先の数β（βは２以上の整数）を表す情報とを含む。処理支援部１２５が、割当問題入力情報１６０を基に、αの割当対象をβの割当先に割り当てる割当問題の数理モデルを、アニーリングマシン１００向けの相互作用モデル（例えば、イジングモデル）に変換する。処理支援部１２５は、相互作用モデルを含む情報でありアニーリングマシン１００への入力情報であるデバイス入力情報１７０を、アニーリングマシン１００に設定する。これにより、アニーリングマシン１００が、デバイス入力情報１７０に基づき、割当問題の最適解を得るための並列処理を実施する。なお、相互作用モデル及び値セットを含んだデバイス入力情報１７０をアニーリングマシン１００に設定することとは、アニーリングマシン１００がアクセス可能な記憶領域（例えばメモリ）にデバイス入力情報１７０を格納することでよい。アニーリングマシン１００は、処理支援部１２５からの明示的な通知を受けることで、又は、当該記憶領域を定期的にアクセスすることで、当該記憶領域に格納されているデバイス入力情報１７０を当該記憶領域から読み込むことができる。

情報処理システム５０では、例えば図示の灰色矢印の通りの出力及び処理が行われる。すなわち、アニーリングマシン１００が、並列処理の結果（すなわち、割当問題の最適解）を表す処理結果情報１８０を処理支援部１２５に返す。処理支援部１２５が、処理結果情報１８０に基づく割当解出力情報１９０を記憶装置１４０に格納する。処理支援部１２５が、割当解出力情報１９０を、出力する。

割当対象になり得る要素も、割当先になり得る要素も、それぞれユーザ任意の要素とすることができる。

図２は、処理支援部１２５の構成例を示す。

処理支援部１２５は、情報処理システム５０の外部に対する入出力のための第１のインターフェース部２０１と、次数判定を行う次数判定部２０２と、デバイス入力情報１７０を決定する入力決定部２０３と、アニーリングマシン１００に対する入出力のための第２のインターフェース部２０４と、割当解出力情報１９０を決定する出力決定部２０５とを有する。入力決定部２０３は、縮約処理を行う縮約部２３１と、モデルコンパイルを行うモデルコンパイル部２３２とを有する。情報処理システム５０の外部としては、サーバ又は可搬型の記憶媒体といった様々な要素を採用可能である。本実施形態では、情報処理システム５０の外部は、ユーザである。

以下、これらの機能の詳細を、処理支援部１２５が行う処理の流れに沿って説明する。ｉ番目の割当対象を「割当対象ｉ」（例えば、ｉ=１，２，…であり、ｉの最大値はα）と表現し、ｊ番目の割当先を「割当先ｊ」（例えば、ｊ=１，２，…であり、ｊの最大値はβ）と表現することができる。

第１のインターフェース部２０１は、割当問題入力情報１６０の入力ＵＩ（User Interface）を提供する。入力ＵＩは、例えばＧＵＩ（Graphical User Interface）である。図６に入力ＵＩ６００が例示される。入力ＵＩ６００を介して、割当問題入力情報１６０が入力される。なお、割当問題入力情報１６０の入力は、入力ＵＩ６００経由の入力に代えて又は加えて他種の入力（例えば、割当問題入力情報１６０の少なくとも一部を含んだファイル（例えばＣＳＶファイル）の入力）でもよい。また、第１のインターフェース部２０１は、割当問題の数理モデルを予め管理してよい。割当問題数理モデルは、本実施形態のように予め処理支援部１２５に設定されていてもよいが（例えば、割当問題数理モデルを表す情報が記憶装置１４０に格納されていてもよいが）、他の方法で処理支援部１２５に入力されてもよい。例えば、割当問題数理モデルを表す情報が、割当問題入力情報１６０に含まれてもよい。

割当問題入力情報１６０は、基本情報（第１の情報の一例）と詳細情報（第２の情報の一例）とのうち少なくとも基本情報を含む。

基本情報は、下記の情報（Ａ）～（Ｃ）を含んだ情報である（一例は図６に示す通り）。下記情報（Ａ）～（Ｃ）について、α及びβは、いずれも自然数であるが、典型的には、２以上の整数でよい。Ｌも、自然数ですが、２以上の整数でよい。つまり、本実施形態では、α、β及びＬの少なくとも一つの値が１である比較的簡単な割当問題を解くこともできるが、α、β及びＬのいずれの値も２以上の整数である比較的複雑な割当問題を解くことに有用である。
（Ａ）割当対象の数αを表す情報。
（Ｂ）割当先の数βを表す情報。
（Ｃ）割当先の許容数Ｌを表す情報。

詳細情報は、割当問題入力情報１６０のうち基本情報以外の情報である。詳細情報のうちの少なくとも一部の情報のユーザ入力（ユーザによる入力）は、オプションでよい。詳細情報のうちユーザ入力されない情報については、デフォルト情報が採用されてよい。例えば、詳細情報が割当対象と割当先とのペア毎に割当対象から割当先への割当コストを表す情報を含むが各ペアについて割当コストを表す情報がユーザ入力されない場合、各ペアについての割当コストとしてデフォルト値（例えば“１”）が一律で採用されてよい。詳細情報は、下記の情報（Ｄ）及び（Ｅ）を含む（一例は図６に示す通り）。なお、情報（Ｄ）及び（Ｅ）のいずれも、後述の（処理Ａ）乃至（処理Ｃ）のうちのいずれの処理が採用されるかによって（どのような縮約処理が行われるかによって）、係数影響情報と係数非影響情報のいずれにも該当し得る。例えば、（処理Ａ）が採用される場合、情報（Ｄ）及び（Ｅ）のいずれも、制約項として採用され得るため、係数影響情報になり得る。一方、（処理Ｂ）及び（処理Ｃ）のいずれかが採用される場合、情報（Ｄ）及び（Ｅ）のいずれも、係数非影響情報になり得る。
（Ｄ）割当先に関する詳細を表す割当先詳細情報（例えば、割当先の許容量ｍ（ｍ＞０）を表す情報）。
（Ｅ）割当対象に関する詳細を表す割当対象詳細情報（例えば、割当対象毎の資源量）。

図６が示す例によれば、割当問題入力情報１６０は、基本情報、割当先詳細情報及び割当対象詳細情報を含む。基本情報が、上述の情報（Ａ）乃至（Ｃ）である。割当先詳細情報が、上述の情報（Ｄ）である。

許容数Ｌは、一つの割当先に割り当て可能な割当対象の数の上限であり、割当問題数理モデルの目的関数項の次数Ｍそれ自体である。許容量ｍは、割当先の種類に応じた種類の値であり割当対象の割り当ての制約に関わる値であり、具体的には、Ｍ次相互作用モデルの制約項、もしくは後述する処理によりアニーリングマシンに入力される際の次数削減後のモデルの制約条件として用いられる。例えば、図６に例示するように、割当対象が仮想ＯＳ（Operating System）であって割当先がサーバの場合、許容数Ｌは、サーバの資源量（例えばメモリ容量）から決定してよい。例えば、各仮想ＯＳが必要とする資源量がｍ＝３０で、サーバの資源量（詳細情報に含まれる）が９０の場合、Ｌ＝３（９０÷３０）でよく、Ｌは次数Ｍと等しい。なお、本実施形態では、許容数Ｌ及び許容量ｍは、全ての割当先に共通であるが、全ての割当先で、許容数Ｌ及び許容量ｍが同じである必要は無い。例えば、許容数Ｌ又は許容量ｍを表す情報が、割当先毎に存在してもよい。この場合、許容量Ｌの最大値が次数Ｍとなる。

詳細情報は、例えば、下記（ｄ１）及び（ｄ２）のうちの少なくとも一つを含む。
（ｄ１）相互作用モデルにおける一つ以上の係数値（一つ以上の割当状態変数の一つ以上の係数値）に影響する情報である係数影響情報。
（ｄ２）相互作用モデルにおける係数値に影響しない情報である係数非影響情報。

「割当状態変数」は、割当対象ｉと割当先ｊとのペア毎に存在し、割当対象ｉの割当先ｊへの割当状態を表す変数である。例えば、割当状態変数の値は、２値と多値のいずれで表現されてもよい。２値が採用される場合、割当状態は、割当対象ｉが割当先ｊに割り当てられているか否か（“１”か“０”）でよい。多値が採用される場合、割当状態として、割当対象ｉが割当先ｊに割り当てられているか否かに加えて他種の状態を表現することができる。

係数影響情報は、例えば、下記（ｘ）及び（ｙ）のうちの少なくとも一方の情報でよい。なお、以下の（ｘ）及び（ｙ）において、「関係性」としては、類似性或いは適切性といった任意の関係性を採用することができる。割当状態変数の係数値としては、例えば、相互作用係数（例えば、Ｃ（σ_ｉｊ×σ_ｉ’ｊ’）におけるＣ）の値、又は、外場係数（１次式における係数、若しくは、Ｄ（σ_ｉｊ×σ_ｉｊ）におけるＤ）の値がある。なお、「σ_ｉｊ」は、割当対象ｉの割当先ｊへの割当状態を表す変数である。「σ_ｉｊ×σ_ｉ’ｊ’」は、割当対象と割当先との組が異なる割当状態同士の積を意味する。「σ_ｉｊ×σ_ｉｊ」は、割当対象と割当先との組が同じ割当状態同士の積を意味する。
（ｘ）割当対象と割当先との間の関係性を表す数値を含んだ情報（例えば、図３が例示する情報）。例えば、割当対象ｉと割当先ｊとの関係性を表す数値の一例として、割当対象ｉが割当先ｊに割り当てられた場合に所与の結果が得られる確率を採用することができる。
（ｙ）割当対象と割当対象間の関係性を表す数値を含んだ情報（例えば、図４が例示する情報）。例えば、割当対象ｉと割当対象（ｉ＋ｕ）間との関係性を表す数値の一例として（ｕ＞０）、割当対象ｉが持つ一つ以上の要素の特徴量と割当対象（ｉ＋ｕ）が持つ一つ以上の要素の特徴量との差を採用することができる。

係数非影響情報は、縮約処理（高次の割当問題数理モデルを低次の割当問題数理モデルに変換する処理）で必要になる情報（例えば、補助スピンの数）であり、具体的には、例えば、高次（次数Ｍ）の割当問題数理モデルの制約条件を表す情報である。係数非影響情報は、以下で説明する縮約処理後では相互作用モデルの中には明示的に入ってこずとも、縮約処理後の割当問題数理モデルにおける係数値を決定するために使用されるメタ情報として活用される。なお、アニーリングマシン１００に読み込まれる段階の相互作用モデル（縮約処理済みの又は縮約処理が不要であった相互作用モデル）についての制約項は、係数影響情報に含まれる情報であるので、本段落における「制約条件」と異なる（区別される）。

第１のインターフェース部２０１が、α及びβを表す情報と割当問題数理モデルとを、モデルコンパイル部２３２に入力し、Ｌを表す情報を次数判定部２０２に入力する。詳細情報（例えば、許容量ｍを含んだ情報）があれば、第１のインターフェース部２０１が、割当問題数理モデルと詳細情報とを縮約部２３１に入力する。

次数判定部２０２は、入力された情報が表すＬに従う次数Ｍ（割当問題数理モデルの目的関数項の次数Ｍ）が所定値以下か否かの判定である次数判定を行う。次数判定の結果に応じて、処理支援部１２５における処理が異なる。次数Ｍと比較される「所定値」は、例えば第１のインターフェース部２０１を介してユーザにより設定された値でよい。

次数Ｍが所定値以下の場合（つまり、次数判定の結果が真の場合）、後述の縮約処理無しに、モデルコンパイルが行われる。すなわち、次数判定部２０２が、モデルコンパイル部２３２にモデルコンパイルを指示する。結果として、次数Ｍが所定値以下の場合、モデルコンパイル部２３２は、モデルコンパイルの指示を、次数判定部２０２から受ける。次数判定部２０２からモデルコンパイルの指示を受けた場合、モデルコンパイル部２３２は、割当問題数理モデルを相互作用モデルに変換する。割当問題数理モデルの一例が、以下の数１～数４であり、相互作用モデルの一例が、以下の数５である。割当問題数理モデルに関し、数１は、目的関数（最小化）であり、数２～数４は、制約条件である。数１～数５において、σ_ｉｊは、割当対象ｉの割当先ｊへの割当状態を表す値である。割当問題数理モデル（例えば数１）では、割当先の負荷が少なくなるように、割当先あたりの割当資源の積を最小化することを想定した。次数Ｍが所定値以下のケースでは、縮約処理が走らないため、次数Ｍの低減は不要であり、故に、次数低減を目的として割当状態変数の数を減らすために割当状態変数の値を２値から多値に変換する必要がない。

次数Ｍが所定値を超えている場合（つまり、次数判定の結果が偽の場合）、縮約処理を経て、モデルコンパイルが行われる。すなわち、次数判定部２０２が、縮約部２３１に縮約処理を指示する。なお、次数Ｍと比較される所定値は、例えば、下記のうちのいずれかでよい。
・アニーリングマシン１０００の設計段階において決定された値であって、次数判定部２０２に定義されている値。
・ユーザ入力（例えば、入力ＵＩ６００経由の入力）がされた値。この値は、アニーリングマシン１００が対処可能な最大次数を上限とした値である。例えば、入力ＵＩ６００が、アニーリングマシン１００が対処可能な最大次数以下の値を次数Ｍと比較される所定値として受け付けるＧＵＩ部品を有してよい。第１のインターフェース部２０１が、入力された所定値を、次数判定部２０２に通知する。
・次数判定部２０２によって次の処理により特定された値。すなわち、次数判定部２０２が、アニーリングマシン１００の属性（例えば、型番やベンダ）をキーに、アニーリングマシンの属性（例えば型番やベンダ）と次数Ｍと比較される所定値との関係を表す情報（例えばテーブル）から、該当の所定値を特定する。

縮約部２３１が、縮約処理の指示を受けて、縮約処理を行う。縮約処理は、割当問題数理モデルの次数Ｍを次数Ｍ´に低減することである。縮約部２３１が、モデルコンパイルをモデルコンパイル部２３２に指示し、縮約処理後の数理モデル（次数低減後の数理モデル）をモデルコンパイル部２３２に入力する。結果として、次数Ｍが所定値を超えている場合、モデルコンパイル部２３２は、モデルコンパイルの指示を、縮約部２３１から受ける。縮約部２３１からモデルコンパイルの指示を受けた場合、モデルコンパイル部２３２は、縮約処理後の数理モデルを相互作用モデルに変換する。なお、Ｍ´の値は、次数Ｍと比較される上述の所定値と同じ値（又は、それよりも小さな値）である。すなわち、当該所定値は、縮約処理後の数理モデルについての次数の上限に相当し、縮約処理により、次数Ｍが、当該上限（又は、それよりも小さな値）にまで低減される。

例えば、縮約処理は、下記（処理Ａ）乃至（処理Ｃ）のうちの少なくとも一つの処理を含む。（処理Ａ）乃至（処理Ｃ）の少なくとも一つにより、次数Ｍが次数Ｍ´に低減される。
（処理Ａ）HOBO（Higher Order Binary Optimization）形式の数理モデルをQUBO（Quadratic Unconstrained Binary Optimization）形式の数理モデルに変換すること。
（処理Ｂ）詳細情報中の係数影響情報（例えば、図３が例示する情報と図４が例示する情報とのうちの少なくとも一方）を基に、相互作用モデルにおける一つ以上の係数値を決定すること。
（処理Ｃ）相互作用モデルにおける割当状態変数の値の表現を２値から多値に変えること。

例えば、縮約処理は、下記でよい。
Ｓ１：縮約部２３１が、（処理Ａ）乃至（処理Ｃ）のうちＳ１においていずれかの未選択の処理を選択し、選択した処理を行う。
Ｓ２：縮約部２３１が、Ｓ１の結果、Ｍ＝Ｍ´になったか否かを判定する。Ｓ２の判定結果が真の場合、処理が終了する。Ｓ２の判定結果が偽の場合、縮約部２３１が、Ｓ１を行う。

なお、採択される処理の優先順位は、例えばアニーリングマシン１００のメモリが十分にある場合、（処理Ｃ）＞（処理Ａ）＞（処理Ｂ）でよい。つまり、（処理Ｃ）が優先的に採択されてよい。すなわち、最初にＳ１で選択される処理は、（処理Ｃ）でよい。理由の一例は、下記の通り通りである。
・（処理Ｃ）の優先順位が１番目である理由は、例えば次の通りである。（処理Ｃ）は、アニーリングマシンのハード依存性が高い（適用可能なマシンの制限が高い）ために適用不可となる可能性も高いが、最もスピン削減効果が高い。
・（処理Ａ）の優先順位が２番目である理由は、例えば次の通りである。４次以上で変換前のスピン数が大きい問題では、精度や変換後のスピン数が急激に悪い方向に振れ得るため、（処理Ａ）は、次数やスピン数を基に採択されるか否かが決まるが、（処理Ａ）は、比較的低負荷で変換可能である。
・（処理Ｂ）の優先順位が３番目である理由は、例えば次の通りである。（処理Ｂ）は、比較的汎用性が高いが、ＣＰＵ上で前処理が必要なため処理に時間がかかり得る。

あるいは、（処理Ａ）乃至（処理Ｃ）の採択される優先順位は、要求スピン数（変換後のモデルのスピン数、つまり、アニーリングマシンのメモリ使用量）が少ない順でよい。すなわち、（処理Ａ）乃至（処理Ｃ）のうち、最初にＳ１で選択される処理は、要求スピン数が最も少なくなる処理でよい。

（処理Ａ）の一例は、次の通りである。すなわち、σ_ｉｊがバイナリ変数であることを利用し、HOBO形式の数理モデル（例えば数１～数４）がQUBO形式の数理モデル（例えば数６～数１１）に変換される。例えばＭ≦４の時に、（処理Ａ）が適用される（Ｍと比較される値“４”は一例であり、比較される値は、“４”に近い値（“４”との差が所定値以下の値）でもよい）。QUBO形式の数理モデルに関し、数６は、目的関数（最小化）であり、数７は、第１の制約条件であり、数８～数１１は、第２の制約条件である。数６～数１１によれば、補助スピンｑ_ｉｊと、QUBOモデルが元のHOBOモデルを再現するためのペナルティ係数νとが導入されている。なお、数６～数１１は一般的な形式で書かれており、QUBO変換後の補助スピン数γやペナルティ係数νは変換方法によって異なる。ペナルティ係数ν及びν´は、第１の制約条件を数６（目的関数）に代入したときに矛盾が生じないように設定される。ペナルティ係数の決定方法は任意性があるためユーザが状況に応じて任意に設定可能である（例えば、入力ＵＩ６００が、ペナルティ係数ν及びν´の入力を受け付けるＧＵＩ部品を有してよい）。数６～数１１が、次数低減後の数理モデルとしてモデルコンパイル部２３２に入力され、相互作用モデル（数１３）に変換される。

（処理Ｂ）の一例は、以下の通りである。

例えば、図３が例示する情報（割当対象と割当先間の関係性を表す情報）を数１～数４での相互作用係数であるとすると、縮約部２３１は、数１～数４でのスピンσ_ｉｊの値のうち数１～数４での制約条件を必ず満たすＮ通り（Ｎは自然数）の組合せを列挙する。縮約部２３１は、Ｎ通りの組合せのうちどの組合せを選択するかを表す数理モデルを、スピンｑ_ｔを変数とする「集合分割問題又は集合被覆問題」の数理モデルに変換する。具体的には、例えば、数１～数４が、数１３～数１５に変換される。数１３～数１５が、次数低減後の数理モデルの一例である。数１３は、目的関数（最小化）であり、数１４～数１５は、制約条件である。数１３～数１５でのσ_ｒ´ｔは、元のモデル（数１～数４）のスピンに対応するものではあるが、変数ではなく定数である。この変換後のモデルでの変数はｑｔである。変数ｑの数Ｎは全組合せのうち、Ｃが閾値より小さいものや、制約を破る組合せとなるｒを排除して残った組合せの数となる。このように、結果として、（処理Ｂ）が次数低減に寄与する。数１３～数１５が、次数低減後の数理モデルとしてモデルコンパイル部２３２に入力され、相互作用モデル（数１６～数１７）に変換される。（処理Ｂ）はＭ＞４の時も有効である。また、以下の例では、補助スピンは、バイナリ値であるが、ハード（アニーリングマシン１００）が対応すれば連続値でもよい。

また、例えば、図４が例示する情報（割当対象間の関係性を表す情報）を数１～数４での相互作用係数であるとすると、数１３～数１５と同様、「集合分割問題又は集合被覆問題」の数理モデルへの変換が行われる。例えば、数１～数４が、数１８～数２０に変換される。数１８～数２０が、次数低減後の数理モデルの式の一例である。数１８は、目的関数（最小化）であり、数１９～数２０は、制約条件である。数１８～数２０の導出方法は数１３～数１５と同様である。このように、結果として、（処理Ｂ）が次数低減に寄与する。数１８～数２０が、次数低減後の数理モデルとしてモデルコンパイル部２３２に入力され、相互作用モデル（数２１～数２２）に変換される。

また、例えば、図３が例示する情報と図４が例示する情報の両方を縮約部２３１が利用することで、例えば数１～数４が数２３～数２５に変換される。数２３～数２５が次数低減後の数理モデルの式の一例である。数２３は、目的関数（最小化）であり、数２４～数２５は、制約条件である。数２３～数２５の導出方法は数１３～数１５と同様である。このように、結果として、（処理Ｂ）が次数低減に寄与する。数２３～数２５が、次数低減後の数理モデルとしてモデルコンパイル部２３２に入力され、相互作用モデル（数２６～数２７）に変換される。

（処理Ｃ）の一例は、次の通りである。すなわち、例えば数１～数４が数２８に変換される。数２８が、数理モデルの次数低減後の式の一例である。ここでは例えば数２３～数２５の数理モデルをベースに、目的関数のスピンアドレスｒ及びｔが変数とされる。変数の定義域が設定されれば、数２３～数２５における制約条件（つまり数２４及び数２５）は不要となる。このように、結果として、（処理Ｃ）が次数低減に寄与する。数２８が、次数低減後の数理モデルとしてモデルコンパイル部２３２に入力され、相互作用モデル（数２９）に変換される。なお、（処理Ｃ）は、スピン値がバイナリ値しか取れないハード上では実行できない。

以上のように、次数判定の結果が真か偽かに応じて、縮約処理が走らないか走るかが決まる。縮約処理を経ないで或いは経て、モデルコンパイルが実施される。つまり、数６～数１１、数１３～１５、数１８～数２０、数２３～数２５、又は数２８のような次数低減後の数理モデルが、それぞれ、数１２、数１６～数１７、数２１～数２２、数２６～数２７、又は数２９のような相互作用モデルに変換される。相互作用モデルは一見それぞれ違う式に見えるが、数理モデルが決定されれば、目的関数と２次式で表した制約項の和としてすべて同一手順で求めることができる。

詳細情報には、図３及び図４が例示する係数影響情報に代えて又は加えて、係数非影響情報が含まれていることがあり得る。係数非影響情報は、縮約部２３１での処理において縮約された相互作用モデルへの変換のために利用される。

例えば、係数非影響情報は、縮約前のモデルにおける制約条件を表す情報を含む。制約条件は、第１のインターフェース部２０１において、割当問題数理モデルに反映され、制約条件が反映された割当問題数理モデルが、第１のインターフェース部２０１から出力される。

また、例えば、係数非影響情報は、Ｋ（Ｋは自然数）を表す情報を含んでよい。Ｋは、一つの割当対象ｉから割り当て可能な割当対象ｉ－ｋ（ｋはＮ以下の自然数）の最大数である。すなわち、一つの割当対象ｉから最大Ｎの割当対象ｉ－ｋが一つ又は複数の割当先に割り当て可能でもよい。この場合、Ｋは、縮約処理において、QUBO形式の数理モデルにおけるスピンやペナルティ項として反映される。

モデルコンパイル部２３２は、相互作用モデルと値セットとを含むデバイス入力情報１７０を出力する。第２のインターフェース部２０４が、当該デバイス入力情報１７０を受けてアニーリングマシン１００へ設定する。相互作用モデルは、モデルコンパイルにより得られたモデルである。値セットは、相互作用モデルの演算に使用される値のセットであり、例えば、相互作用モデルにおける割当状態変数毎に、係数値と、アドレス値とを含む。値セットにおける係数値は、アニーリングマシン１００における図示しない制御回路により、アニーリングマシン１００内（当該係数値に対応したアドレス）にマッピングされる。

アニーリングマシン１００が、相互作用モデルのエネルギー基底状態を求めるための演算を実行することで、割当案（割当対象ｉと割当先ｊとのペア毎の割当状態値）を算出し、割当案を表す情報である処理結果情報１８０を、処理支援部１２５に出力する。なお、この出力は、処理支援部１２５が、相互作用モデル及び値セットのアニーリングマシン１００への設定に対する応答として、受けることができる。処理結果情報１８０から、処理支援部１２５は、最終的なスピン値を知ることができる。

第２のインターフェース部２０４が、アニーリングマシン１００から処理結果情報１８０を受け付け、当該処理結果情報１８０を出力決定部２０５に出力する。出力決定部２０５が、処理結果情報１８０を基に割当解出力情報１９０を生成し、割当解出力情報１９０を第１のインターフェース部２０１に出力する。第１のインターフェース部２０１が、割当解出力情報１９０を、情報処理システム５０の外部（例えばユーザの情報処理端末）に提供する。例えば、図７に示すように、割当解出力情報１９０が表す割当解を表示した出力ＵＩ７００が、提供される。出力ＵＩ７００は、割当解出力情報１９０が表す割当結果（いずれの割当対象がいずれの割当先にどのような割当コストで割り当てられるかを表す結果）を表示する。割当解出力情報１９０の出力は、出力ＵＩ７００経由の出力に代えて又は加えて他種の出力（例えば、割当解出力情報１９０の少なくとも一部を含んだファイル（例えばＣＳＶファイル）の出力）でもよい。

図５は、情報処理システムが行う処理の流れの一例を示す。

Ｓ５０１で、第１のインターフェース部２０１が、割当問題入力情報１６０の入力を受け付ける。第１のインターフェース部２０１が、割当問題入力情報１６０を、記憶装置１４０に格納する。

Ｓ５０２で、次数判定部２０２が、記憶装置１４０における割当問題入力情報１６０のうち次数判定に必要な情報（許容数Ｌを含む情報）を基に、次数Ｍを特定し、次数Ｍが所定値以下か否かを判定する。

Ｓ５０２の判定結果が偽の場合、Ｓ５０３で、縮約部２３１が、上述した縮約処理を行う。

Ｓ５０２の判定結果が真の場合、又は、Ｓ５０３の縮約処理の後、Ｓ５０４で、モデルコンパイル部２３２が、モデルコンパイルを行う。モデルコンパイル前のモデルは、縮約処理後の数理モデル（次数Ｍ´の数理モデル）、又は、縮約処理がされていない数理モデル（次数Ｍの数理モデル）である。モデルコンパイル後のモデルは、相互作用モデルである。モデルコンパイルでは、割当問題入力情報１６０におけるα（割当対象の数）の値とβ（割当先の数）の値も使用される。また、モデルコンパイルでは、割当問題入力情報１６０における詳細情報のうちの少なくとも一部の情報が使用されてよい。モデルコンパイルにより、相互作用モデルについての値セットも得られる。

Ｓ５０５で、モデルコンパイル部２３２が、相互作用モデルと値セットとを含むデバイス入力情報１７０を出力し、第２のインターフェース部２０４が、当該デバイス入力情報１７０を受けてアニーリングマシン１００へ設定する（書き込む）。

Ｓ５０６で、アニーリングマシン１００が、デバイス入力情報１７０を基に並列処理（値セットを用いて相互作用モデルを並列演算すること）を実施する。

Ｓ５０７で、アニーリングマシン１００が、処理結果情報１８０を出力する。

Ｓ５０８で、第２のインターフェース部２０４が、アニーリングマシン１００から処理結果情報１８０を受け付け、当該処理結果情報１８０を出力決定部２０５に出力する。出力決定部２０５が、処理結果情報１８０を基に割当解出力情報１９０を生成し、割当解出力情報１９０を第１のインターフェース部２０１に出力する。第１のインターフェース部２０１が、割当解出力情報１９０を、情報処理システム５０の外部（例えば、ユーザの情報処理端末）に出力する。

以上、一実施形態を説明したが、これは本発明の説明のための例示であって、本発明の範囲をこの実施形態にのみ限定する趣旨ではない。本発明は、他の種々の形態でも実行することが可能である。

例えば、アニーリングマシン１００は、ＡＳＩＣ、ＦＰＧＡ又はＧＰＵといったハードウェア回路に限られないでよい。

また、例えば、相互作用モデルは、ニューラルネットワークやボルツマンマシンでよい。

また、上述した数１～数２９における「制約条件」は、割当問題入力情報１６０における詳細情報のうちの係数非影響情報でよい。

また、例えば、ユーザ入力を受け付けるための複数のＧＵＩ部品は、一つの入力ＵＩ６００に存在してもよいし、複数のＵＩに分散していてもよい（ＧＵＩ部品はＵＩ部品の一例）。また、例えば、割当解出力情報１９０を表すＵＩは、一つの出力ＵＩ７００であってもよいし、複数のＵＩであってもよい。

また、例えば、第２のインターフェース部２０４は、相互作用モデル及び値セットを含んだデバイス入力情報１７０を、アニーリングマシン１００に設定することに代えて又は加えて、情報処理システム５０の外部（例えば、ユーザの情報処理端末）に提供してもよい。

５０：情報処理システム

Claims

割当対象の数α（αは自然数）を表す情報割当対象数情報と、割当先の数β（βは自然数）を表す割当先数情報と、一つの割当先に割り当て可能な割当対象の数の上限である許容数Ｌ（Ｌは自然数）とを受け付ける第１のインターフェース部と、
αの割当対象をβの割当先に割り当てる割当問題の数理モデルの次数に該当しＬに従うＭ（Ｍは自然数）が所定値以下か否かの判定である次数判定を行う次数判定部と、
前記次数判定の結果が偽の場合、Ｍより小さい次数Ｍ´を決定する縮約処理を行い、当該縮約処理において決定された次数Ｍ´での数理モデルと、α及びβとを基に、相互作用モデルを演算することで割当問題を解くためのアクセラレータであるアニーリングマシン向けの相互作用モデルと、当該相互作用モデルの演算に使用される値のセットである値セットを決定する入力決定部と、
前記決定された相互作用モデル及び値セットを提供する第２のインターフェース部と
を備える情報処理システム。
前記第１のインターフェース部は、相互作用モデルにおける一つ以上の割当状態変数の一つ以上の係数値に影響する情報である係数影響情報を更に受け付け、
前記縮約処理は、前記係数影響情報を基に前記一つ以上の係数値を決定することを含む、
請求項１に記載の情報処理システム。
前記係数影響情報は、割当対象と割当先との間の関係性を表す数値を含んだ情報を含む、
請求項２に記載の情報処理システム。
前記係数影響情報は、割当対象と割当対象間の関係性を表す数値を含んだ情報を含む、
請求項２に記載の情報処理システム。
前記縮約処理は、下記（処理Ａ）乃至（処理Ｃ）のうちの少なくとも一つの処理を含み、
（処理Ａ）HOBO（Higher Order Binary Optimization）形式の数理モデルをQUBO（Quadratic Unconstrained Binary Optimization）形式の数理モデルに変換すること、
（処理Ｂ）相互作用モデルにおける一つ以上の割当状態変数の一つ以上の係数値に影響する情報である係数影響情報を基に、相互作用モデルにおける一つ以上の係数値を決定すること、
（処理Ｃ）相互作用モデルにおける割当状態変数の値の表現を２値から多値に変えること、
前記入力決定部は、（処理Ａ）乃至（処理Ｃ）のうち、次数Ｍを次数Ｍ´に低減可能な処理を選択する、
請求項１に記載の情報処理システム。
（処理Ａ）乃至（処理Ｃ）の各々の選択される優先順位は、（処理Ｃ）、（処理Ｂ）及び（処理Ａ）の順に高い、
請求項５に記載の情報処理システム。
（処理Ａ）乃至（処理Ｃ）の各々の選択される優先順位は、変換後のモデルのスピン数でありアニーリングマシンのメモリ使用量である要求スピン数の少ない順に高い、
請求項５に記載の情報処理システム。
前記第１のインターフェース部は、相互作用モデルにおける一つ以上の割当状態変数の一つ以上の係数値に影響しない情報であり前記縮約処理において使用され次数Ｍの数理モデルの制約条件を表す情報である係数非影響情報を更に受け付け、
前記入力決定部は、前記係数非影響情報を利用して前記縮約処理を行う、
請求項１に記載の情報処理システム。
前記アニーリングマシンを更に備え、
前記アニーリングマシンが、前記提供された相互作用モデル及び値セットを読み込み、当該相互作用モデルを、当該値セットを用いて演算することにより、前記割当問題を解き、前記割当問題の最適解を表す処理結果情報を出力する、
請求項１に記載の情報処理システム。
コンピュータが、割当対象の数α（αは自然数）を表す情報割当対象数情報と、割当先の数β（βは自然数）を表す割当先数情報と、一つの割当先に割り当て可能な割当対象の数の上限である許容数Ｌ（Ｌは自然数）とを受け付け、
コンピュータが、αの割当対象をβの割当先に割り当てる割当問題の数理モデルの次数に該当しＬに従うＭ（Ｍは自然数）が所定値以下か否かの判定である次数判定を行い、
コンピュータが、前記次数判定の結果が偽の場合、Ｍより小さい次数Ｍ´を決定する縮約処理を行い、当該縮約処理において決定された次数Ｍ´での数理モデルと、α及びβとを基に、相互作用モデルを演算することで割当問題を解くためのアクセラレータであるアニーリングマシン向けの相互作用モデルと、当該相互作用モデルの演算に使用される値のセットである値セットを決定し、
コンピュータが、前記決定された相互作用モデル及び値セットを提供する、
情報処理方法。