(57)【特許請求の範囲】
【請求項１】
第１の数理モデルにおける変数のうち、少なくとも一つの変数の値ごとに、前記第１の数理モデルにおける制約条件を表現する制約条件式を分割した、複数の分割ハミルトニアンを生成する分割工程と、
前記分割ハミルトニアンのそれぞれに対する量子アニーリングを実行する第１アニーリング工程と、
前記第１アニーリング工程の結果に応じて、前記第１の数理モデルを補正した、第２の数理モデルを生成する補正工程とを含む計算方法。
【請求項２】
前記第２の数理モデルが、前記第１の数理モデルにおける変数の組み合わせの少なくとも一部を、前記第１アニーリング工程において得られた解の少なくとも一部に固定した数理モデルである請求項１に記載の計算方法。
【請求項３】
前記第２の数理モデルから生成したハミルトニアンに対する量子アニーリングを実行する第２アニーリング工程をさらに含む請求項１または２に記載の計算方法。
【請求項４】
前記分割工程と、前記第１アニーリング工程との間において、前記分割ハミルトニアンに対する量子アニーリングが実行可能か否かを判断する判定工程をさらに含む請求項１から３の何れか１項に記載の計算方法。
【請求項５】
前記判定工程において、前記分割ハミルトニアンに対する量子アニーリングが実行可能ではないと判断した場合に、当該判定工程に次いで、前記分割ハミルトニアンのそれぞれが含む変数のうち、少なくとも一つの変数の値ごとに、前記分割ハミルトニアンのそれぞれをさらに複数の分割ハミルトニアンに分割する再分割工程をさらに含む請求項４に記載の計算方法。
【請求項６】
第１の数理モデルにおける変数のうち、少なくとも一つの変数の値ごとに、前記第１の数理モデルの制約条件を表現する制約条件式を分割し、複数の分割ハミルトニアンを生成する分割部と、
前記分割ハミルトニアンのそれぞれに対する量子アニーリングを実行させる実行部と、
前記量子アニーリングの結果に応じて、前記第１の数理モデルを補正した、第２の数理モデルを生成する補正部とを備えた計算装置。
【請求項７】
請求項６に記載の計算装置としてコンピュータを機能させるための計算プログラムであって、前記分割部、前記実行部、および前記補正部として前記コンピュータを機能させるための計算プログラム。
【請求項８】
請求項７に記載の計算プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は数理モデルの系のエネルギーを表すハミルトニアンを生成し、アニーリングマシンによって計算するための計算方法、および当該計算方法を実行するための計算装置、および計算プログラムに関する。
【背景技術】
【０００２】
非特許文献１は、アニーリングマシンを使用した、数理モデルをＱＵＢＯ（二次最適化問題）モデルに定式化して計算するための方法について開示する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models (Fred Glover, Gary Kochenberger, Yu Du, Quantum Bridge Analytics 1 Qubo for Oct 31)
【発明の概要】
【発明が解決しようとする課題】
【０００４】
数理モデルにおける変数の組み合わせの総数が増大した場合、当該数理モデルを量子アニーリングによって計算する過程はより複雑化する。特に、アニーリングマシンが使用可能な量子ビット数、または、各量子ビットの結合状態等に応じて、アニーリングマシンは、解くことが可能なハミルトニアンの規模に制限がある。このため、数理モデルにおける変数の組み合わせの総数が増大した場合、アニーリングマシンのスペックによっては、量子アニーリングの実施が困難となる場合がある。
【０００５】
この場合、ある変数の値ごとに、ハミルトニアンを分割して量子アニーリングを行うことが考えられる。しかしながら、ハミルトニアンに含まれる目的関数および制約条件式には、複数の変数に跨って作用する成分が存在する場合がある。この場合、単純に変数の値ごとにハミルトニアンを分割して量子アニーリングを実施すると、最適性を満たさない解、あるいは、制約条件を満たさない解が生成される場合がある。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、本開示の一態様に係る計算方法は、第１の数理モデルにおける変数のうち、少なくとも一つの変数の値ごとに、前記第１の数理モデルにおける制約条件を表現する制約条件式を分割した、複数の分割ハミルトニアンを生成する分割工程と、前記分割ハミルトニアンのそれぞれに対する量子アニーリングを実行する第１アニーリング工程と、前記第１アニーリング工程の結果に応じて、前記第１の数理モデルを補正した、第２の数理モデルを生成する補正工程とを含む。
【０００７】
また、本開示の一態様に係る計算装置は、第１の数理モデルにおける変数のうち、少なくとも一つの変数の値ごとに、前記第１の数理モデルの制約条件を表現する制約条件式を分割し、複数の分割ハミルトニアンを生成する分割部と、前記分割ハミルトニアンのそれぞれに対する量子アニーリングを実行させる実行部と、前記量子アニーリングの結果に応じて、前記第１の数理モデルを補正した、第２の数理モデルを生成する補正部とを備える。
【０００８】
本開示の各態様に係る計算装置は、コンピュータによって実現してもよい。この場合には、コンピュータを、前記計算装置が備える各部（ソフトウェア要素）として動作させてもよい。この場合、前記計算装置をコンピュータにて実現させる計算プログラム、およびそれを記録したコンピュータ読み取り可能な記録媒体も、本開示の範疇に入る。
【発明の効果】
【０００９】
本開示の一態様によれば、第１の数理モデルにおいて、少なくとも局所的に最適性を有し、かつ、第１の数理モデルにおける制約条件を満たす解を、より簡便に得ることができる。
【図面の簡単な説明】
【００１０】
【図１】本開示の実施形態１に係る計算方法を説明するためのフローチャートである。
【図２】本開示の実施形態１に係る計算装置のブロック図である。
【図３】本開示の実施形態２に係る計算方法を説明するためのフローチャートである。
【図４】本開示の実施形態２に係る計算装置のブロック図である。
【発明を実施するための形態】
【００１１】
〔実施形態１〕
＜計算装置の概要＞
以下、本開示の一実施形態について、詳細に説明する。
【００１２】
本実施形態に係る計算方法は、第１の数理モデルの系全体のエネルギーを最小化する、当該第１の数理モデルにおける変数の組み合わせを、アニーリングマシンによって計算する方法である。本実施形態においては、上記第１の数理モデルのエネルギーを表すハミルトニアンを生成し、当該ハミルトニアンからＱＵＢＯ行列を生成し、当該ＱＵＢＯ行列をアニーリングマシンによって解くことにより計算を行う。
【００１３】
本実施形態に係る第１の数理モデルの計算方法について、図１および図２を参照してより詳細に説明する。図１は、本実施形態に係る第１の数理モデルの計算方法を説明するためのフローチャートである。図２は、図１のフローチャートに示す計算方法を実行するための計算装置２のブロック図である。
【００１４】
図２に示すように、本実施形態に係る計算装置２は、アニーリングマシン４による計算を実行するためのデータを生成し、当該計算結果を蓄積および表示するための装置である。計算装置２は、操作部６と、メモリ８と、制御部１０と、通信部１２と、表示部１４とを備える。また、制御部１０は、ハミルトニアン生成部１６と、分割部１８と、ＱＵＢＯ行列生成部２０と、補正部２２とを備える。さらに、分割部１８は、固定変数決定部２４と、ハミルトニアン分割部２６とを備える。
【００１５】
操作部６は、例えば、計算装置２の使用者によって操作される。例えば、操作部６は、計算装置２による計算のためのデータを外部から入力するために使用される、キーボード等を含んでいてもよい。例えば、操作部６は、第１の数理モデルの各パラメータ、または、第１の数理モデルを計算する際の設定等を行うためのデータを入力するために使用されてもよい。
【００１６】
メモリ８は、計算装置２の備える各部から入力されたデータを少なくとも一時的に記憶する。メモリ８が記憶するデータは、計算装置２の備える各部から適宜読み出される。
【００１７】
制御部１０は、計算装置２に入力された、第１の数理モデルのパラメータ、および、計算の設定に基づいて、アニーリングマシン４による計算を実行するためのデータを生成する。制御部１０の各部の詳細な動作は、本実施形態に係る計算方法についての説明と併せ、後により詳細に説明する。
【００１８】
通信部１２は、メモリ８から読み出したデータの少なくとも一部を、計算装置２の外部機器へ送信し、当該外部機器から送信されたデータを受信し、メモリ８に記録するための通信装置である。本実施形態において、通信部１２は、アニーリングマシン４とデータの相互通信が可能である。
【００１９】
表示部１４は、メモリ８からの読み出したデータの少なくとも一部を、計算装置２の使用者等に表示するための装置である。例えば、表示部１４は、計算装置２に入力されたデータ、計算装置２の計算の設定、または、アニーリングマシン４による計算の結果等を表示するモニタであってもよい。
【００２０】
＜第１の数理モデルの定式化＞
本実施形態に係る第１の数理モデルの計算方法においては、はじめに、第１の数理モデルを定式化し、第１の数理モデルの系全体のエネルギーを表現する、第１のハミルトニアンＨを生成する（ステップＳ２）。ステップＳ２においては、例えば、はじめに、計算装置２の使用者が、操作部６によって、計算したい第１の数理モデルの各パラメータを計算装置２に入力する。入力された第１の数理モデルの各パラメータは、メモリ８に一時的に記録されてもよい。入力された第１の数理モデルの各パラメータは、次いで、制御部１０のハミルトニアン生成部１６に読み出される。
【００２１】
ハミルトニアン生成部１６は、メモリ８から読み出したデータを解析し、第１の数理モデルを表す式を生成し、当該式をＱＵＢＯモデルに沿って定式化した式に変換する。これにより、ハミルトニアン生成部１６は、例えば、目的関数ＨＯと、第１の数理モデルにおける制約条件を定式化した制約条件式ＨＬとを生成する。次いで、ハミルトニアン生成部１６は、生成した目的関数ＨＯおよび制約条件式ＨＬを合成して、第１のハミルトニアンＨを生成する。例えば、第１のハミルトニアンＨは、Ｈ＝ＨＯ＋ＨＬと表される。
【００２２】
目的関数ＨＯがＱＵＢＯモデルを定式化した式である場合、目的関数ＨＯは、例えば、下記式（１）によって表現される。
【００２３】
【数１】
0006985481.tif 000002
【００２４】
式（１）において、ｘｉは、０または１の値を取るバイナリ変数である。また、ａｉおよびｂｉｊは、それぞれ、１次の項および２次の項の係数である。また、ｉ、ｊ、およびｈは自然数である。また、ｈは、数理モデルにおける各変数の取り得る組み合わせの総数に対応する。スピン変数ｓｉ＝±１を用いて、ｘｉ＝（ｓｉ＋１）／２と表現できることから、目的関数ＨＯは、イジングモデルのエネルギー関数と等価である。
【００２５】
制約条件式ＨＬは、例えば、係数Ｃｌ等を用いて、以下の式（２）のように表現できる。
【００２６】
【数２】
0006985481.tif 000003
【００２７】
ここで、Ｌｌは、それぞれ、制約条件を定式化した制約条件項である。制約条件項Ｌｌは、元の第１の数理モデルにおける制約条件を満たさない組み合わせの場合に増大する項である。これにより、元の第１の数理モデルにおける制約条件が満たされない場合に、系全体のエネルギーを増大させて、解として採用されないように設定することが可能である。なお、式（２）におけるｋは自然数であり、第１の数理モデルにおける制約条件の個数に対応する。
【００２８】
＜固定する変数の決定＞
次いで、第１のハミルトニアンＨの制約条件式ＨＬを分割する分割工程を実行する。分割工程においては、第１のハミルトニアンＨに含まれる全ての変数のうち、少なくとも１つの変数について、その値ごとに制約条件式ＨＬを分割する。本実施形態に係る分割工程においては、第１のハミルトニアンＨに含まれる１つの変数について、その値ごとに制約条件式ＨＬを分割する例を説明する。
【００２９】
分割工程は、例えば、制御部１０の分割部１８に、第１のハミルトニアンＨの、少なくとも制約条件式ＨＬに関するデータを入力し、分割部１８の各部において、当該データを解析することにより実行される。分割工程においては、はじめに、第１のハミルトニアンＨに含まれる全ての変数のうち、その値ごとに制約条件式ＨＬを分割する変数の決定を行う（ステップＳ４）。換言すれば、ステップＳ４においては、制約条件式ＨＬを分割した後の式のそれぞれにおいて固定される変数である、固定変数を決定する。
【００３０】
ステップＳ４は、例えば、第１のハミルトニアンＨを、分割部１８の固定変数決定部２４に入力し、当該第１のハミルトニアンＨを解析させることにより実行する。本実施形態においては、例えば、制約条件式ＨＬが含む全ての変数のうち、目的関数ＨＯまたは制約条件式ＨＬにおいて、複数の値に渡って作用する成分が存在しない、あるいは、当該成分が少ない変数を、固定変数に優先的に採用してもよい。
【００３１】
＜ハミルトニアンの分割＞
次いで、ステップＳ４において決定された固定変数の値ごとに、制約条件式ＨＬを分割する（ステップＳ６）。ステップＳ６は、固定変数決定部２４からハミルトニアン分割部２６に、第１のハミルトニアンＨの、少なくとも制約条件式ＨＬに関するデータと、ステップＳ４において決定された、固定変数の情報とを入力し、分割後の式を出力させることにより実行する。
【００３２】
本実施形態において、例えば、ステップＳ６においては、制約条件式ＨＬを、複数の分割ハミルトニアンＨｍに分割する。分割ハミルトニアンＨｍは以下の式（３）のように表現できる。
【００３３】
【数３】
0006985481.tif 000004
【００３４】
上記式（３）において、ｍは、上述した固定変数の取り得る値の何れかである。また、上記式（３）における制約条件項Ｌｌｍは、制約条件項Ｌｌに含まれる固定変数にｍを代入した式を表す。例えば、固定変数が、１の値を取り得るとする。ここで、ｍ＝１の場合、制約条件項Ｌｌｍは、制約条件項Ｌｌの固定変数に１を代入した式となる。このため、固定変数の値ごとに、複数の分割ハミルトニアンＨｍがステップＳ６において生成される。
【００３５】
また、上記式（３）におけるＺは、制約条件項Ｌｌが、固定変数の複数の値に渡って作用する制約条件に対応する項となる、ｌの値の集合である。このため、分割ハミルトニアンＨｍには、固定変数の複数の値に渡って作用する制約条件に対応する制約条件項Ｌｌｍが含まれていない。
【００３６】
＜分割ハミルトニアンに対する量子アニーリング工程＞
次いで、分割ハミルトニアンＨｍのそれぞれに対し、量子アニーリングを実行する（ステップＳ８）、第１アニーリング工程を実行する。ステップＳ８においては、はじめに、分割ハミルトニアンＨｍのそれぞれに関するデータを、ハミルトニアン分割部２６からＱＵＢＯ行列生成部２０に入力することにより、各分割ハミルトニアンＨｍに対するＱＵＢＯ行列を生成する。
【００３７】
ＱＵＢＯ行列は、対応するハミルトニアンをＱＵＢＯモデルの行列によって表現する上三角行列である。あるハミルトニアンからのＱＵＢＯ行列の生成は、一般に用いられる、ハミルトニアンをＱＵＢＯ行列に変換する手法を採用できる。これにより、アニーリングマシンによって計算可能なＱＵＢＯ行列が生成される。生成されたＱＵＢＯ行列は、例えば、少なくとも一時的に、メモリ８に記録される。
【００３８】
次いで、分割ハミルトニアンＨｍのそれぞれから生成されたＱＵＢＯ行列を、アニーリングマシン４に入力し、アニーリングマシン４を用いて計算する。例えば、通信部１２が、メモリ８からＱＵＢＯ行列のデータを読み出し、アニーリングマシン４に送信する。ＱＵＢＯ行列のデータを受信したアニーリングマシン４は、ＱＵＢＯ行列のデータを受信して、当該ＱＵＢＯ行列に対する量子アニーリングを実行する。なお、通信部１２は、ＱＵＢＯ行列生成部２０から直接ＱＵＢＯ行列に関するデータを受信し、アニーリングマシン４への当該データの送信を行ってもよい。
【００３９】
以上より、少なくとも、計算装置２における、通信部１２、およびＱＵＢＯ行列生成部２０は、分割ハミルトニアンＨｍのそれぞれに対する量子アニーリングを実行させるための、実行部として機能する。
【００４０】
これにより、分割ハミルトニアンＨｍのそれぞれのエネルギーを最適化する変数の組み合わせが解として得られる。アニーリングマシン４による計算の結果は、通信部１２に送信される。アニーリングマシン４による計算の結果を受信した通信部１２は、当該結果をメモリ８に記録する。アニーリングマシン４による計算の結果は、メモリ８から表示部１４によって読みだされ、表示部１４に表示されてもよい。
【００４１】
ステップＳ８において得られる解は、分割ハミルトニアンＨｍのそれぞれのエネルギーを最適化する変数の組み合わせであるため、元の第１の数理モデルに対する最適性および制約条件を満たす組み合わせとは限らない。特に、ステップＳ８において得られる解は、元の第１の数理モデルから得られた第１のハミルトニアンＨの目的関数ＨＯおよび固定変数の複数の値に跨って適用される制約条件項Ｌｌの成分が考慮されていない。ただし、ステップＳ８において得られる解は、固定変数の複数の値に跨って適用される制約条件項Ｌｌに相当する制約条件を除く、全ての制約条件を満たす変数の組み合わせとなる。
【００４２】
＜第２の数理モデルの生成＞
次いで、分割ハミルトニアンＨｍに対する量子アニーリングの結果に応じて、第１の数理モデルを補正し、第２の数理モデルを生成する（ステップＳ１０）、補正工程を実行する。補正工程は、例えば、補正部２２が、メモリ８から、分割ハミルトニアンＨｍに対する量子アニーリングの結果を含むデータを読み出し、当該データを解析することにより実行する。
【００４３】
補正工程において、具体的には、第１の数理モデルにおける、少なくとも一部の変数の組み合わせを、ステップＳ８において得られた解の少なくとも一部の組み合わせに固定して、これを第２の数理モデルとする。これにより、第２の数理モデルにおいては、変数の組み合わせの一部が固定されているため、最適な組み合わせを求める必要のある変数の個数が低減する。
【００４４】
上述したように、ステップＳ８において得られた解は、固定変数の複数の値に跨って適用される制約条件項Ｌｌに相当する制約条件を除く、全ての制約条件を満たす変数の組み合わせとなる。これを受けて、本実施形態において、第２の数理モデルにおいて組み合わせを固定する変数は、例えば、ステップＳ４において決定された固定変数、または、当該固定変数の値との相互作用の大きい変数を除く変数の組み合わせとする。これにより、第２の数理モデルに対する量子アニーリングにより得られる解が、第１の数理モデルにおける全ての制約条件を満たす蓋然性が向上する。
【００４５】
次いで、第２の数理モデルに基づいて、新たな目的関数Ｈ’Ｏ、および、新たな制約条件式Ｈ’Ｌを生成することにより、第２のハミルトニアンＨ’を生成する（ステップＳ１２）。第２のハミルトニアンＨ’は、例えば、Ｈ’＝Ｈ’Ｏ＋Ｈ’Ｌと表される。ステップＳ１２は、補正部２２からハミルトニアン生成部１６に、第２の数理モデルの各パラメータに関するデータを入力し、解析させることにより実行する。
【００４６】
新たな目的関数Ｈ’Ｏは、第１の数理モデルにおける目的関数ＨＯを、第２の数理モデルにおいて最小化したいエネルギーを表すコスト関数に変換したコスト関数である。特に、第２の数理モデルにおける目的関数Ｈ’Ｏは、当該目的関数Ｈ’Ｏを最小化した場合に、ステップＳ８において固定された変数の組み合わせの範囲内において、目的関数ＨＯについても最小化するように決定してもよい。
【００４７】
また、制約条件式Ｈ’Ｌは、第１の数理モデルにおける制約条件を、第２の数理モデルに沿って変換し、定式化したものである。例えば、制約条件式Ｈ’Ｌは、以下の式（４）のように表される。
【００４８】
【数４】
0006985481.tif 000005
【００４９】
ここで、Ｌ’ｌは、それぞれ、第１の数理モデルにおける制約条件を、第２の数理モデルに沿って変形して生成した、第２の数理モデルにおける制約条件を定式化した制約条件項である。また、制約条件項Ｌ’ｌには、固定変数の複数の値に渡って作用する成分を有する制約条件項Ｌｌに対応する制約条件を含める。特に、制約条件項Ｌ’ｌは、得られた解が、当該項に対応する、第２の数理モデルにおける制約条件を満たす場合に、第１の数理モデルにおける制約条件も満たすように決定してもよい。なお、式（４）におけるｕは自然数であり、第２の数理モデルにおける制約条件の個数に対応する。
【００５０】
＜第２のハミルトニアンに対する計算＞
次いで、第２のハミルトニアンＨ’に対し、量子アニーリングを再度実行する（ステップＳ１４）、第２アニーリング工程を実行する。ステップＳ１４においては、はじめに、第２のハミルトニアンＨ’に関するデータを、ハミルトニアン生成部１６からＱＵＢＯ行列生成部２０に入力することにより、第２のハミルトニアンＨ’に対するＱＵＢＯ行列を生成する。生成されたＱＵＢＯ行列は、例えば、少なくとも一時的に、メモリ８に記録される。
【００５１】
次いで、第２のハミルトニアンＨ’から生成されたＱＵＢＯ行列を、アニーリングマシン４に入力し、アニーリングマシン４を用いて計算する。例えば、通信部１２が、メモリ８からＱＵＢＯ行列のデータを読み出し、アニーリングマシン４に送信する。ＱＵＢＯ行列のデータを受信したアニーリングマシン４は、当該ＱＵＢＯ行列に対する量子アニーリングを実行する。
【００５２】
これにより、第２のハミルトニアンＨ’のエネルギーを最適化する変数の組み合わせが解として得られる。アニーリングマシン４による計算の結果は、通信部１２に送信される。アニーリングマシン４による計算の結果を受信した通信部１２は、当該結果をメモリ８に記録する。アニーリングマシン４による計算の結果は、メモリ８から表示部１４によって読みだされ、表示部１４に表示されてもよい。
【００５３】
ステップＳ１４において得られた解は、理想的には、第２の数理モデルの系全体のエネルギーを最小化する、第２の数理モデルにおける変数の組み合わせの最適解である。換言すれば、当該解は、第１の数理モデルにおける変数の一部の組み合わせを固定した状態における計算によって得られたものである。このため、ステップＳ１４において得られた解の、第１の数理モデルにおける、大域的な最適性は必ずしも保障されない。
【００５４】
ただし、第１の数理モデルにおける変数の組み合わせのうち、第２の数理モデルにおいて固定された変数の組み合わせは、第１の数理モデルにおける制約条件を満たすものである。また、第２の数理モデルにおける制約条件は、固定変数の複数の値に渡って作用する成分を有する制約条件項Ｌｌに対応する制約条件を含む。さらに、第２の数理モデルを定式化して生成した目的関数Ｈ’Ｏ、および、制約条件式Ｈ’Ｌは、それぞれ、第１の数理モデルを定式化して生成した目的関数ＨＯ、および、制約条件式ＨＬに対応する。したがって、ステップＳ１４において得られた解は、第１の数理モデルにおいても、一部の変数の組み合わせを固定した状態における最適解であり、換言すれば、少なくとも局所的な最適性を有する解であり、制約条件を満たす解となる。
【００５５】
＜実施形態のまとめ＞
本実施形態に係る計算方法においては、第１の数理モデルにおける変数の組み合わせの一部を固定した、第２の数理モデルを生成して、当該第２の数理モデルに基づき、第２のハミルトニアンＨ’を生成している。このため、第２の数理モデルを定式化した第２のハミルトニアンＨ’に含まれる変数は、第１の数理モデルを定式化したハミルトニアンＨに含まれる変数よりも少ない。このため、第２の数理モデルは、量子アニーリングによって、より簡便に解くことが可能となる。
【００５６】
また、上述したように、第２の数理モデルを、量子アニーリングによって解くことにより得られる解は、第１の数理モデルにおいても、少なくとも局所的な最適性を有する解であり、制約条件を満たす解となる。
【００５７】
したがって、本実施形態に係る計算方法によれば、第１の数理モデルにおいて、少なくとも局所的に最適性を有し、かつ、制約条件を満たす解を、より簡便に得ることができる。
【００５８】
本実施形態に係る計算方法によって計算される第１の数理モデルは、例えば、レイバースケジューリングモデルであってもよい。以下、本実施形態に係る計算方法によって、レイバースケジューリングモデルを計算する具体的手法を、実施例として説明する。
【実施例】
【００５９】
＜レイバースケジューリングモデル＞
レイバースケジューリングモデルは、例えば、各作業者に、どの日の、どの時間帯に、どの作業を割り当てるかの組み合わせを決定するためのモデルである。本実施例においては、はじめに、ステップＳ２を実行し、ハミルトニアン生成部１６が、レイバースケジューリングモデルを定式化し、第１のハミルトニアンＨを生成する。
【００６０】
第１のハミルトニアンＨの生成に使用する要素の集合およびバイナリ変数を以下に定義する。例えば、作業を行う作業者の集合を、Ｐ＝｛１，２，・・・，ｎ｝とする。スケジュール対象となる日付の集合を、Ｄ＝｛１，２，・・・，ｑ｝とする。スケジュール対象となる日付における、一日のうちのある時間帯の集合を、Ｓ＝｛１，２，・・・，ｒ｝とする。休憩を含む、作業者が実施する作業の集合を、Ｗ＝｛１，２，・・・，ｔ｝とする。作業者ｐが、日付ｄの時間帯ｓに、作業種別ｗをする場合に１、そうでない場合に０となるバイナリ変数を、ｘｐｄｓｗ，ｐ∈Ｐ，ｄ∈Ｄ，ｓ∈Ｓ，ｗ∈Ｗとする。
【００６１】
本実施例に係る第１の数理モデルにおいては、総人件費を最低限に抑えつつ、かつ、各作業者の休日の希望、または休憩時間帯の希望を可能な限り実現したスケジュールを、レイバースケジューリングモデルを用いて決定することを目的とする。このため、第１の数理モデルにおける目的関数ＨＯは、人件費のコストと、各作業者の休日の希望、または休憩時間帯の希望の、少なくとも何れか一方を満たせなかった場合に増加するコストとの合計値とする。
【００６２】
目的関数ＨＯを決定するため、以下の集合を定義する。例えば、作業者ｐが休憩を希望する、日付ｄおよび時間帯ｓの組み合わせの集合を、Ｏｐ＝｛（ｄ，ｓ），ｄ∈Ｄ，ｓ∈Ｓ｝（ｐ∈Ｐ）とする。日付ｄの時間帯ｓに作業種別ｗをするために必要な作業者の人数の集合を、ｅｄｓｗ∈｛０，１，・・・｝，ｄ∈Ｄ，ｓ∈Ｓ，ｗ∈Ｗとする。作業者ｐに対する、１つの時間帯あたりの人件費の集合を、ｆｐ∈｛０，１，・・・｝，ｐ∈Ｐとする。
【００６３】
上記集合およびバイナリ変数を用いて、本実施例に係る第１の数理モデルの目的関数ＨＯは、以下の式（５）によって表される。
【００６４】
【数５】
0006985481.tif 000006
【００６５】
次に、本実施例に係る第１の数理モデルにおける制約条件を設定する。例えば、以下の４つの制約条件を設定する。
条件１：作業者１人に２つ以上の作業を同時に割り当てない。
条件２：各作業に必要な作業者の人数を満たす。
条件３：各作業者の一日の労働時間が、上限Ｌを超えない。
条件４：各作業者に対し、一週間に少なくとも１日は休日を割り当てる。
【００６６】
上記条件１は、下記式（６）にて表現できる。
【００６７】
【数６】
0006985481.tif 000007
【００６８】
上記条件２は、下記式（７）にて表現できる。
【００６９】
【数７】
0006985481.tif 000008
【００７０】
上記条件３は、下記式（８）にて表現できる。
【００７１】
【数８】
0006985481.tif 000009
【００７２】
上記条件４を定式化するために、新たなバイナリ変数ａｐｄ，ｐ∈Ｐ，ｄ∈Ｄを定義する。ａｐｄは、作業者ｐが、日付ｄに作業を行う場合に１、そうでない場合に０をとるバイナリ変数である。
【００７３】
上記バイナリ変数ａｐｄに対する制約条件を、下記式（９）および下記式（１０）に沿って定義する。
【００７４】
【数９】
0006985481.tif 000010
【００７５】
【数１０】
0006985481.tif 000011
【００７６】
これより、上記条件４は、下記式（１１）にて表現できる。
【００７７】
【数１１】
0006985481.tif 000012
【００７８】
ここで、上記式（１１）におけるｗｋは週の集合である。集合ｗｋに含まれる、ｗｋ１、ｗｋ２、…は、それぞれ、第１週、第２週、…のそれぞれの日付を含む集合である。
【００７９】
これらの制約条件から、制約条件項Ｌｌを決定する。条件１、条件２、条件３、および条件４のそれぞれに対応する制約条件項を、Ｌ１、Ｌ２、Ｌ３、およびＬ４とする。この場合、Ｌ１、Ｌ２、Ｌ３、およびＬ４は、それぞれ、以下の式（１２）から式（１５）に定式化される。
【００８０】
【数１２】
0006985481.tif 000013
【００８１】
【数１３】
0006985481.tif 000014
【００８２】
【数１４】
0006985481.tif 000015
【００８３】
【数１５】
0006985481.tif 000016
【００８４】
なお、本実施形態に係る計算装置２を用いる場合、操作部６を用いて、上述した第１のハミルトニアンＨの生成に使用する、要素の集合およびバイナリ変数を表現する各パラメータを入力してもよい。これにより、ハミルトニアン生成部１６が、入力されたパラメータに基づいて、第１のハミルトニアンＨに関するデータを生成する。
【００８５】
＜分割を用いない場合の解き方＞
従来の手法により、上記第１の数理モデルに対する量子アニーリングを実行する場合、上記式（５）、および上記式（１２）から式（１５）までに基づいて、第１のハミルトニアンＨ＝ＨＯ＋ＨＬ＝ＨＯ＋Ｃ１Ｌ１＋Ｃ２Ｌ２＋Ｃ３Ｌ３＋Ｃ４Ｌ４を生成する。次いで、第１のハミルトニアンＨからＱＵＢＯ行列を生成し、アニーリングマシン４による量子アニーリングを実行する。
【００８６】
この場合、作業者、日付、時間帯、および作業種別の要素の個数が増えた場合、バイナリ変数の数、および、各要素の相互作用の数も増える。これに伴い、数理モデルがより複雑化し、最適解が求まる蓋然性が低下する。さらに、バイナリ変数の数、および、各要素の相互作用の数が増えることにより、アニーリングマシン４が必要な量子ビットの結合状態の個数が増え、アニーリングマシン４による計算が不可能となる場合もある。
【００８７】
さらに、上述した条件３、および条件４が守られた場合においても、Ｌ３、Ｌ４については、０とならない場合がある。このように、制約条件が複雑となると、扱うバイナリ変数の個数が増えるほど、制約条件式ＨＬの各係数Ｃｌのそれぞれの値の設定がより困難となる課題も存在する。
【００８８】
＜レイバースケジューリングにおけるハミルトニアンの分割＞
本実施例においては、上述した第１のハミルトニアンＨのうち、制約条件式ＨＬの分割を行い、分割ハミルトニアンＨｍを生成する。本実施例においては、はじめに、ステップＳ４において、固定変数決定部２４が、制約条件式ＨＬの変数のうち、固定する変数を日付ｄに決定する。固定変数を日付ｄとした理由は、制約条件のうち、複数の日付に渡って作用する制約条件が、条件４のみである点、および、日付ｄを除く変数の組み合わせを決定した場合に、条件４を満たす解が求まりやすい点が挙げられる。固定する変数の決定は、例えば、固定変数決定部２４が、第１のハミルトニアンＨに関するデータを解析することにより実行されてもよい。
【００８９】
次いで、ステップＳ６を実行し、ハミルトニアン分割部２６が、上述した制約条件式ＨＬを、を、日付の集合Ｄの要素ごとに分割し、複数の分割ハミルトニアンＨｍを生成する。分割ハミルトニアンＨｍは、Ｈｍ＝Ｃ１Ｌ１ｍ＋Ｃ２Ｌ２ｍ＋Ｃ３Ｌ３ｍと表される。例えば、Ｌ１１、Ｌ２１、およびＬ３１は、それぞれ、Ｌ１、Ｌ２、およびＬ３に、ｄ＝１を代入した式となる。以上により、日付ｄの値ごとに分割ハミルトニアンＨｍが生成される。
【００９０】
次いで、ステップＳ８を実行し、生成された分割ハミルトニアンＨｍのそれぞれに対する量子アニーリングを実行する。当該量子アニーリングの実行は、ＱＵＢＯ行列生成部２０が、分割ハミルトニアンＨｍに関するデータからＱＵＢＯ行列を生成し、当該ＱＵＢＯ行列に関するデータをアニーリングマシン４に入力することにより実行されてもよい。これにより、本実施例においては、第１の数理モデルにいて、各日付における、どの作業者が、どの時間帯に、どの作業を行うかについての組み合わせが決定される。当該組み合わせは、上述した制約条件のうち、条件１、条件２、および条件３を満たす組み合わせとなる。
【００９１】
＜レイバースケジューリングモデルの補正＞
次いで、ステップＳ１０を実行し、補正部２２が、ステップＳ８において得られた解に基づき、上述した第１の数理モデルを補正し、第２の数理モデルを生成する。本実施例においては、第１の数理モデルにおける、時間帯と当該時間帯に実施する作業の種別との組み合わせのみを、ステップＳ８において得られた組み合わせに固定したものを、第２の数理モデルとする。
【００９２】
換言すれば、第２の数理モデルは、どの作業者が、どの日付に、どの時間帯に割り当てられた作業を行うのかについての組み合わせを決定するモデルである。時間帯と作業種別との組み合わせが固定されているため、第２の数理モデルは、第１の数理モデルと比較して、求めるべき組み合わせを構成する変数の個数が少なくなっている。
【００９３】
＜第２のレイバースケジューリングモデルの定式化＞
次いで、ステップＳ１２を実行し、ハミルトニアン生成部１６が、第２の数理モデルの定式化により、第２のハミルトニアンＨ’を生成する。本実施例においては、第２の数理モデルの定式化を実行するために、集合およびバイナリ変数を以下に定義する。例えば、作業者ｐが日付ｄに作業を行う場合に１となり、そうでない場合に０となるバイナリ変数を、ｖｄｐ∈｛０，１｝，ｄ∈Ｄ，ｐ∈Ｐとする。作業者ｐの日付ｄにおける、休憩を除いた作業種別の個数を、ｙｄｐ∈｛０，１，・・・｝，ｄ∈Ｄ，ｐ∈Ｐとする。
【００９４】
なお、本実施例においては、ステップＳ８にて算出された、第１の数理モデルにおける変数の組み合わせの一部に基づいて、第２の数理モデルにおける変数および集合を定義してもよい。例えば、ステップＳ８にて算出した解において、作業者ｐが日付ｄに割り当てられていた作業を、作業者ｐ’が代わりに行う場合に１、そうでない場合に０となるバイナリ変数を、ｘ’ｐ’ｄｐ，ｐ’∈Ｐ，ｄ∈Ｄ，ｐ∈Ｐとする。また、ｘ’ｐ’ｄｐが１である場合に、無視することとなる、作業者Ｐ’が希望する休みの数を、ｚｐ’ｄｐ∈｛０，１，・・・｝，ｐ’∈Ｐ，ｄ∈Ｄ，ｐ∈Ｐとする。
【００９５】
第２の数理モデルにおいても、第１の数理モデルと同じく、総人件費を最低限に抑えつつ、かつ、各作業者の休日の希望、または休憩時間帯の希望を可能な限り実現したスケジュールを、レイバースケジューリングモデルを用いて決定することを目的とする。このため、第２の数理モデルにおける目的関数Ｈ’Ｏは、人件費のコストと、各作業者の休日の希望、または休憩時間帯の希望を満たせなかった場合に増加するコストとの合計値とする。
【００９６】
上記集合およびバイナリ変数を用いて、本実施例に係る第２の数理モデルの目的関数Ｈ’Ｏは、以下の式（１６）によって表される。
【００９７】
【数１６】
0006985481.tif 000017
【００９８】
次に、本実施例に係る第２の数理モデルにおける制約条件を設定する。本実施例においては、上述した第１の数理モデルにおける制約条件を変形した、以下の３つの制約条件を設定する。
条件１’：作業者１人に２つ以上の時間帯および作業の組み合わせを同時に割り当てない。
条件２’：時間帯と作業種別の組み合わせのそれぞれに、作業者を１人ずつ割り当てる。
条件３’：各作業者に対し、一週間に少なくとも１日は休日を割り当てる。
【００９９】
上記条件１’から、制約条件項Ｌ’１は、下記式（１７）にて表現できる。
【０１００】
【数１７】
0006985481.tif 000018
【０１０１】
上記条件２’から、制約条件項Ｌ’２は、下記式（１８）にて表現できる。
【０１０２】
【数１８】
0006985481.tif 000019
【０１０３】
上記条件３’から、制約条件項Ｌ’３は、下記式（１９）にて表現できる。
【０１０４】
【数１９】
0006985481.tif 000020
【０１０５】
ここで、上記式（１９）における、ｄ１とは、各週における最初の日付を含む集合である。以上より、第２のハミルトニアンＨ’＝Ｈ’Ｏ＋Ｈ’Ｌ＝Ｈ’Ｏ＋Ｃ１Ｌ’１＋Ｃ２Ｌ’２＋Ｃ３Ｌ’３が生成される。
【０１０６】
なお、ステップＳ１２においては、操作部６を用いて、上述した第２のハミルトニアンＨ’の生成に使用する、要素の集合およびバイナリ変数を表現する各パラメータが入力されてもよい。これにより、ハミルトニアン生成部１６が、入力されたパラメータと、補正部２２により生成された第２の数理モデルの関するデータとに基づいて、第２のハミルトニアンＨ’に関するデータを生成する。
【０１０７】
＜第２のレイバースケジューリングモデルの量子アニーリング工程＞
次いで、ステップＳ１４を実行し、生成された第２のハミルトニアンＨ’に対する量子アニーリングを実行する。当該量子アニーリングの実行は、ＱＵＢＯ行列生成部２０が、第２のハミルトニアンＨ’に関するデータからＱＵＢＯ行列を生成し、当該ＱＵＢＯ行列に関するデータをアニーリングマシン４に入力することにより実行されてもよい。これにより、本実施例においては、第２の数理モデルにおいて、各日付における、どの作業者が、どの時間帯に割り当てられた作業を行うかについての組み合わせが決定される。
【０１０８】
ステップＳ１４において得られた解は、理想的には、第２の数理モデルにおける、各変数の組み合わせの最適解である。換言すれば、ステップＳ１４において得られた解は、条件１’、条件２’、および条件３’を満たしつつ、目的関数Ｈ’Ｏを最小化する、第２の数理モデルにおける変数の組み合わせとなる。
【０１０９】
ここで、第２の数理モデルにおいては、時間帯と作業種別との組み合わせが固定されている。また、第２の数理モデルにおける、時間帯と作業種別との組み合わせは、上述した、第１の数理モデルにおける、各制約条件を満たすように決定されている。このことから、ステップＳ１４において得られた解が、第２の数理モデルにおける制約条件を全て満たす場合、当該解は、第１の数理モデルにおける制約条件を全て満たす解である。
【０１１０】
また、第２の数理モデルにおける目的関数Ｈ’Ｏは、第１の数理モデルにおける目的関数ＨＯと対応している。このため、ステップＳ１４において得られた解が、目的関数Ｈ’Ｏを最小化する場合、当該解は、時間帯と作業種別との組み合わせを、ステップＳ８において算出した解に基づき固定した場合において、目的関数ＨＯを最小化する解である。したがって、第２の数理モデルの最適解は、少なくとも、第１の数理モデルの局所的な最適解となる。
＜補記＞
本実施例においては、数理モデルがレイバースケジューリングモデルである場合について説明した。しかしながら、これに限られず、本実施形態に係る計算方法は、数理モデルが複数の変数の組み合わせを求める問題であり、数理モデルにおける制約条件を表す関係式を、ある変数の値ごとに分割できる場合には、適用することができる。この場合、上述した各式における集合およびバイナリ変数の定義、あるいは、係数の値は、数理モデルに応じて適宜決定することが可能である。
【０１１１】
〔実施形態２〕
＜再分割工程＞
本実施形態に係る第１の数理モデルの計算方法について、図３および図４を参照してより詳細に説明する。図３は、本実施形態に係る第１の数理モデルの計算方法を説明するためのフローチャートである。図４は、図３のフローチャートに示す計算方法を実行するための計算装置２Ａのブロック図である。
【０１１２】
本実施形態に係る計算方法を実行するために使用する計算装置２Ａは、前実施形態に係る計算装置２と比較して、分割部１８が、さらに、分割ハミルトニアン評価部２８を備えている点を除き、同一の構成を備えていてもよい。
【０１１３】
本実施形態においても、前実施形態と同じく、第１の数理モデルの系全体のエネルギーを最小化する、当該第１の数理モデルにおける変数の組み合わせを、アニーリングマシンによって計算する方法について説明する。
【０１１４】
本実施形態に係る第１の数理モデルの計算方法においては、前実施形態に係る、ステップＳ２からステップＳ６までを、前実施形態において説明した方法と同一の方法にて、順に実行する。これにより、本実施形態においても、第１の数理モデルから定式化した第１のハミルトニアンＨのうち、制約条件式ＨＬを分割した、複数の分割ハミルトニアンＨｍが生成される。
【０１１５】
本実施形態においては、ステップＳ６に次いで、分割ハミルトニアンＨｍのそれぞれに対する量子アニーリングが実行可能か否かを判定する（ステップＳ１６）、判定工程を実施する。判定工程においては、例えば、分割ハミルトニアンＨｍのそれぞれに含まれる変数がとり得る値の組み合わせの総数が、アニーリングマシン４によって計算可能な規模を超過しているか否かを判定する。判定工程は、例えば、分割ハミルトニアンＨｍのそれぞれのデータを、分割ハミルトニアン評価部２８がハミルトニアン分割部２６から受信し、解析することにより実行される。
【０１１６】
ステップＳ１６において、分割ハミルトニアンＨｍのそれぞれに対する量子アニーリングの実行が困難であると判断した場合には、分割ハミルトニアンＨｍのそれぞれをさらに分割する、再分割工程が実行される。
【０１１７】
はじめに、分割ハミルトニアン評価部２８から固定変数決定部２４に、分割ハミルトニアンＨｍのそれぞれに対する量子アニーリングの実行が困難であるとの情報を送信する。当該情報を受けて、固定変数決定部２４は、上述したステップＳ４と同一の手法により、分割ハミルトニアンＨｍに含まれる全ての変数のうち、その値ごとに分割ハミルトニアンＨｍを分割する変数の決定を行う。次いで、固定変数決定部２４からハミルトニアン分割部２６に、分割ハミルトニアンＨｍに関するデータと、新たに決定された固定変数の情報とを入力し、分割後の式を出力させる。
【０１１８】
上記再分割工程により、分割ハミルトニアンＨｍのそれぞれをさらに分割したハミルトニアンが生成される。分割ハミルトニアンＨｍからさらに分割されたハミルトニアンは、分割ハミルトニアンＨｍよりも、さらに変数が少ないため、変数がとり得る値の組み合わせの総数についても減少する。
【０１１９】
上述した判定工程および再分割工程とは、最終的に得られた分割後のハミルトニアンが、アニーリングマシン４によって計算可能となる規模まで分割されるまで、繰り返し実行されてもよい。最終的に得られた分割後のハミルトニアンが、アニーリングマシン４によって計算可能となった場合には、分割ハミルトニアン評価部２８からＱＵＢＯ行列生成部２０にデータが送信され、ＱＵＢＯ行列の生成が実行される。これにより、上述したステップＳ８が実行される。
【０１２０】
この後、ステップＳ１０からステップＳ１４が、上述した手法と同一の手法により、順に実行される。これにより、本実施形態においても、第１の数理モデルにおいて、少なくとも局所的に最適性を有し、かつ、第１の数理モデルにおける制約条件を満たす解が得られる。
【０１２１】
本実施形態においては、分割ハミルトニアンＨｍのそれぞれに対する量子アニーリングが実行可能か否かを判定する判定工程が実行される。また、判定工程において、分割ハミルトニアンＨｍのそれぞれに対する量子アニーリングが実行可能ではないと判定された場合に、さらに分割ハミルトニアンＨｍを分割する再分割工程が実行される。これにより、１回の分割によって量子アニーリングの実行が不可能な程度の規模を有する第１のハミルトニアンＨに対しても、少なくとも局所的に最適性を有し、かつ、第１の数理モデルにおける制約条件を満たす解が得られる。
＜ソフトウェアおよびプログラムによる実施例＞
上述した各実施形態に係る分割部１８、ＱＵＢＯ行列生成部２０、および、補正部２２は、計算装置２および計算装置２Ａが備える集積回路、換言すれば、ＩＣチップ等に形成された論理回路、換言すれば、ハードウェアによって実現してもよい。あるいは、分割部１８、ＱＵＢＯ行列生成部２０、および、補正部２２は、ソフトウェアによって実現してもよい。
【０１２２】
上記各部がソフトウェアである場合、アニーリングマシン４と通信可能な端末において、各部の機能を実現するソフトウェアであるプログラムの命令を実行することにより、分割部１８、ＱＵＢＯ行列生成部２０、および、補正部２２における処理が実行されてもよい。この端末は、例えば１つ以上のプロセッサを備えていると共に、上記プログラムを記憶した端末読み取り可能な記録媒体を備えている。上記端末において、上記プロセッサが上記プログラムを上記記録媒体から読み取って実行することにより、本開示の目的が達成される。したがって、上記プログラムは、分割部１８、ＱＵＢＯ行列生成部２０、および、補正部２２における処理を実行する、計算プログラムとして機能する。
【０１２３】
上記プロセッサとしては、例えばＣＰＵ（Central Processing Unit）を用いることができる。上記記録媒体としては、「一時的でない有形の媒体」、例えば、ＲＯＭ（Read Only Memory）等の他、テープ、ディスク、カード、半導体メモリ、プログラマブルな論理回路などを用いることができる。また、上記プログラムを展開するＲＡＭ（Random Access Memory）などをさらに備えていてもよい。
【０１２４】
上記プログラムは、該プログラムを伝送可能な任意の伝送媒体（通信ネットワークや放送波等）を介して上記端末に供給されてもよい。なお、本開示の一態様は、上記プログラムが電子的な伝送によって具現化された、搬送波に埋め込まれたデータ信号の形態でも実現され得る。
【０１２５】
本開示は上述した各実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、異なる実施形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施形態についても本開示の技術的範囲に含まれる。
【符号の説明】
【０１２６】
２、２Ａ  計算装置
１０      制御部
１２      通信部
１６      ハミルトニアン生成部
１８      分割部
２０      ＱＵＢＯ行列生成部
２２      補正部
２４      固定変数決定部
２６      ハミルトニアン分割部
２８      分割ハミルトニアン評価部
【要約】
【課題】ある数理モデルにおいて、少なくとも局所的に最適性を有し、かつ、制約条件を満たす解を、より簡便に得ることができる。
【解決手段】計算方法は、分割工程（Ｓ４、Ｓ６）と、第１アニーリング工程（Ｓ８）と、補正工程（Ｓ１０）とを含む。分割工程においては、第１の数理モデルにおける変数のうち、少なくとも一つの変数の値ごとに、第１の数理モデルにおける制約条件を表現する制約条件式を分割した、複数の分割ハミルトニアンを生成する。第１アニーリング工程においては、分割ハミルトニアンのそれぞれに対する量子アニーリングを実行する。補正工程においては、第１アニーリング工程の結果に応じて、第１の数理モデルを補正した、第２の数理モデルを生成する。
【選択図】図１【図１】
0006985481.tif 000021
【図２】
0006985481.tif 000022
【図３】
0006985481.tif 000023
【図４】
0006985481.tif 000024