(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)
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１に開示される、ＱＵＢＯ行列を生成するためのハミルトニアンには、制約条件を表現する関数の近似式を含む場合がある。ここで、数理モデルにおける各変数の値と、上記近似式との差異を評価する比較項が、２次以下の項である必要があることを考慮すると、上記近似式は、１次式である必要がある。このため、上記関数の値とその近似式の値との誤差が大きくなる場合がある。
【０００５】
当該誤差を有するハミルトニアンを使用して、アニーリングマシンによる計算を実行した場合、制約条件を満たさない、あるいは、制約条件を満たすものの、最適性を有さない計算結果が得られる場合があり、計算精度が低下する場合がある。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、本開示の一態様に係る計算方法は、数理モデルをアニーリングマシンによって計算するためのハミルトニアンを、前記数理モデルから生成する計算方法であって、前記数理モデルにおける変数の関数と、該関数の近似式とに基づいて定式化した項を含む制約条件式に、前記関数と前記近似式との誤差に基づいて、補助変数を含む補正項を追加した、補正制約条件式を生成する補正工程と、前記数理モデルから得られる目的関数と、前記補正制約条件式とを含むハミルトニアンを生成するハミルトニアン生成工程とを含む。
【０００７】
また、本開示の一態様に係る計算装置は、数理モデルをアニーリングマシンによって計算するためのハミルトニアンを、前記数理モデルから生成する計算装置であって、前記数理モデルにおける変数の関数と、該関数の近似式とに基づいて定式化した項を含む制約条件式に、前記関数と前記近似式との誤差に基づいて、補助変数を追加した、補正制約条件式を生成する補正部と、前記数理モデルから得られる目的関数と、前記補正制約条件式とを含むハミルトニアンを生成するハミルトニアン生成部とを備える。
【０００８】
本開示の各態様に係る計算装置は、コンピュータによって実現してもよい。この場合には、コンピュータを、前記計算装置が備える各部（ソフトウェア要素）として動作させてもよい。この場合、前記計算装置をコンピュータにて実現させる計算プログラム、およびそれを記録したコンピュータ読み取り可能な記録媒体も、本開示の範疇に入る。
【発明の効果】
【０００９】
本開示の一態様によれば、制約条件式の比較項における近似式の近似の精度が低い場合であっても、アニーリングマシンによる計算の精度を向上させる。
【図面の簡単な説明】
【００１０】
【図１】本開示の実施形態に係る計算方法を説明するためのフローチャートである。
【図２】本開示の実施形態に係る計算装置のブロック図である。
【図３】本開示の実施例における制約条件である、作業時間と休憩時間との関係を示すグラフである。
【図４】本開示の実施例における、作業時間と休憩時間との関係式の近似式を示すグラフである。
【図５】本開示の実施例における、作業時間と休憩時間との関係式の近似式の補正について説明するためのグラフである。
【発明を実施するための形態】
【００１１】
〔実施形態〕
＜計算装置の概要＞
以下、本開示の一実施形態について、詳細に説明する。
【００１２】
本実施形態に係る計算方法は、ある数理モデルの系全体のエネルギーを最小化する、当該数理モデルにおける変数の組み合わせを、アニーリングマシンによって計算する方法である。本実施形態においては、上記数理モデルの系全体のエネルギーを表すハミルトニアンＨを生成し、当該ハミルトニアンＨからＱＵＢＯ行列を生成し、当該ＱＵＢＯ行列をアニーリングマシンによって解くことにより計算を行う。
【００１３】
本実施形態に係る数理モデルの計算方法について、図１および図２を参照してより詳細に説明する。図１は、本実施形態に係る数理モデルの計算方法を説明するためのフローチャートである。図２は、図１のフローチャートに示す計算方法を実行するための計算装置２のブロック図である。
【００１４】
図２に示すように、本実施形態に係る計算装置２は、アニーリングマシン４による計算を実行するためのデータを生成し、当該計算結果を蓄積および表示するための装置である。計算装置２は、操作部６と、メモリ８と、制御部１０と、通信部１２と、表示部１４とを備える。また、制御部１０は、数理モデル定式化部１６と、補正部１８と、ハミルトニアン生成部２０と、ＱＵＢＯ行列生成部２２とを備える。さらに、補正部１８は、近似式生成部２４と、誤差評価部２６と、補助変数追加部２８とを備える。
【００１５】
操作部６は、例えば、計算装置２の使用者によって操作される。例えば、操作部６は、計算装置２による計算のためのデータを外部から入力するために使用される、キーボード等を含んでいてもよい。例えば、操作部６は、数理モデルの各パラメータ、または、数理モデルを計算する際の設定等を行うためのデータを入力するために使用されてもよい。
【００１６】
メモリ８は、計算装置２の備える各部から入力されたデータを少なくとも一時的に記憶する。メモリ８が記憶するデータは、計算装置２の備える各部から適宜読み出される。
【００１７】
制御部１０は、計算装置２に入力された、数理モデルのパラメータ、および、計算の設定に基づいて、アニーリングマシン４による計算を実行するためのデータを生成する。制御部１０の各部の詳細な動作は、本実施形態に係る計算方法についての説明と併せ、後により詳細に説明する。
【００１８】
通信部１２は、メモリ８から読み出したデータの少なくとも一部を、計算装置２の外部機器へ送信し、当該外部機器から送信されたデータを受信し、メモリ８に記録するための通信装置である。本実施形態において、通信部１２は、アニーリングマシン４とデータの相互通信が可能である。
【００１９】
表示部１４は、メモリ８からの読み出したデータの少なくとも一部を、計算装置２の使用者等に表示するための装置である。例えば、表示部１４は、計算装置２に入力されたデータ、計算装置２の計算の設定、または、アニーリングマシン４による計算の結果等を表示するモニタであってもよい。
【００２０】
＜数理モデルの定式化＞
本実施形態に係る数理モデルの計算方法においては、はじめに、数理モデルを定式化する（ステップＳ２）。ステップＳ２においては、例えば、はじめに、計算装置２の使用者が、操作部６によって、計算したい数理モデルの各パラメータを計算装置２に入力する。入力された数理モデルの各パラメータは、メモリ８に一時的に記録されてもよい。入力された数理モデルの各パラメータは、次いで、制御部１０の数理モデル定式化部１６に読み出される。
【００２１】
数理モデル定式化部１６は、メモリ８から読み出したデータを解析し、数理モデルを表す式を生成し、当該式をＱＵＢＯモデルに沿って定式化した式に変換する。数理モデル定式化部１６は、例えば、目的関数ＨＯと、数理モデルにおける制約条件を定式化した制約条件式ＨＬとを生成する。
【００２２】
数理モデルの定式化は、例えば、制約条件式ＨＬに対応する制約条件を満たす範囲内において、目的関数ＨＯが最小となる場合、元の数理モデルにおいて最適な組み合わせが得られるように、目的関数ＨＯおよび制約条件式ＨＬを決定することにより実行される。目的関数ＨＯがＱＵＢＯモデルを定式化した式である場合、目的関数ＨＯは、例えば、下記式（１）によって表現される。
【００２３】
【数１】
0006985479.tif 000002
【００２４】
式（１）において、ｘｐは、０または１の値を取るバイナリ変数である。また、ａｐおよびｂｐｑは、それぞれ、１次の項および２次の項の係数である。また、ｐ、ｑ、およびｒは自然数である。また、ｒは、第１の数理モデルにおける各変数の取り得る組み合わせの総数に対応する。スピン変数ｓｐ＝±１を用いて、ｘｐ＝（ｓｐ＋１）／２と表現できることから、目的関数ＨＯは、イジングモデルのエネルギー関数と等価である。
【００２５】
制約条件式ＨＬは、例えば、係数Ｃｓ等を用いて、以下の式（２）のように表現できる。
【００２６】
【数２】
0006985479.tif 000003
【００２７】
ここで、Ｌｓは、それぞれ、制約条件を定式化した制約条件項である。制約条件項Ｌｓは、元の数理モデルにおける各変数の値が、制約条件を満たさない組み合わせの場合に増大する項である。これにより、元の数理モデルにおける制約条件が満たされない場合に、系全体のエネルギーを増大させて、解として採用されないように設定することが可能である。なお、式（２）におけるｋは自然数であり、数理モデルにおける制約条件の個数に相当する。
【００２８】
＜制約条件の定式化および近似＞
本実施形態において、数理モデルの制約条件の少なくとも一つが、数理モデルにおけるある変数ｘと、変数ｘと異なる変数ｙとの関数によって表現されるとする。ここで、変数ｘおよび変数ｙのそれぞれは、数理モデルにおける、ある要素の値を表現する変数であり、各バイナリ変数ｘｐの値によって値が変動する変数である。換言すれば、変数ｘおよび変数ｙのそれぞれは、バイナリ変数ｘｐを変数とする関数であり、例えば、ｘ＝ｆ（ｘｐ）、ｙ＝ｇ（ｘｐ）と表現することができる。
【００２９】
この場合、制約条件式ＨＬの少なくとも一つの制約条件項Ｌｓは、上述した制約条件を表す関数に、変数ｘの値を代入して得られる変数ｙの値と、実際の変数ｙの値との差を比較する比較項Ｄとなる。本実施形態において、制約条件項Ｌｓのうちの一つである制約条件項Ｌが、比較項Ｄである場合、当該比較項Ｄは、例えば、下記式（３）によって表される。
【００３０】
【数３】
0006985479.tif 000004
【００３１】
ここで、関数ｈ（ｘ）は、数理モデルの制約条件に含まれる、変数ｘと変数ｙとの関係式である。本実施形態において、関数ｈ（ｘ）は、変数をｘとする関数であり、関数ｈ（ｘ）＝ｙが成立する場合、変数ｘと変数ｙとが制約条件を満たす値となっているとする。なお、変数ｘと変数ｙとは、バイナリ変数ｘｐを変数とする関数であるため、関数ｈ（ｘ）についても、バイナリ変数ｘｐの変数として表現できる。
【００３２】
この場合、比較項Ｄは、変数ｙと関数ｈ（ｘ）との差を二乗した項である。換言すれば、変数ｙの値と、上述した関係式に、変数ｘを代入して得られる値との差が小さい程、値が小さくなる項である。これにより、比較項Ｄは、実際の変数ｘと変数ｙとの値が、制約条件を満たす場合に、値が小さくなる項となる。このため、実際の変数ｘの値と変数ｙの値との組み合わせが、制約条件を満たさない場合に、系全体のエネルギーを上昇させて、当該組み合わせが解として採用されないように設定することが可能である。
【００３３】
＜比較項の制約および関数の近似＞
ここで、一般に、ＱＵＢＯモデルは、イジングモデルを変形したモデルであり、二体相互作用までの作用を考慮している。このため、ＱＵＢＯモデルは、三体以上の相互作用を前提としていないため、数理モデルをＱＵＢＯモデルに変形して計算を行う場合、最終的に得られるハミルトニアンが、三次以上の項を含まないことが求められる。
【００３４】
上記式（３）から明らかであるように、比較項Ｄには、ｈ（ｘ）を二乗した項が含まれる。このため、比較項Ｄが二次以下の式であるためには、比較項Ｄの括弧内に含まれるｈ（ｘ）は、一次式である必要がある。また、ｈ（ｘ）は、例えば、不等式によって表されるような、不連続な関数ではなく、変数ｘの全範囲において、連続した関数である必要がある。
【００３５】
本実施形態においては、ｈ（ｘ）が、二次以上の関数、または、不連続な関数であったとする。ここで、比較項Ｄを生成するために、本実施形態においては、ステップＳ２に次いで、制約条件を表現する関数の近似式を生成する（ステップＳ４）。ステップＳ４は、数理モデル定式化部１６により得られた、制約条件を表現する関数を、補正部１８の近似式生成部２４に入力し、近似式を生成させることにより得られる。
【００３６】
上記式（３）におけるｈ（ｘ）を、１次式に近似した場合、上記式（３）は、下記式（４）に変形される。
【００３７】
【数４】
0006985479.tif 000005
【００３８】
上記式（４）において、ＡおよびＢはそれぞれ定数である。すなわち、比較項Ｄに含まれるｈ（ｘ）の近似式は、下記式（５）にて表される。
【００３９】
【数５】
0006985479.tif 000006
【００４０】
ステップＳ４において、１次の近似式を用いた近似を行わざるを得ないために、制約条件を表すための関数によっては、当該関数と近似式との差異が非常に大きくなる場合がある。
【００４１】
＜誤差の評価および近似式の補正＞
上記関数と、その近似式との差異を低減するために、本実施形態においては、近似式の補正を行う。近似式の補正工程においては、はじめに、ステップＳ４により得られた近似式の値と、上述した制約条件を表現する関数との誤差を評価する（ステップＳ６）。ステップＳ６は、近似式生成部２４から、誤差評価部２６に、比較項Ｄのデータを入力し、比較項Ｄを評価させることにより実行される。
【００４２】
次いで、ステップＳ６において実行された、関数とその近似式との誤差の評価に基づいて、比較項Ｄに、新たな補助変数Ｋを含む項を追加し（ステップＳ８）、補正比較項Ｄ’を生成する。ステップＳ８は、例えば、誤差評価部２６における、比較項Ｄの評価に基づいて、補助変数追加部２８が、比較項Ｄに追加する、補助変数Ｋを含む適切な項を決定することにより実行される。
【００４３】
例えば、本実施形態においては、比較項Ｄに、新たな補助変数Ｋを含む、第１の補正項である補正項Ｅと、第２の補正項である補正項Ｆとを追加する。具体的には、上述した比較項Ｄを下記式（６）に示す補正比較項Ｄ’に変形する。これに伴い、下記式（６）に示すように制約条件項Ｌについても、補正制約条件項Ｌ’に変形される。
【００４４】
【数６】
0006985479.tif 000007
【００４５】
ここで、補正項Ｅおよび補正項Ｆを、係数Ｐｌ、係数Ｑｌを用いて、それぞれ、下記式（７）および下記式（８）とする。
【００４６】
【数７】
0006985479.tif 000008
【００４７】
【数８】
0006985479.tif 000009
【００４８】
ここで、補助変数Ｋｌは、０または１の値を取るバイナリ変数であり、ｘの値によって変化する変数である。ＰｌおよびＱｌは、各補助変数Ｋｌに対する係数である。このため、補正項Ｅは、ｈ（ｘ）に定数Ｐｌと補助変数Ｋｌとの積を追加し、ｈ（ｘ）を補正するための項である。
【００４９】
また、補正項Ｆは、補正制約条件項Ｌ’を含むハミルトニアンを用いて、量子アニーリングが実行された際、その計算過程において、補助変数Ｋｌの値が不適切な場合に、値が大きくなるように設定されている。例えば、変数ｘの値、および補正項Ｅの値によっては、元の関数の値と、近似式の値とに、大きな差異が生じる場合がある。このような場合、補正項Ｆの値は大きくなるように設定されている。
【００５０】
したがって、関数の値と近似式の値との差異が大きく、補正項Ｅの値が不適切な場合に、補正項Ｆの値が大きくなることにより、補正比較項Ｄ’の値が大きくなり、解として採用されないように設定できる。換言すれば、補正項Ｆは、変数ｘの値に対し、補正項Ｅによりｈ（ｘ）に追加された定数の値が適切な場合に、値が小さくなる項である。ゆえに、補正項Ｅおよび補正項Ｆを導入した補正比較項Ｄ’は、上述した関数とその近似式との誤差を、より効率よく低減できる。これにより、制約条件式ＨＬは、補正制約条件項Ｌ’を含む補正制約条件式ＨＬ’に変形される。
【００５１】
なお、式（６）、式（７）、および式（８）において、ｌ、ｍ、ｎのそれぞれは、自然数である。ｍおよびｎは、それぞれ、補正項Ｅおよび補正項Ｆにおける、補助変数Ｋｌを含む項の個数に相当する。ｍおよびｎの値が大きい程、変数ｘの各値に対する補正項Ｅおよび補正項Ｆの値を、より厳密に設定することができるため、補正比較項Ｄ’がより厳密に補正される。
【００５２】
＜ハミルトニアンおよびＱＵＢＯ行列の生成＞
ステップＳ８に次いで、目的関数ＨＯと、補助変数Ｋを追加された補正制約条件項Ｌ’を含む、補正制約条件式ＨＬ’とを合成して、ハミルトニアンＨを生成する（ステップＳ１０）。ハミルトニアンＨは、例えば、Ｈ＝ＨＯ＋ＨＬ’にて表される。ステップＳ１０においては、はじめに、ハミルトニアン生成部２０に、補正部１８から、目的関数ＨＯと、補助変数Ｋの項が追加された補正制約条件式ＨＬ’のデータとを、それぞれ入力する。次いで、目的関数ＨＯと補正制約条件式ＨＬ’とを合成して、数理モデルの系全体のエネルギーを表現するハミルトニアンＨを生成する。
【００５３】
次いで、ステップＳ１０において得られたハミルトニアンＨから、ＱＵＢＯ行列を生成する（ステップＳ１２）。ステップＳ１２は、ハミルトニアン生成部２０によって生成されたハミルトニアンＨを、ＱＵＢＯ行列生成部２２に入力することにより実行される。ＱＵＢＯ行列は、ハミルトニアンＨをＱＵＢＯモデルの行列によって表現する上三角行列である。ハミルトニアンＨからのＱＵＢＯ行列の生成は、一般に用いられる、ハミルトニアンＨをＱＵＢＯ行列に変換する手法を採用できる。これにより、アニーリングマシンによって計算可能なＱＵＢＯ行列が生成される。生成されたＱＵＢＯ行列は、一時的にメモリ８に記録されてもよい。
【００５４】
次いで、ステップＳ１２において生成されたＱＵＢＯ行列を、アニーリングマシン４に入力し、アニーリングマシン４を用いて当該ＱＵＢＯ行列に対する量子アニーリングを実行する（ステップＳ１４）。ステップＳ１４においては、はじめに、通信部１２が、メモリ８からＱＵＢＯ行列のデータを読み出し、アニーリングマシン４に送信する。ＱＵＢＯ行列のデータを受信したアニーリングマシン４は、ＱＵＢＯ行列のデータを受信して、当該ＱＵＢＯ行列に対する量子アニーリングを実行する。
【００５５】
これにより、生成されたＱＵＢＯ行列に対する、量子アニーリングの解が得られる。当該量子アニーリングによって得られた解は、理想的には、数理モデルの変数の組み合わせのうち、制約条件を満たす範囲内において、目的関数の値を最小化する変数の組み合わせであり、数理モデルにおける最適解となる。
【００５６】
アニーリングマシン４による計算の結果は、通信部１２に送信される。アニーリングマシン４による計算の結果を受信した通信部１２は、当該結果をメモリ８に記録する。アニーリングマシン４による計算の結果は、表示部１４によって読みだされ、表示部１４に表示されてもよい。これにより、数理モデルの系全体のエネルギーを最小化する変数の組み合わせが最適解として得られる。
【００５７】
＜本実施形態に係る計算方法の奏する効果＞
本実施形態に係る計算方法によれば、補正制約条件式ＨＬ’に含まれる補正比較項Ｄ’が、制約条件を表現する関数とその近似式との誤差を低減する補助変数Ｋを含む。このため、補正比較項Ｄ’が含む近似式が、１次の近似式であった場合でも、上記関数と、その近似式との誤差が低減する。このため、本実施形態に係る計算方法によって得られた解が、制約条件を満たし、かつ、最適性を有する蓋然性が向上し、計算精度が向上する。
【００５８】
本実施形態に係る計算方法によって計算される数理モデルは、例えば、レイバースケジューリングモデルであってもよい。以下、本実施形態に係る計算方法によって、レイバースケジューリングモデルを計算する具体的手法を、実施例として説明する。
【実施例】
【００５９】
＜レイバースケジューリングモデル＞
本実施例に係るレイバースケジューリングモデルは、例えば、各作業者に、どの日の、どの時間帯に、どの作業を割り当てるかの組み合わせを決定するためのモデルである。レイバースケジューリングモデルにおいては、例えば、各作業者の、１つの時間帯あたりに係る人件費と、各作業者の作業時間との積の合計値を目的関数としてもよい。または、レイバースケジューリングモデルにおいては、例えば、各作業者が希望する休日が実現しなかった場合に値が増大する関数を目的関数としてもよい。あるいは、これらの目的関数を組み合わせたものを、目的関数として採用してもよい。これにより、例えば、総人件費を最低限に抑えつつ、かつ、各作業者の希望する休暇日を可能な限り実現したスケジュールを決定することができる。
【００６０】
＜レイバースケジューリングモデルの制約条件＞
ここで、本実施例に係るレイバースケジューリングモデルにおいては、制約条件の一つとして、一日の作業時間と休憩時間との関係式を採用する。本実施例において採用される、一日の作業時間と休憩時間との関係を、図３のグラフに示す。
【００６１】
図３のグラフにおいて、横軸は、ある一日における、休憩時間を除く作業を行った合計時間を、単位を時間（ｈ）として表す。図３のグラフにおいて、縦軸は、ある一日において、取るべき休憩時間の長さを、単位を分（ｍ）として表す。なお、本明細書におけるグラフは、何れも、各軸の定義および縮尺が、図３のグラフと同一である。
【００６２】
本実施例に係るレイバースケジューリングモデルにおいては、ある作業者が、休憩時間を除く作業をａ時間以上行った場合、当該作業者は、必ずｂ分の休憩を取らなければならないとする。さらに、本実施形態に係るレイバースケジューリングモデルにおいては、ある作業者が、休憩時間を除く作業をｃ時間以上行った場合、当該作業者は、計ｅ分の休憩を取らなければならないとする。このため、上述した制約条件を表す関数を、休憩を除く作業時間を変数とした、必要な休憩時間の関数とすると、当該関数は、図３に示す階段関数となる。
【００６３】
＜制約条件の定式化および近似＞
ここで、バイナリ変数ｘｉ，ｄ，ｔ，ｗを定義する。ここで、バイナリ変数ｘｉ，ｄ，ｔ，ｗは、作業者ｉが、ｄ日に、時間帯ｔにおいて、ｗの作業をする場合に１となり、そうでない場合に０となるとする。ここで、ある一日における、休憩を除く全ての作業時間を含む集合をＴとする。また、ある作業者が休憩を取る場合、ｗ＝Ｒとする。さらに、当該作業者の休憩を除く全ての作業を含む作業の集合をＷとする。
【００６４】
図３に示す制約条件を定式化した場合、以下の式（９）、式（１０）、および式（１１）が得られる。
【００６５】
【数９】
0006985479.tif 000010
【００６６】
【数１０】
0006985479.tif 000011
【００６７】
【数１１】
0006985479.tif 000012
【００６８】
図３に示すように、本実施例における制約条件を表す関数は、３段の階段関数となる。したがって、上記制約条件から比較項Ｄを設定する場合、当該階段関数に対する、１次の近似式を設定する必要がある。ここで、図３に示す、３段の階段関数を、１次の近似式に近似する場合、関数の２つ不連続点のそれぞれにおいて、当該不連続点の前後における関数の値の中点となる２点を通る直線を設定することが考えられる。具体的には、本実施例において、図４に一点鎖線にて示す、座標（ａ，ｂ／２）および座標（ｃ，（ｂ＋ｅ）／２）の２点を通る直線を、１次の近似式として設定する。
【００６９】
＜近似式の補正＞
当該近似式は、休憩を除く作業時間が、ａ時間程度またはｃ時間程度の場合において、元の階段関数との誤差が比較的小さくなる。しかしながら、上記近似式は、休憩を除く作業時間が、０時間付近である場合には、元の階段関数との誤差が非常に大きくなる場合がある。本実施例においては、制約条件をＱＵＢＯ式に定式化し、比較項Ｄを生成する際に、上記事情を考慮して、補助変数Ｋを含む補正項Ｅおよび補正項Ｆを、比較項Ｄに追加する。
【００７０】
具体的には、式（９）、式（１０）、および式（１１）と、式（６）、式（７）、および式（８）とから、比較項Ｄを定義する、以下の式（１２）を生成する。
【００７１】
【数１２】
0006985479.tif 000013
【００７２】
なお、式（１２）における、係数Ａおよび係数Ｂは、以下の式（１３）、および式（１４）によって定義される。
【００７３】
【数１３】
0006985479.tif 000014
【００７４】
【数１４】
0006985479.tif 000015
【００７５】
ここで、式（１４）において、εは小さな定数である。また、本実施例においては、式（７）、および式（８）における、ｍおよびｎの値を１とした。
【００７６】
ここで、補助変数Ｋが０である場合、補正項Ｅが０となるため、比較項Ｄにおける近似式は、図５に一点鎖線にて示す式となり、図４に一点鎖線にて示す式と略同一となる。一方、補助変数Ｋが１である場合、比較項Ｄにおける近似式に、補正項Ｅ＝Ｐ１が定数として追加される。したがって、補助変数Ｋが１である場合、比較項Ｄにおける近似式は、図５に二点鎖線にて示す１次式に変換される。
【００７７】
補正項Ｅが定数として追加された近似式は、補正項Ｅが０である近似式と比較して、休憩を除く作業時間が０時間付近である場合に、元の階段関数との誤差が小さくなる。一方、補正項Ｅが定数として追加された近似式は、補正項Ｅが０である近似式と比較して、休憩を除く作業時間がａ時間付近、あるいはそれ以上である場合に、元の階段関数との誤差が大きくなる。
【００７８】
ここで、補正項Ｆは、休憩時間が０時間である場合には値が小さくなる。また、Ｑ１を十分に大きく設定することにより、補正項Ｆは、休憩時間がある時間以上である場合には値が大きくなるように設定される。したがって、アニーリングマシン４による計算過程においては、比較項Ｄを小さくする観点から、休憩を除く作業時間が０時間付近である場合には、Ｋ＝１が、休憩を除く作業時間がある時間以上である場合には、Ｋ＝０が、適切な値として自ずと選択される。このため、アニーリングマシン４による、比較項Ｄの計算の精度が向上する。
【００７９】
＜補記＞
本実施例においては、数理モデルがレイバースケジューリングモデルである場合について説明した。しかしながら、これに限られず、本実施形態に係る計算方法は、数理モデルにおける制約条件を表す関係式が、１次式に近似できる場合には、適用することができる。この場合、上記関係式およびその近似式によって、上述した式（７）および式（８）における、ｍ、ｎ、Ｐｌ、Ｑｌの値を適切に設定することにより、比較項Ｄを適宜補正することができる。
【００８０】
＜ソフトウェアおよびプログラムによる実施例＞
本実施形態に係る数理モデル定式化部１６、補正部１８、ハミルトニアン生成部２０、およびＱＵＢＯ行列生成部２２は、計算装置２が備える集積回路、換言すれば、ＩＣチップ等に形成された論理回路、換言すれば、ハードウェアによって実現してもよい。あるいは、数理モデル定式化部１６、補正部１８、ハミルトニアン生成部２０、およびＱＵＢＯ行列生成部２２は、ソフトウェアによって実現してもよい。
【００８１】
上記各部がソフトウェアである場合、アニーリングマシン４と通信可能な端末において、各部の機能を実現するソフトウェアであるプログラムの命令を実行してもよい。より具体的には、当該プログラムの命令を実行することにより、数理モデル定式化部１６、補正部１８、ハミルトニアン生成部２０、およびＱＵＢＯ行列生成部２２における処理が実行されてもよい。この端末は、例えば１つ以上のプロセッサを備えていると共に、上記プログラムを記憶した端末読み取り可能な記録媒体を備えている。上記端末において、上記プロセッサが上記プログラムを上記記録媒体から読み取って実行することにより、本開示の目的が達成される。したがって、上記プログラムは、数理モデル定式化部１６、補正部１８、ハミルトニアン生成部２０、およびＱＵＢＯ行列生成部２２における処理を実行する、計算プログラムとして機能する。
【００８２】
上記プロセッサとしては、例えばＣＰＵ（Central Processing Unit）を用いることができる。上記記録媒体としては、「一時的でない有形の媒体」、例えば、ＲＯＭ（Read Only Memory）等の他、テープ、ディスク、カード、半導体メモリ、プログラマブルな論理回路などを用いることができる。また、上記プログラムを展開するＲＡＭ（Random Access Memory）などをさらに備えていてもよい。
【００８３】
上記プログラムは、該プログラムを伝送可能な任意の伝送媒体（通信ネットワークや放送波等）を介して上記端末に供給されてもよい。なお、本開示の一態様は、上記プログラムが電子的な伝送によって具現化された、搬送波に埋め込まれたデータ信号の形態でも実現され得る。
【００８４】
本開示は上述した実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、実施形態にそれぞれ開示された異なる技術的手段を適宜組み合わせて得られる実施形態についても本開示の技術的範囲に含まれる。
【符号の説明】
【００８５】
２    計算装置
１０  制御部
１６  数理モデル定式化部
１８  補正部
２０  ハミルトニアン生成部
２２  ＱＵＢＯ行列生成部
２４  近似式生成部
２６  誤差評価部
２８  補助変数追加部
【要約】
【課題】制約条件式の比較項における近似式の近似の精度が低い場合であっても、アニーリングマシンによる計算の精度を向上させる。
【解決手段】計算方法は、補正工程（Ｓ６、Ｓ８）と、ハミルトニアン生成工程（Ｓ１０）とを含む。補正工程においては、数理モデルにおける変数の関数と、該関数の近似式とに基づいて定式化した項を含む制約条件式に、関数と近似式との誤差に基づいて、補助変数を含む補正項を追加した、補正制約条件式を生成する。ハミルトニアン生成工程においては、数理モデルから得られる目的関数と、補正制約条件式とを含むハミルトニアンを生成する。
【選択図】図１【図１】
0006985479.tif 000016
【図２】
0006985479.tif 000017
【図３】
0006985479.tif 000018
【図４】
0006985479.tif 000019
【図５】
0006985479.tif 000020