(57)【要約】２値多項的に制約された多項計画問題（ＢＰＣＰＰＰ、binary polynomially constrained polynomial programming problem）のラグランジュ双対を解くための方法及びシステムを開示する。方法は、ＢＰＣＰＰＰを取得するステップと；収束が検出されるまでは反復的に、ラグランジュ乗数のセットを提供し、これらのラグランジュ乗数におけるＢＰＣＰＰＰのラグランジュ緩和を表す制約無しの２値２次計画問題（ＵＢＱＰＰ、unconstrained binary quadratic programming problem）を提供し、ＵＢＱＰＰを２値オプティマイザに提供し、２値オプティマイザから少なくとも１つの対応する解を取得し、少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと；収束後に、対応する知られている最良の主双対及び知られている最良の実行可能解の全てを提供するステップとを含む。【選択図】図１
2019512134.tif 000002
【特許請求の範囲】
【請求項１】
２値多項的に制約された多項計画問題 のラグランジュ双対を解くための方法であって、該方法は、
処理装置を用いて：
２値多項的に制約された多項計画問題 を取得するステップと；
収束が検出されるまでは反復的に、
ラグランジュ乗数のセットを提供し、
提供されたラグランジュ乗数の前記セットにおける 前記２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、
前記制約無しの２値２次計画問題 を２値オプティマイザに提供し、
前記２値オプティマイザから少なくとも１つの対応する解を取得し、
前記少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと；
収束後に、対応する 前記２値多項的に制約された多項計画問題 の前記ラグランジュ双対の知られている最良の主双対及び 前記２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するステップ
とを行わせることを含む、方法。
【請求項２】
請求項１に記載の方法において、前記２値多項的に制約された多項計画問題を取得するステップは、
多項式たる目的関数を表すデータを取得することと、
多項等式制約を表すデータを取得することと、
多項不等式制約を表すデータを取得すること
とを含む、方法。
【請求項３】
請求項１〜２のいずれか１つに記載の方法において、前記２値多項的に制約された多項計画問題は、ユーザ、コンピュータ、ソフトウェアパッケージ及びインテリジェントエージェントの少なくとも１つから取得される、方法。
【請求項４】
請求項１〜３のいずれか１つに記載の方法において、前記２値多項的に制約された多項計画問題を取得するステップは、ソフトウェアパラメータを初期化すること及びステップサイズサブルーチンを取得することをさらに含む、方法。
【請求項５】
請求項４に記載の方法において、前記ソフトウェアパラメータを初期化することは、
前記２値多項的に制約された多項計画問題の一般的ラグランジュ緩和の一般的次数低減形式を、元の変数及び補助変数を用いて前記ラグランジュ乗数でパラメータ化した２値２次関数についてのパラメータ化ファミリとして提供することを含む、方法。
【請求項６】
請求項４に記載の方法において、前記ソフトウェアパラメータを初期化することは、
前記２値多項的に制約された多項計画問題の前記一般的ラグランジュ緩和の前記一般的次数低減形式についての一般的埋め込みを提供することと、
解についてのリストを提供するための埋め込みソルバ関数を提供することと、
ラグランジュ乗数について初期値及びデフォルト値の内の１つを提供することと、
収束条件に関して誤差許容値を提供することと、
総反復回数についての制限値及び非改善反復回数についての制限値を表す整数を提供すること
とをも含む、方法。
【請求項７】
請求項１に記載の方法において、前記２値多項的に制約された多項計画問題の初期ラグランジュ緩和は初期のラグランジュ乗数のセットを用いて生成される、方法。
【請求項８】
請求項１に記載の方法において、前記少なくとも１つの対応する解を用いて前記２値多項的に制約された多項計画問題のラグランジュ双対の劣勾配を生成する、方法。
【請求項９】
請求項１に記載の方法において、前記少なくとも１つの対応する解を用いて、前記２値多項的に制約された多項計画問題のラグランジュ双対についての線形再定式化のための少なくとも１つの外側近似切断を生成する、方法。
【請求項１０】
請求項１〜９のいずれか１つに記載の方法において、前記２値多項的に制約された多項計画問題のラグランジュ双対への対応する解の提供は、前記対応する解をファイルに格納することを含む、方法。
【請求項１１】
デジタルコンピュータであって：
中央処理装置と；
表示装置と；
前記デジタルコンピュータを２値オプティマイザに動作可能に接続するための通信ポートと；
２値多項的に制約された多項計画問題 のラグランジュ双対を解くためのアプリケーションを含むメモリ部であって、該アプリケーションは：
２値多項的に制約された多項計画問題を取得するための命令と；
反復的に、ラグランジュ乗数のセットを提供し、これらのラグランジュ乗数における 前記２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、前記通信ポートを用いて 前記制約無しの２次計画問題 を前記２値オプティマイザへと提供し；前記通信ポートを介して前記２値オプティマイザから少なくとも１つの対応する解を取得し、前記少なくとも１つの対応する解を用いて収束が検出されるまで新たなラグランジュ乗数のセットを生成するための命令と、
収束が検出された後に、対応する 前記２値多項的に制約された多項計画問題 のラグランジュ双対の知られている最良の主双対及び 前記２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するための命令
とを含む、メモリ部と；
前記中央処理装置と前記表示装置と前記通信ポートと前記メモリ部とを相互接続するためのデータバス
とを含む、デジタルコンピュータ。
【請求項１２】
請求項１１に記載のデジタルコンピュータにおいて、前記２値オプティマイザは量子アニーラを含む、デジタルコンピュータ。
【請求項１３】
コンピュータ実行可能命令を格納するための不揮発性コンピュータ可読記憶媒体であって、該命令を実行すると、２値多項的に制約された多項計画問題 のラグランジュ双対を解くための方法をデジタルコンピュータに行わせるのであり、該方法は：
２値多項的に制約された多項計画問題を取得するステップと、
収束が検出されるまでは反復的に：
ラグランジュ乗数のセットを提供し、
これらのラグランジュ乗数における 前記２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、
前記制約無しの２次計画問題 を２値オプティマイザへと提供し、
前記２値オプティマイザから少なくとも１つの対応する解を取得し、
前記少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと、
収束が検出された後に、対応する 前記２値多項的に制約された多項計画問題 のラグランジュ双対の知られている最良の主双対及び 前記２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するステップ
とを含む、媒体。
【請求項１４】
請求項１３に記載の不揮発性コンピュータ可読記憶媒体において、前記２値オプティマイザは量子アニーラを含む、媒体。
【請求項１５】
２値多項的に制約された多項計画問題 のラグランジュ双対を解くための方法であって、該方法は：
２値多項的に制約された多項計画問題 を取得するステップと；
収束が検出されるまでは反復的に、
ラグランジュ乗数のセットを提供し、
提供されたラグランジュ乗数の前記セットにおける 前記２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、
前記制約無しの２値２次計画問題 を２値オプティマイザに提供し、
前記２値オプティマイザから少なくとも１つの対応する解を取得し、
前記少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと；
収束後に、対応する 前記２値多項的に制約された多項計画問題 の前記ラグランジュ双対の知られている最良の主双対及び 前記２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するステップ
とを含む、方法。
【請求項１６】
請求項１〜１０及び１５のいずれか１つに記載の方法において、前記２値オプティマイザは量子アニーラを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してコンピューティングに関する。より正確には、本発明は２値多項的に制約された多項計画問題に対応するラグランジュ双対問題を２値オプティマイザ（binary optimizer）を用いて解くための方法及びシステムに関する。
【０００２】
関連出願の相互参照
本願は、２０１６年２月２３日に出願されたカナダ国特許出願第２，９２１，７１１号及び２０１６年２月２３日に出願された米国特許出願第１５／０５１，２７１号の優先権を主張する。
【０００３】
本願は、カナダ国特許第２，８８１，０３３号に関連する。
【背景技術】
【０００４】
２次２値計画問題（quadratic binary programming problem）のラグランジュ双対（Lagrangian dual）及び双対性（duality）についての背景情報は、特許文献１に見出され得る。
【０００５】
双対性理論においては、双対化及び双対問題について幾つかの異なるタイプが提案されている。双対問題の１つのタイプとしてはラグランジュ双対問題が挙げられる。ラグランジュ双対性理論についての詳細な説明は非特許文献１において開示されている。離散的最適化においてのラグランジュ手法の応用については、非特許文献２及び非特許文献３を参照されたい。
【０００６】
ラグランジュ双対問題を解くための方法としては幾つかの方法が提唱されており、例えば非特許文献１の第３章に開示されているように、劣勾配法、外側ラグランジュ線形化法、及びバンドル法等が挙げられる。これらのアルゴリズムにおいて効率的な実装を得るに際しての困難は、これらの方法の様々な段階において困難な非線形整数計画問題を解くための効率的な方法を見つけたいという願望に関連して生ずる。例えば、単一制約２次０−１ナップサック問題は、非特許文献１の§１１．５にて説明されているように、ラグランジュ双対性に基づいた効率的な分枝限定法を用いて解くことができる。しかし、提案された方法は多次元ナップサック問題へと一般化することはできない。
【０００７】
特許文献１は、制約された２次計画問題のラグランジュ双対を量子アニーラを用いて解くための方法を開示する。開示されている方法は、外側ラグランジュ線形化方法に基づいている。残念ながら、量子アニーラと共に用いた際の当該方法の限界としては、処理中に変異性の制約無し２次最適化問題（error-prone unconstrained quadratic optimization problem）が顕在化し得ることが挙げられる。
【０００８】
上記特定された欠点の少なくとも１つを克服するような、ラグランジュ双対最適化問題（Lagrangian dual optimization problem）を解くための方法及びシステムが必要とされる。
【０００９】
本願明細書の開示事項、図面及び後述の本発明についての説明を参照することによって本発明の特徴が明らかとなる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】カナダ国特許第２，８８１，０３３号
【特許文献２】米国特許出願第２００６／０２２５１６５号
【特許文献３】米国特許出願第２００８／０２１８５１９号
【特許文献４】米国特許第８，６５５，８２８号
【非特許文献】
【００１１】
【非特許文献１】“Nonlinear integer programming”、Duan Li and Xiaoling Sun
【非特許文献２】“A survey of Lagrangean techniques for discrete optimization”、Jeremy F. Shapiro、Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts
【非特許文献３】“Lagrangean relaxation for integer programming”、A.M. Geoffrion、Mathematics Programming Study 2 (1974) 82 114、North-Holland Publishing Company
【非特許文献４】Farhi, E. et al.、“Quantum Adiabatic Evolution Algorithms versus Simulated Annealing”、arXiv.org:quant ph/0201031 (2002)
【非特許文献５】McGeoch, Catherine C. and Cong Wang, (2013)、“Experimental Evaluation of an Adiabiatic Quantum System for Combinatorial Optimization” Computing Frontiers”、2013年5月14, 16日、(http://www.cs.amherst.edu/ccm/cf14-mcgeoch.pdf)
【非特許文献６】“A practical heuristic for finding graph minors”、Jun Cai, William G. Macready, Aidan Roy
【発明の概要】
【００１２】
広範な態様によれば、次の方法が開示されている：即ち、２値多項的に制約された多項計画問題（ＢＰＣＰＰＰ、binary polynomially constrained polynomial programming problem）のラグランジュ双対を解くための方法であって、該方法は、処理装置を用いて：２値多項的に制約された多項計画問題 を取得するステップと；収束が検出されるまでは反復的に、ラグランジュ乗数のセットを提供し、提供されたラグランジュ乗数のセットにおける ２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、制約無しの２値２次計画問題（ＵＢＱＰＰ、unconstrained binary quadratic programming problem）を２値オプティマイザに提供し、２値オプティマイザから少なくとも１つの対応する解を取得し、少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと；収束後に、対応する ２値多項的に制約された多項計画問題 のラグランジュ双対の知られている最良の主双対及び ２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するステップとを行わせることを含む、方法。
【００１３】
広範な態様によれば、次の方法が開示されている：即ち、２値多項的に制約された多項計画問題のラグランジュ双対を解くための方法であって、２値多項的に制約された多項計画問題を取得するステップと、収束が検出されるまでは反復的に：ラグランジュ乗数のセットを提供し、これらのラグランジュ乗数における ２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、制約無しの２次計画問題 を２値オプティマイザへと提供し、２値オプティマイザから少なくとも１つの対応する解を取得し、少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと、収束が検出された後に、対応する ２値多項的に制約された多項計画問題 のラグランジュ双対の知られている最良の主双対及び ２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するステップとを含む、方法。
【００１４】
実施形態によれば、２値多項的に制約された多項計画問題の取得は、多項式たる目的関数を表すデータを取得することと、多項等式制約を表すデータを取得することと、多項不等式制約を表すデータを取得することとを含む。
【００１５】
実施形態によれば、２値多項的に制約された多項計画問題は、ユーザ、コンピュータ、ソフトウェアパッケージ及びインテリジェントエージェントの少なくとも１つから取得される。
【００１６】
実施形態によれば、２値多項的に制約された多項計画問題を取得するステップは、ソフトウェアパラメータを初期化すること及びステップサイズサブルーチンを取得することをさらに含む。
【００１７】
実施形態によれば、ソフトウェアパラメータを初期化することは、２値多項的に制約された多項計画問題の一般的ラグランジュ緩和の一般的次数低減形式（ＧＤＲＦ、generic degree reduced form）を、元の変数及び補助変数を用いてラグランジュ乗数でパラメータ化した２値２次関数についてのパラメータ化ファミリとして提供することを含む。
【００１８】
実施形態によれば、ソフトウェアパラメータを初期化することは、２値多項的に制約された多項計画問題の一般的ラグランジュ緩和の一般的次数低減形式についての一般的埋め込みを提供することと、解についてのリストを提供するための埋め込みソルバ関数を提供することと、ラグランジュ乗数について初期値及びデフォルト値の内の１つを提供することと、収束条件に関して誤差許容値を提供することと、総反復回数についての制限値及び非改善反復回数についての制限値を表す整数を提供することとを含む。
【００１９】
実施形態によれば、２値多項的に制約された多項計画問題の初期ラグランジュ緩和は、初期ラグランジュ乗数を用いて生成される。
【００２０】
実施形態によれば、２値多項的に制約された多項計画問題のラグランジュ緩和の初期次数低減形式は量子アニーラを用いて解かれるのであり、少なくとも１つの対応する解が取得される。
【００２１】
実施形態によれば、少なくとも１つの対応する解を用いて２値多項的に制約された多項計画問題のラグランジュ双対の劣勾配を生成する。
【００２２】
実施形態によれば、少なくとも１つの対応する解を用いて、２値多項的に制約された多項計画問題のラグランジュ双対についての線形再定式化のための少なくとも１つの外側近似切断を生成する。
【００２３】
実施形態によれば、２値多項的に制約された多項計画問題のラグランジュ双対への対応する解の提供は、対応する解をファイルに格納することを含む。
【００２４】
広範な態様によれば、次のデジタルコンピュータが開示されている：即ち、デジタルコンピュータであって：中央処理装置と；表示装置と；デジタルコンピュータを２値オプティマイザに動作可能に接続するための通信ポートと；２値多項的に制約された多項計画問題 のラグランジュ双対を解くためのアプリケーションを含むメモリ部であって、該アプリケーションは：２値多項的に制約された多項計画問題を取得するための命令と；反復的に、ラグランジュ乗数のセットを提供し、これらのラグランジュ乗数における ２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、通信ポートを用いて 制約無しの２次計画問題 を２値オプティマイザへと提供し；通信ポートを介して２値オプティマイザから少なくとも１つの対応する解を取得し、少なくとも１つの対応する解を用いて収束が検出されるまで新たなラグランジュ乗数のセットを生成するための命令と、収束が検出された後に、対応する ２値多項的に制約された多項計画問題 のラグランジュ双対の知られている最良の主双対及び ２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するための命令とを含む、メモリ部と；中央処理装置と表示装置と通信ポートとメモリ部とを相互接続するためのデータバスとを含む、デジタルコンピュータ。
【００２５】
広範な態様によれば、次の不揮発性コンピュータ可読記憶媒体が開示されている：即ち、コンピュータ実行可能命令を格納するための不揮発性コンピュータ可読記憶媒体であって、該命令を実行すると、２値多項的に制約された多項計画問題 のラグランジュ双対を解くための方法をデジタルコンピュータに行わせるのであり、該方法は：２値多項的に制約された多項計画問題を取得するステップと、収束が検出されるまでは反復的に：ラグランジュ乗数のセットを提供し、これらのラグランジュ乗数における ２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、制約無しの２次計画問題 を２値オプティマイザへと提供し、２値オプティマイザから少なくとも１つの対応する解を取得し、少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと、収束が検出された後に、対応する ２値多項的に制約された多項計画問題 のラグランジュ双対の知られている最良の主双対及び ２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するステップとを含む、媒体。
【００２６】
実施形態によれば、２値オプティマイザは量子アニーラを含む。
【００２７】
ＢＰＣＰＰＰのラグランジュ双対を解くための本願開示の方法の利点としては、量子システムのエラーに対してより感度が減じられているということが挙げられる。これらのエラーは、量子アニーラ（例えば、D-Wave Systems）の一部の実装例で用いられるノイジーな量子ビットによって惹起され得る。したがって、本願開示の方法は、量子アニーラを含むシステムの処理内容を大幅に改善するのであり、また、量子アニーラの一部の実装例で用いられるノイジーな量子ビットによって惹起される技術的問題を解決することになる。
【００２８】
本願開示の方法の別の利点としては、ラグランジュ双対性を様々な用途に用いる方法を提供することが挙げられ、例えば、整数計画問題や混合整数計画問題に関して量子アニーラを用いてラグランジュ系の限界を探索することが挙げられる。
【００２９】
本願開示の方法の別の利点としては、ＢＰＣＰＰＰのラグランジュ双対を解くためのシステムの処理内容が改善されることが挙げられる。
【図面の簡単な説明】
【００３０】
発明の理解が容易となるようにするために、添付の図面を伴って本発明の実施形態について例示的に示す。
【００３１】
本発明のさらなる詳細及びそれらの利点は、後述の詳細な説明から明らかとなる。
【００３２】
【図１】２値多項的に制約された多項計画問題（ＢＰＣＰＰＰ、binary polynomially constrained polynomial programming problem）のラグランジュ双対を量子アニーラを用いて解くための方法についての実施形態を示すフローチャートである。
【図２】ＢＰＣＰＰＰのラグランジュ双対を量子アニーラを用いて解くための方法を実施できるシステムについての概略図であって、該実施形態においてシステムはデジタルコンピュータと量子アニーラとを備える、概略図である。
【図３】ＢＰＣＰＰＰのラグランジュ双対を量子アニーラを用いて解くためのシステムにおいて用いられるデジタルコンピュータについての実施形態に関しての概略図である。
【図４】ＢＰＣＰＰＰを提供するための実施形態を示すフローチャートである。
【図５】ＢＰＣＰＰＰのラグランジュ双対を解くための方法の実施形態で用いられるソフトウェアパラメータを初期化する実施形態を示すフローチャートである。
【図６】ラグランジュ乗数を更新するための方法として提唱される方法についての実施形態を示すフローチャートである。
【発明を実施するための形態】
【００３３】
実施形態についての以下の説明においては、添付の図面への言及は事例に関しての例示としてされているのであり、これらは本発明を実施し得る態様を示している。
【００３４】
用語
「発明」等の語は、「本願にて開示される１つ以上の発明」を意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００３５】
「態様」、不定冠詞を伴う「実施形態」、無冠詞の「実施形態」、無冠詞複数形の「実施形態」、定冠詞を伴う「実施形態」、定冠詞を伴う複数形の「実施形態」、「１つ以上の実施形態」、「幾つかの実施形態」、「特定の実施形態」、「或る実施形態」、「別の実施形態」等の語は、「本願開示の発明の１つ以上（但し、全部ではない）」を意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００３６】
実施形態について説明するに際して「別の実施形態」や「別の態様」に言及しても、被言及側の実施形態が別の実施形態（例えば、被参照側実施形態の前に説明された実施形態）と相互排反的であることを暗示するわけではないが、明示的に別段の定めがされている場合はこの限りでない。
【００３７】
「含む」、「備える」、及びこれらのバリエーションは「含むがこれらには限られない」とのことを意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００３８】
「不定冠詞たるa」、「不定冠詞たるan」、「定冠詞たるthe」及び「少なくとも１つ」との語は、「１つ以上」を意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００３９】
「複数」との語は「２つ以上」を意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００４０】
「ここで」との語は「本願において、そして参照によって取り込まれる任意のものを含む」とのことを意味するが、明示的に別段の定めがされている場合はこの限りでない。
【００４１】
「exempli gratis」等の語は「例えば」を意味するのであり、説明される語又はフレーズを限定はしない。例えば、「コンピュータはインターネット上にデータ（e.g.，命令やデータ構造）を送る」とのセンテンスにおいては、「e.g.」との語は「命令」というものがコンピュータによってインターネット上に送られ得る「データ」の例であることを説明し、また、「データ構造」というものがコンピュータによってインターネット上に送られ得る「データ」の例であることをも説明する。もっとも、「命令」も「データ構造」も「データ」の例に過ぎず、「データ構造」や「データ」以外のものも「データ」たり得る。
【００４２】
「id est」等の語は「即ち」を意味するのであり、説明される語又はフレーズを限定する。例えば、「コンピュータはインターネット上にデータ（i.e.，命令）を送る」とのセンテンスにおいては、「i.e.」との語は「命令」がというものがコンピュータによってインターネット上に送られる「データ」であることを説明する。
【００４３】
「２値多項的に制約された多項計画問題」（ＢＰＣＰＰＰ、binary polynomially constrained polynomial programming problem）等の語は、複数の２値変数ｘ＝（ｘ１，．．．，ｘｎ）における実多項式ｙ＝ｆ（ｘ）の最小値を見つけることを意味し、ここで次の制約を課されるものとする（以下、「subject to」とも表現する）：（空集合かもしれない）ｍ個の等式ｇｊ（ｘ）＝０のファミリ（ここで、ｊ＝１，．．．，ｍ）によって決定される（空集合かもしれない）等式制約のファミリ、並びに、（空集合かもしれない）ｌ個の不等式ｈｊ（ｘ）≦０のファミリ（ここで、ｊ＝１，．．．，ｌ）によって決定される（空集合かもしれない）不等式制約のファミリ。ここで、全ての関数ｇｉ及びｈｊは多項式である。
【数１】
2019512134.tif 000003
【００４４】
ＢＰＣＰＰＰの「定義域」とは、２値エントリを伴うサイズがｎであるベクトルについての集合｛０，１｝ｎを意味する。ＢＰＣＰＰＰの「実行可能領域」とは定義域の部分集合たるＦ⊆｛０，１｝ｎを意味し、これは上述のｍ個の等式制約及びｌ個の不等式制約の全てを充足する全ての２値ベクトルｖ∈｛０，１｝ｎで構成されている。
【００４５】
上述のＢＰＣＰＰＰは（Ｐ）と表され、その最適値はｖ（Ｐ）と表される。最適解ｘ（即ち目的関数が値ｖ（Ｐ）を達成するベクトル）は、ｘ＊として表される。
【００４６】
ＢＰＣＰＰＰたる（Ｐ）の「ラグランジュ関数」とは次の関数を意味する：
【数２】
2019512134.tif 000004
【００４７】
2019512134.tif 000005
【００４８】
δｐ（λ，μ）として表記される上述の最適化の値は、元のＢＰＣＰＰＰについての最適値の下限として知られており、即ち、δｐ（λ，μ）≦ｖ（Ｐ）である。
【００４９】
2019512134.tif 000006
【００５０】
ＢＰＣＰＰＰの「ラグランジュ双対」との語は、次の最適化問題との関連で用いられる：
【数３】
2019512134.tif 000007
【００５１】
上述の最適化はδ（Ｐ）として表され、元のＢＰＣＰＰＰについての最適値の下限として知られており、即ち、δ（Ｐ）≦ｖ（Ｐ）である。この値は一意的であり、元のＢＰＣＰＰＰについての「ラグランジュ双対限界」とも称される。
【００５２】
「最適ラグランジュ乗数」等の用語は、必ずしも一意的ではないポイントの集合λ＊及びμ＊を指し示し、そこにおいてはδ（Ｐ）の値が上述の最適化問題との関係で達成される。
【００５３】
元のＢＰＣＰＰＰについての「ラグランジュ双対問題について解」とは、ラグランジュ双対問題を解いた後に受信される次の情報の寄せ集めを指し示す：（１）ラグランジュ双対限界；（２）上述のような最適ラグランジュ乗数についての（必ずしも一意的ではない）集合；（３）所与の最適ラグランジュ乗数においてラグランジュ双対問題の最適値が得られる２値ベクトルについての（必ずしも一意的ではない）集合
【００５４】
2019512134.tif 000008
【００５５】
2019512134.tif 000009
【００５６】
「知られている最良の主双対」（best-known primal-dual pair）とは、実行中の処理についてδｐ（λ，μ）が関数たるδｐについての最大観測値となるような主双対たる（ｘ，λ，μ）を指し示す。
【００５７】
2019512134.tif 000010
【００５８】
「量子アニーラ」等の語は、制約無しの２値多項式計画問題（unconstrained binary polynomial programming problem）についての最適又は準最適な解を見つけることができる１つ又は多数のタイプのハードウェアを含むシステムを意味する。この例としては、２値多項的に制約された多項計画（binary polynomially constrained polynomial programming）をイジングスピンモデル（Ising spin model）として埋め込むデジタルコンピュータであって、アナログコンピュータに接続されたものを挙げることができ、該アナログコンピュータは例えば次の文献に開示されているような量子アニーリングを用いてイジングスピンモデル内のスピン構成について最適化を行う：非特許文献４、pp.1-16。このようなアナログコンピュータの実施形態は被特許文献５及び特許文献２において開示されている。なお、「量子アニーラ」は古典的なコンピュータ等の「古典的なコンポーネント」を備えていることもできることに留意されたい。したがって、「量子アニーラ」は完全にアナログ型であるか或いはアナログ−典型のハイブリッド型であることができる。また、「量子アニーラ」は２値オプティマイザの実施形態であることにも留意されたい。
【００５９】
2019512134.tif 000011
【００６０】
２値最適化問題についての「埋め込み」等の語は、割当たるｅｍｂ:{ｘ1,・・・,
ｘn,ｙ1,・・・,ｙt｝→2｛ｑ1,・・,qn}を指し示し、該割当は量子アニーラの全量子ビットの部分集合を２値変数ｘｉの各々及び補助変数ｙｊの各々へと渡すのであり、変数間の接続性は、それらのｅｍｂ下での像の接続性によって遵守されるようになっている。例えば、項たるｘｒｘｓがＢＰＣＰＰＰの一般的ラグランジュ緩和のＧＤＲＦ内に現れる場合、２つの変数ｘｒ及びｘｓに対応する量子ビットの部分集合は、量子アニーラ内においてはそれらの間での結合を有しているはずである。制約無しの２値多項式計画問題を解く場合及びそれについての効率的なアルゴリズムを提唱する場合に関しての上述のような埋め込みの役割の詳細については、次の文献を参照されたい：非特許文献６、特許文献３、及び特許文献４。
【００６１】
「埋め込みソルバ」等の語は、次のような命令を含む関数、手続及びアルゴリズムを指し示す：制約無しの２値２次計画問題（ＵＢＱＰＰ、unconstrained binary quadratic programming problem）を受信するステップと、提供された埋め込みを用いて量子アニーラに対してクエリの遂行を行うステップと、少なくとも１つの結果を返すステップであって各結果は次の事項を表す２値エントリのベクトルを含むステップ：即ち提供された制約無しの２値２次計画（ＵＢＱＰ、unconstrained binary quadratic programming）の定義域における２値ポイントに関する事項と、そのポイントにおけるＵＢＱＰの目的関数の値に関する事項と、読み出し回数全体における結果の発生回数に関する事項。
【００６２】
「サブルーチン」等の語は、実行時において随時ソフトウェアによって反復的に呼び出されるユーザ定義型の関数、手順又はアルゴリズムを指し示す。本願開示のシステムにおいては、ステップサイズサブルーチンは、図１に示した反復回における次回ステップサイズを決定する。本願開示のシステムでは、埋め込みソルバサブルーチンは量子アニーラへのクエリを捌くのであり、埋め込みが提供した観点もある。
【００６３】
「制約無しの２値２次計画問題」（ＵＢＱＰＰ、unconstrained binary quadratic programming problem）等の語は、目的関数たるｙ＝ｘｔＱｘ+ｂの最小値を探索することを意味し、ここでＱはサイズがｎの対称型かつ正方型の実行列であり、ｂは実数であり目的関数のバイアスとも呼ばれる。関数の定義域は、２値エントリを有する次の条件を満たすベクトル全てにわたる：ｘ∈Ｂｎ＝｛０，１｝ｎ。
【００６４】
2019512134.tif 000012
【００６５】
発明の名称及び要約のいずれも、何らの観点からも、開示された発明の範囲を限定するために用いられてはならない。本願の発明の名称及び明細書中の項目名は利便性のためだけに付されているのであり、何らの観点からも開示内容を限定するものとして用いられてはならない。
【００６６】
本願においては様々な実施形態が説明されており、例示的目的のみのために提示されている。説明された実施形態は何らの意味合いにおいても限定的なものではなく、またそのような意図すらないことに留意されたい。開示内容から明らかなように、開示されている発明は様々な実施形態に適用可能である。当業者であれば、開示されている発明には構造的な変更や論理的な変更等の様々な変更や改変を加えた上で実施することができることに気付くであろう。開示されている発明の特定の特徴は１つ以上の特定の実施形態及び／又は図面との関係で説明されている場合があり得るが、そのような特徴はそれらの説明に際して参照される特定の実施形態や図面における用例に限定されないことに留意されたい。もっとも、明示的に別段の定めがされている場合はこの限りでない。
【００６７】
本発明は様々な態様で実施されることができ、これらには方法やシステムやコンピュータ可読媒体（例えば、コンピュータ可読記憶媒体）が含まれる。本明細書においては、これらの実施態様及び本発明が取り得る他の任意の形式を、システムや手法と称することができることに留意されたい。あるタスクを行うように構成されているものとして説明されているプロセッサやメモリ等のコンポーネントには、次の両者が含まれ得る：所定の時期においてタスクを行うように一次的に構成されている汎用コンポーネント、及び、タスクを行うように製造された具体的コンポーネント。
【００６８】
上記全てを考慮に入れた上で、以下においてはＢＰＣＰＰＰのラグランジュ双対を解くための方法及びシステムに関する発明について説明する。
【００６９】
後述の実施形態では量子アニーラが用いられるも、当業者であれば量子アニーラは２値オプティマイザの１つの実装例であることに気付くであろう。
【００７０】
図２を参照するに、システム２００についての実施形態が示されており、該システムにおいてＢＰＣＰＰＰのラグランジュ双対を解くための方法についての実施形態を実装することができる。
【００７１】
システム２００は、デジタルコンピュータ２０２と量子アニーラ２０４とを備える。
【００７２】
デジタルコンピュータ２０２はＢＰＣＰＰＰを受信し、ＢＰＣＰＰＰのラグランジュ双対についての少なくとも１つの解を提供する。
【００７３】
様々な実施形態に従ってＢＰＣＰＰＰを提供することができることに留意されたい。
【００７４】
１つの実施形態では、ＢＰＣＰＰＰは、デジタルコンピュータ２０２と対話するユーザによって提供される。
【００７５】
代替的には、ＢＰＣＰＰＰは、図示されていない別のコンピュータによって提供されるのであり、該別のコンピュータはデジタルコンピュータ２０２と動作可能に接続されている。
【００７６】
代替的には、ＢＰＣＰＰＰは、独立のソフトウェアパッケージによって提供される。
【００７７】
代替的には、ＢＰＣＰＰＰは、インテリジェントエージェントによって提供される。
【００７８】
同様に、様々な実施形態に従ってＢＰＣＰＰＰのラグランジュ双対についての少なくとも１つの解を提供することができることに留意されたい。
【００７９】
ある実施形態によれば、ＢＰＣＰＰＰのラグランジュ双対についての少なくとも１つの解は、デジタルコンピュータ２０２と対話しているユーザに対して提供される。
【００８０】
代替的には、ＢＰＣＰＰＰのラグランジュ双対についての少なくとも１つの解は、デジタルコンピュータ２０２と動作可能に接続されている別のコンピュータに対して提供される。
【００８１】
実際、当業者であれば、デジタルコンピュータ２０２は任意のタイプのコンピュータであることができることに気付くであろう。
【００８２】
１つの実施形態では、デジタルコンピュータ２０２は次のものからなる群から選択される：デスクトップ型コンピュータ、ラップトップ型コンピュータ、タブレット型ＰＣ、サーバ、スマートフォン等。
【００８３】
図３に転じるに、デジタルコンピュータ２０２についての実施形態が同図に示されている。デジタルコンピュータ２０２は、広義な意味合いではプロセッサとも称され得る。
【００８４】
この実施形態では、デジタルコンピュータ２０２は次のものを備える：マイクロプロセッサ又は処理装置とも呼ばれる中央処理装置（ＣＰＵ）３０２、表示装置３０４、入力装置３０６、通信ポート３０８、データバス３１０、及びメモリ部３１２。
【００８５】
ＣＰＵ３０２は、コンピュータ命令を処理するために用いる。当業者にとっては、ＣＰＵ３０２については様々な実施形態をもたらすことができることが明らかである。
【００８６】
１つの実施形態では、ＣＰＵ３０２は3.6 GHzで実行されているCore i7 3820である（インテル製（登録商標））。
【００８７】
表示装置３０４はデータをユーザに対して表示するために用いられる。当業者にとっては、表示装置３０４については様々なタイプの実施形態をもたらすことができることが明らかである。
【００８８】
１つの実施形態では、表示装置３０４は標準的な液晶表示装置（ＬＣＤ）モニタである。
【００８９】
通信ポート３０８は、データをデジタルコンピュータ２０２と共有するために使用される。
【００９０】
通信ポート３０８は、例えば、キーボード及びマウスをデジタルコンピュータ２０２に接続するためのユニバーサルシリアルバス（ＵＳＢ）ポートを含み得る。
【００９１】
通信ポート３０８は、データネットワークを介してデジタルコンピュータ２０２を別のコンピュータと接続することを可能とするようなIEEE 802.3ポート等のデータネットワーク通信ポートをさらに含み得る。
【００９２】
当業者にとっては、通信ポート３０８については様々な代替的実施形態をもたらすことができることが明らかである。
【００９３】
１つの実施形態では、通信ポート３０８はイーサネット（登録商標）ポートとマウスポート（例えば、Logitech（登録商標）のそれ）とを含み得る。
【００９４】
メモリ部３１２はコンピュータ実行可能命令を格納するために用いられる。
【００９５】
１つの実施形態では、メモリ部３１２はオペレーティングシステムモジュール３１４を備える。
【００９６】
当業者にとっては、オペレーティングシステムモジュール３１４に関しては様々なタイプを用いることができることが明かである。
【００９７】
ある実施形態では、オペレーティングシステムモジュール３１４はMicrosoft（登録商標）製のWindows（登録商標） 8とされる。
【００９８】
メモリ部３１２はＢＰＣＰＰＰのラグランジュ双対を解くためのアプリケーション３１６をさらに備える。
【００９９】
アプリケーション３１６はＢＰＣＰＰＰを取得するための命令を備えている。
【０１００】
アプリケーション３１６は次の処理を行うための命令をさらに備えている：反復的に、ラグランジュ乗数のセットを提供し、これらのラグランジュ乗数におけるＢＰＣＰＰＰのラグランジュ緩和を表すＵＢＱＰＰを提供し、ＵＢＱＰＰを量子アニーラに提供し；量子アニーラから少なくとも１つの対応する解を取得し、また、少なくとも１つの対応する解を用いて新たなラグランジュ乗数セットを生成する処理。
【０１０１】
アプリケーション３１６は、収束が検出されたらばＢＰＣＰＰＰのラグランジュ双対についての少なくとも１つの解に対応する解を提供するための命令をさらに備える。
【０１０２】
ＣＰＵ３０２、表示装置３０４、入力装置３０６、通信ポート３０８、及びメモリ部３１２のそれぞれは、データバス３１０を介して相互接続されている。
【０１０３】
図２に戻るに、量子アニーラ２０４はデジタルコンピュータ２０２と動作可能に接続されていることに留意されたい。
【０１０４】
量子アニーラ２０４をデジタルコンピュータ２０２に接続するに際しては、様々な実施形態をもたらすことが可能であることに留意されたい。
【０１０５】
１つの実施形態では、データネットワークを介して量子アニーラ２０４とデジタルコンピュータ２０２とが接続される。
【０１０６】
量子アニーラ２０４は、様々なタイプのものとすることができることに留意されたい。
【０１０７】
１つの実施形態では、量子アニーラ２０４はD Wave Systems Inc.製である。量子アニーラ２０４についてのこの実施形態に関して妥当するさらなる情報は次のサイトで入手可能である：http://www.dwavesys.com。当業者にとっては、量子アニーラ２０４について様々な代替的実施形態をもたらすことが可能であることが明かである。
【０１０８】
より正確に述べれば、量子アニーラ２０４は、デジタルコンピュータ２０２からＵＢＱＰＰを受信する。
【０１０９】
量子アニーラ２０４は、ＵＢＱＰＰを解くことができ、また、少なくとも１つの対応する解を提供することができる。複数の対応する解が提供される局面においては、複数の対応する解には最適解及び準最適解が含まれ得る。
【０１１０】
少なくとも１つの対応する解は、量子アニーラ２０４によってデジタルコンピュータ２０２に対して提供される。
【０１１１】
図１に転じる。処理ステップ１０２を参照するに、ＢＰＣＰＰＰが取得される。
【０１１２】
次に図４に転じるに、同図においてはＢＰＣＰＰＰを提供するための実施形態が示されている。
【０１１３】
上述のように、ＢＰＣＰＰＰは次のように表すことができる：
【数４】
2019512134.tif 000013
ここで、関数ｆ（ｘ）、ｇｉ（ｘ）及びｈｊ（ｘ）は複数変数に関しての実多項式である。
【０１１４】
処理ステップ４０２によれば、多項式たる目的関数ｆ（ｘ）を表すデータが提供される。
【０１１５】
処理ステップ４０４によれば、等式制約及び不等式制約ｇｉ（ｘ）及びｈｊ（ｘ）を表すデータが提供される。
【０１１６】
ＢＰＣＰＰＰの取得の実行については、様々な実施形態をもたらすことが可能であることに留意されたい。
【０１１７】
上述したように、そして１つの実施形態では、ＢＰＣＰＰＰは、デジタルコンピュータ２０２と対話するユーザによって提供される。
【０１１８】
代替的には、ＢＰＣＰＰＰは、デジタルコンピュータ２０２と動作可能に接続されている別のコンピュータによって提供される。
【０１１９】
代替的には、ＢＰＣＰＰＰは、独立のソフトウェアパッケージによって提供される。
【０１２０】
代替的には、ＢＰＣＰＰＰは、インテリジェントエージェントによって提供される。
【０１２１】
図１を参照するに、そして処理ステップ１０４によれば、ソフトウェアのパラメータが初期化される。
【０１２２】
１つの実施形態では、ソフトウェアのパラメータは、デジタルコンピュータ２０２によって初期化される。
【０１２３】
図５に転じるに、同図にはパラメータの初期化に関する実施形態やサブルーチンやそれらのためにデフォルト値を用いる態様が示されている。
【０１２４】
処理ステップ５０２によれば、ＢＰＣＰＰＰの一般的ラグランジュ緩和についてのＧＤＲＦが提供される。
【０１２５】
処理ステップ５０４によれば、ＢＰＣＰＰＰの一般的ラグランジュ緩和のＧＤＲＦについての一般的埋め込みを表すデータが提供される。
【０１２６】
１つの実施形態では、埋め込みはORACLEとの名前空間においてユーザによって格納されるのであり、ORACLE::embeddingとされる。
【０１２７】
引き続き図５を参照するに、そして処理ステップ５０６によれば、埋め込みソルバサブルーチン（embedding solver subroutine）が提供される。
【０１２８】
１つの実施形態では、関数はORACLEとの名前空間においてユーザによって実装されるのであり、ORACLE::solve_quboとされる。
【０１２９】
埋め込みソルバサブルーチンの入力パラメータは、ORACLE::solve_quboデータ型のインスタンスへのポインタであり、制約無しの２値２次計画問題を表すのであり、それに対応するバイアスは無視されている。
【０１３０】
埋め込みソルバサブルーチンの出力は、ORACLE::result型のインスタンスへのポインタであり、制約無しの２値多項計画問題に関しての最適解及び準最適解のリストを表すものである。
【０１３１】
以下においては、D-Wave Systemsによって開発されたＡＰＩ（Sapi 2.0）を用いたサブルーチンを提供するためのＣ＋＋で書かれたコードスニペットの例が提示される。このスニペット内で用いられている関数及び型は２つの補助関数、即ちqubo_to_ising及びspin_to_binaryを除いて、全てSapi 2.0によってサポートされている。前者の関数は、ORACLE::qubo型のＵＢＱＰＰを、sapi_problem型のイジングスピン問題へと転換するのであり、ｓ＝２ｘ−１との変数変換によってこれをなす。２点目の関数は、｛−１，１｝内のベクトル配列を受信し、ｘ＝１／２（ｓ＋１）との逆変換を適用することによって２値ベクトルを返す。
【数５】
2019512134.tif 000014
【０１３２】
１つの実施形態では、デジタルコンピュータ２０２を用いることによって、制約無しの２値最適化問題を量子アニーラ２０４へと提供する処理が達成されていることが分かる。
【０１３３】
より正確には、１つの実施形態では、インターネット上でのトークンシステムが用いられて、量子アニーラ２０４に対して遠隔的なアクセスを提供し、また、使用に際しての認証を提供する。
【０１３４】
１つの実施形態では、量子アニーラ２０４の使用に関しての命令に従って少なくとも１つの解が量子アニーラ２０４によってテーブル内で提供されることが分かる。
【０１３５】
１つの実施形態では、D Wave systemはsapi_IsingResult*のデータ型で少なくとも１つの解を提供するのであり、そしてそれはQUBO::result*のインスタンスへと自動的にタイプキャスティングされる。
【０１３６】
引き続き図５を参照するに、そして処理ステップ５０８によれば、ラグランジュ乗数に関しての下限及び上限が提供される。
【０１３７】
１つの実施形態では、これらのダブル型の実数についての提供行為は、ORACLE::dual_lb及びORACLE::dual_ubの名前を上書きすることによって達成されることに留意されたい。これらの型のそれぞれは、サイズがｍ＋ｌのダブルのアレイを含む必要がある。これらのアレイの最初のｍ個のエントリはｍ個の等式制約に対応するラグランジュ乗数についての下限及び上限をそれぞれ表し、これらの最後のｌ個はｌ個の不等式制約に対応するラグランジュ乗数についての下限及び上限をそれぞれ表す。
【０１３８】
これらの名前が上書きされない場合、それらの値はデフォルト値をもって初期化されることに留意されたい。
【０１３９】
１つの実施形態では、等式制約に対応するラグランジュ乗数についての既定下限は、−１ｅ３であり、それについての既定上限は＋１ｅ３である。
【０１４０】
不等式制約に対応するラグランジュ乗数についての既定下限は０であり、それについての既定上限は＋１ｅ３である。
【０１４１】
引き続き図５を参照するに、そして処理ステップ５１０によれば、ラグランジュ乗数についての初期値は提供される。
【０１４２】
これらの実数としての値の提供は、ORACLE::dual_init_valとの名前に対して、サイズがｍ＋ｌのダブルのアレイで上書きすることによって達成されることに留意されたい。この名前が上書きされない場合、それらの値はデフォルト値をもって初期化される。
【０１４３】
任意の等式制約又は不等式制約に対応する任意のラグランジュ乗数についてのデフォルト初期値は、０である。
【０１４４】
処理ステップ５１２によれば、ラグランジュ双対の劣勾配のノルムについての誤差許容値が提供される。ラグランジュ緩和の任意の劣勾配のノルムがこの許容値を下回った場合、強双対性（strong duality）が成立しているとみなされる。このような場合、ラグランジュ乗数は最適である。１つの実施形態によれば、ユーザによって上書きされない限り、誤差許容値は１ｅ−５に初期化されてORACLE::tolとして格納される。誤差許容値は、ソフトウェアの幾つかの箇所で用いられる。
【０１４５】
１つの実施形態によれば、ORACLE::tolは等式制約及び不等式制約を確認するために用いられる。特に、ＬＨＳ−ＲＨＳの全エントリの値（value）が最大でORACLE::tolであれば、ＬＨＳ≦ＲＨＳの不等式の任意の系は充足されているものとみなされる。同様に、ＬＨＳ−ＲＨＳの全エントリの絶対値（absolute value）が最大でORACLE::tolであれば、ＬＨＳ＝ＲＨＳの等式の任意の系は充足されているものとみなされる。
【０１４６】
引き続き図５を参照するに、そして処理ステップ５１４によれば、総反復回数についての制限値が提供される。
【０１４７】
１つの実施形態によれば、ユーザによって上書きされない限り、反復回数に関しての制限値は１ｅ３に初期化されてORACLE::MaxItrとして格納される。
【０１４８】
アルゴリズムが処理ステップ１１６のORACLE::MaxItrの反復回数に達した場合、アルゴリズムが終了されて、少なくとも１つの知られている最良の主双対（best-known primal-dual pair）と少なくとも１つの知られている最良の実行可能解（best-known feasible solution）とが返される。
【０１４９】
ステップ５１４によれば、非改善反復回数についての制限値が提供される。
【０１５０】
１つの実施形態によれば、ユーザによって上書きされない限り、反復回数に関しての制限値は１０に初期化されてORACLE::MaxNonImpItrとして格納される。ORACLE::MaxNonImpItr回の反復回数中に知られている最良のラグランジュ双対値（best-known Lagrangian dual value）が増加しない場合、アルゴリズムが終了されて、少なくとも１つの知られている最良の主双対と少なくとも１つの知られている最良の実行可能解とが返される。
【０１５１】
ステップ５１６によれば、ステップサイズを発見するためのサブルーチンが提供される。
【０１５２】
１つの実施形態では、サブルーチンはORACLEとの名前空間においてユーザによって実装されるのであり、ORACLE::StepSizeとされる。ORACLE::StepSizeがユーザによって上書きされない場合、デフォルト値についての固定ステップサイズが用いられる。
【０１５３】
１つの実施形態では、ORACLE::StepSizeのサブルーチンは、探索方向を表すダブル＊（double*）型のオブジェクトを入力として受信し、また、ステップサイズを表すダブル(double)型のオブジェクトを出力として返す。
【０１５４】
１つの実施形態では、探索方向はラグランジュ双対関数の劣勾配であり、また、ステップサイズは固定値たる１とされる。
【０１５５】
図１に戻るに、そして処理ステップ１０６によれば、ラグランジュ乗数の現在値におけるＢＰＣＰＰＰたる（Ｐ）のラグランジュ緩和を表すＵＢＱＰＰが、生成される。
【０１５６】
１つの実施形態では、ラグランジュ乗数の現在値におけるＢＰＣＰＰＰたる（Ｐ）のラグランジュ緩和を表すＵＢＱＰＰが、デジタルコンピュータ２０２によって生成されるものと理解される。
【０１５７】
より正確には、この実施形態では、次のことをなすことによってＵＢＱＰＰの生成がなされるものと理解される：即ち、ＢＰＣＰＰＰたる（Ｐ）の一般的ラグランジュ緩和のＧＤＲＦたるｑλ，μ（ｘ，ｙ）内において、ラグランジュ乗数の現在値をパラメータたるλ及びμと代替させること。
【０１５８】
１つの実施形態では、ＵＢＱＰＰの情報は、ORACLE::quboとの名前の下で格納される。
【０１５９】
引き続き図１を参照するに、そして処理ステップ１０８によれば、サブルーチンたるORACLE::solve_quboが、入力としてＵＢＱＰＰたるORACLE::quboと埋め込みたるORACLE::embeddingを伴って呼び出されるのであり、それによってＵＢＱＰＰについての少なくとも１つの対応する解を量子アニーラ２０４からもたらすようにする。
【０１６０】
１つの実施形態では、ＵＢＱＰＰについての少なくとも１つの対応する解が、ORACLE::result型のインスタンスへのポインタをもって達成されるものと理解される。
【０１６１】
引き続き図１を参照するに、そして処理ステップ１１０によれば、ＵＢＱＰＰの少なくとも１つの解は、ＢＰＣＰＰＰたる（Ｐ）の定義域内のポイントへと変換される。
【０１６２】
引き続き図１を参照するに、そして処理ステップ１１２によれば、検査を行うのであって、これによってＵＢＱＰＰについての少なくとも１つの解うちのいずれかがＢＰＣＰＰＰたる（Ｐ）の実行可能解に対応するかを決定する。
【０１６３】
同処理ステップによれば、少なくとも１つの知られている最良の主双対と少なくとも１つの知られている最良の実行可能解とが、更新される。
【０１６４】
そして処理ステップ１１４に転じるに、制約無しの２値２次計画に関しての少なくとも１つの対応する解を用いてラグランジュ緩和の劣勾配を生成する、即ちδｐ（λ，μ）。
【０１６５】
図６に転じるに、そして処理ステップ６０２によれば、ＢＰＣＰＰＰたる（Ｐ）の定義域内の少なくとも１つの対応する２値ベクトルが提供される。
【０１６６】
処理ステップ６０４によれば、ＵＢＱＰＰの解たる
2019512134.tif 000015
に対応するラグランジュ緩和の劣勾配が次のように導出される：
【数６】
2019512134.tif 000016
【０１６７】
１つの実施形態では、制約無しの２次計画問題（unconstrained quadratic programming problem）についての複数の２値解（binary solution）が提供された場合、最小のノルムを有する劣勾配を選択することができる。
【０１６８】
１つの実施形態では、導出された劣勾配を正規化することができる。
【０１６９】
処理ステップ６０６によれば、導出された劣勾配はステップサイズサブルーチンに提供され、ステップサイズに関しての値が得られる。
【０１７０】
実施形態によれば、ステップサイズサブルーチンがユーザによって初期化された場合、ORACLE::StepSizeに対して呼び出しを行うことによってステップサイズたるαを見つける。
【０１７１】
処理ステップ６０８によれば、ラグランジュ乗数は次のように更新される：
【数７】
2019512134.tif 000017
ここで、new：新であり、old：旧である。
【０１７２】
図１に戻るに、そして処理ステップ１１６によれば、検査を行うのであって、これによってこれまでのORACLE::MaxNonImpItr回のステップにおいてδｐ（λ，μ）の最良値が改善されたか否かを判別する。
【０１７３】
処理ステップ１１８によれば、これまでのORACLE::MaxNonImpItr回のステップにおいてδｐ（λ，μ）の最良値が改善されていない場合、最適化の結果が提供される。
【０１７４】
１つの実施形態では、結果は次の事項を含む集合を含むものと理解される：即ち、知られている最良の主双対（ｘ＊，λ＊，μ＊）全部、及び、知られている最良の実行可能解全部。
【０１７５】
１つの実施形態では、結果は、デジタルコンピュータを用いてファイル内に格納される。
【０１７６】
本願開示の方法の利点としては、ＢＰＣＰＰＰの解を探索するに際して効率的な方法を可能たらしめることが挙げられるのであり、量子アニーラを用いてそのラグランジュ双対の解を見つけることによってこのことを成し遂げる。
【０１７７】
さらに、本願開示の方法によれば、ＢＰＣＰＰＰのラグランジュ双対を解くためのシステムの処理内容を向上させることできることが明かとなる。
【０１７８】
終了がなされるまで、ラグランジュ乗数が反復的に更新されていくものと理解されよう。ラグランジュ双対関数の劣勾配のノルムが最大でORACLE::tolとなった場合、又は、ORACLE::MaxNonImpItr回若しくはORACLE::MaxItr回の反復後に最良主双対に関して改善が見られない場合に、プログラムは終了する。
【０１７９】
以下においては本願開示の方法の使用例についての例示を示すのであり、最大２次安定化集合問題（ＭＱＳＳＰ、maximum quadratic stable set problem）に適用した場合について述べる。
【０１８０】
Ｇ＝（Ｖ，Ｅ）がｎ個の頂点についてのグラフを定義するものとし；ＷはエッジたるＥの重み付けを表す行列であってサイズがｎで対称かつ正方型の行列であり；そして、ＡはＧの隣接行列であるものとする。ＭＱＳＳＰは次のように定式化される：
【数８】
2019512134.tif 000018
【０１８１】
目的関数について符号を負としたものを採用することによって、最大化目的関数（maximization objective function）は最小化処理（minimization）として次のように記述され得る：
【数９】
2019512134.tif 000019
【０１８２】
2019512134.tif 000020
【０１８３】
１つの例では、５つの頂点を有するグラフが５人の同僚（coworker）からなる群を表すものとする。同僚のペア毎に、同僚間の協調に関しての効用係数（utility factor）が割り当てられているものとする。各個人に対して、各々の成果に関して効用係数が割り当てられているものとし、これらの値は行列Ｗの対角線上にあるものとする。これらの効用は次の上三角行列として表され得る：
【数１０】
2019512134.tif 000021
【０１８４】
2019512134.tif 000022
【０１８５】
各作業員（worker）には作業シフトがあるものとし、重複するシフトを有する同僚ペアについては行列Ａがゼロでないエントリを有しているものとするのであり例えば次のようになるとする：
【数１１】
2019512134.tif 000023
【０１８６】
どの二人のチーム構成員も重複するシフトを有していないようにしてプロジェクトについての最も生産的なチーム編成を選択するという問題は、ＭＱＳＳＰの一例である。
【０１８７】
上述の行列Ａ及びＷを与えられたらば、処理ステップ１０２に従って以下のＢＰＣＰＰＰが得られる：
【数１２】
2019512134.tif 000024
【０１８８】
上述の例の目的関数及び不等式制約の２つの多項式は２次式であるため、この問題のラグランジュ緩和の次数低減形式は、ラグランジュ緩和それ自体と同じである。サイズが５である完全なグラフについての埋め込みが提供される。次のコードスニペットは、２つの部分からなるＫ４，４−二部型キメラブロック上の、サイズが５である完全なグラフについての埋め込みを提供するのであり、それは２つの部分からなり、各々のサイズは４であり、第１の部分は０〜３の整数でインデキシングされ、第２の部分は４〜７の整数でインデキシングされている。
【数１３】
2019512134.tif 000025
【０１８９】
ラグランジュ乗数の下限及び上限はそれぞれ０及び１００として設定される。ラグランジュ乗数の初期値として０が割り当てられている。ラグランジュ双対関数の劣勾配のノルムについての許容値は１０−３として設定される。総反復回数及び改善をもたらさない反復回数についての制限値は、それぞれ１００及び５とされる。この例で用いられるステップサイズサブルーチンは、次のスクリプトに従ってサイズが０．５の固定ステップサイズをもたらすサブルーチンである：
double ORACLE::StepSize() { return 0.5; }
【０１９０】
メソッドが開始されると、最良実行可能解及び最良主双対についてのリストは初期化されて空集合とされる。提示される方法のラグランジュ乗数はλ１＝０で初期化され、下記の問題が量子アニーラによって解かれる：
【数１４】
2019512134.tif 000026
得られる最適解はｘ１＝（１，１，１，１，１）であり、最適値は−３３である。ｘ１は実行可能ではない故に、最良実行可能解のリストは更新されない。もっとも、最良主双対は（ｘ１，λ１）に更新される。
【０１９１】
以下のラグランジュ緩和の劣勾配はｘ１＝（１，１，１，１，１）についてｘｔＡｘ＝8である：
【数１５】
2019512134.tif 000027
ステップサイズサブルーチンに関しては、サイズが０．５の固定ステップサイズが用いられるものとする。そして、その次のラグランジュ乗数は次のように計算される：
λ２＝０+０．５*８＝４
【０１９２】
以下のラグランジュ緩和問題は量子アニーラによって解かれる：
【数１６】
2019512134.tif 000028
最適値が−１６となる最適解ｘ２＝（１，０，１，１，０）が得られる。最良主双対は（ｘ２，λ２）に更新されるも、ｘ２が実行不能故に最良実行可能解は空集合のままとされる。
【０１９３】
この解におけるラグランジュ緩和の劣勾配は２である。そして、その次のラグランジュ乗数は次のように計算される：
λ３＝４+０．５*２＝５
【０１９４】
以下のラグランジュ緩和問題は量子アニーラによって解かれる：
【数１７】
2019512134.tif 000029
最適値が−１４となる最適解ｘ３＝（１，０，１，１，０）が得られる。最良主双対は（ｘ３，λ３）に更新されるも、ｘ３が実行不能故に最良実行可能解は空集合のままとされる。
【０１９５】
この解におけるラグランジュ緩和の劣勾配は２である。そして、その次のラグランジュ乗数は次のように計算される：
λ４＝５+０．５*２＝６
【０１９６】
以下のラグランジュ緩和問題は量子アニーラによって解かれる：
【数１８】
2019512134.tif 000030
最適値が−１３となる最適解ｘ４＝（１，０，０，１，０）が得られる。ｘ４が実行可能であるが故に、最良主双対（ｘ４，λ４）と共に最良実行可能解も更新される。
【０１９７】
この現在の解においては、ラグランジュ緩和の劣勾配のノルムは０であり、方法は終了する。最良実行可能解たるｘ４＝（１，０，０，１，０）及び最良主双対たる（ｘ４，λ４）＝（（１，０，０，１，０），６）が報告される。
【０１９８】
本願に関していえば、得られた解では、どの二人の同僚も重複するシフトを有さないようにした場合、全てのチームの内、作業員１号及と作業員４号とからなるチームが最も生産的なチームであることになる。
【０１９９】
本願開示の方法の利点としては、ＢＰＣＰＰＰのラグランジュ双対を解くためのシステムの処理が改善することが挙げられる。より正確には、本願開示の方法は、従来技術の方法に比してよりエラーをもたらしづらいのであり、これは相当な利点である。
【０２００】
不揮発性コンピュータ可読記憶媒体がさらに開示されていることに留意されたい。不揮発性コンピュータ可読記憶媒体はコンピュータ実行可能命令を格納するために用いられるのであり、該命令は実行されるとデジタルコンピュータにＢＰＣＰＰＰのラグランジュ双対を解くための方法を行わせるのであって該方法は次のステップを含む：ＢＰＣＰＰＰを取得するステップと；収束が検出されるまでは反復的に：ラグランジュ乗数のセットを提供し、これらのラグランジュ乗数におけるＢＰＣＰＰＰのラグランジュ緩和を表すＵＢＱＰＰを提供し、ＵＢＱＰＰを量子アニーラに提供し、量子アニーラから少なくとも１つの対応する解を取得し、少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと；収束が検出された後に、対応するＢＰＣＰＰＰのラグランジュ双対の知られている最良の主双対及びＢＰＣＰＰＰの知られている最良の実行可能解の全てを提供するステップ。
【０２０１】
上述の説明は発明者らによって現在検討されている具体的な実施形態に関連しているが、広義の意味合いにおいては、本発明は説明された要素についての機能的等価物をも含むものであると解されるべきである。
【０２０２】
項１
２値多項的に制約された多項計画問題 のラグランジュ双対を解くための方法であって、該方法は、
処理装置を用いて：
２値多項的に制約された多項計画問題 を取得するステップと；
収束が検出されるまでは反復的に、
ラグランジュ乗数のセットを提供し、
提供されたラグランジュ乗数の前記セットにおける 前記２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、
前記制約無しの２値２次計画問題 を２値オプティマイザに提供し、
前記２値オプティマイザから少なくとも１つの対応する解を取得し、
前記少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと；
収束後に、対応する 前記２値多項的に制約された多項計画問題 の前記ラグランジュ双対の知られている最良の主双対及び 前記２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するステップ
とを行わせることを含む、方法。
【０２０３】
項２
項１に記載の方法において、前記２値多項的に制約された多項計画問題を取得するステップは、
多項式たる目的関数を表すデータを取得することと、
多項等式制約を表すデータを取得することと、
多項不等式制約を表すデータを取得すること
とを含む、方法。
【０２０４】
項３
項１〜２のいずれか１つに記載の方法において、前記２値多項的に制約された多項計画問題は、ユーザ、コンピュータ、ソフトウェアパッケージ及びインテリジェントエージェントの少なくとも１つから取得される、方法。
【０２０５】
項４
項１〜３のいずれか１つに記載の方法において、前記２値多項的に制約された多項計画問題を取得するステップは、ソフトウェアパラメータを初期化すること及びステップサイズサブルーチンを取得することをさらに含む、方法。
【０２０６】
項５
項４に記載の方法において、前記ソフトウェアパラメータを初期化することは、
前記２値多項的に制約された多項計画問題の一般的ラグランジュ緩和の一般的次数低減形式を、元の変数及び補助変数を用いて前記ラグランジュ乗数でパラメータ化した２値２次関数についてのパラメータ化ファミリとして提供することを含む、方法。
【０２０７】
項６
項４に記載の方法において、前記ソフトウェアパラメータを初期化することは、
前記２値多項的に制約された多項計画問題の前記一般的ラグランジュ緩和の前記一般的次数低減形式についての一般的埋め込みを提供することと、
解についてのリストを提供するための埋め込みソルバ関数を提供することと、
ラグランジュ乗数について初期値及びデフォルト値の内の１つを提供することと、
収束条件に関して誤差許容値を提供することと、
総反復回数についての制限値及び非改善反復回数についての制限値を表す整数を提供すること
とをも含む、方法。
【０２０８】
項７
項１に記載の方法において、前記２値多項的に制約された多項計画問題の初期ラグランジュ緩和は初期のラグランジュ乗数のセットを用いて生成される、方法。
【０２０９】
項８
項１に記載の方法において、前記少なくとも１つの対応する解を用いて前記２値多項的に制約された多項計画問題のラグランジュ双対の劣勾配を生成する、方法。
【０２１０】
項９
項１に記載の方法において、前記少なくとも１つの対応する解を用いて、前記２値多項的に制約された多項計画問題のラグランジュ双対についての線形再定式化のための少なくとも１つの外側近似切断を生成する、方法。
【０２１１】
項１０
項１〜９のいずれか１つに記載の方法において、前記２値多項的に制約された多項計画問題のラグランジュ双対への対応する解の提供は、前記対応する解をファイルに格納することを含む、方法。
【０２１２】
項１１
デジタルコンピュータであって：
中央処理装置と；
表示装置と；
前記デジタルコンピュータを２値オプティマイザに動作可能に接続するための通信ポートと；
２値多項的に制約された多項計画問題 のラグランジュ双対を解くためのアプリケーションを含むメモリ部であって、該アプリケーションは：
２値多項的に制約された多項計画問題を取得するための命令と；
反復的に、ラグランジュ乗数のセットを提供し、これらのラグランジュ乗数における 前記２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、前記通信ポートを用いて 前記制約無しの２次計画問題 を前記２値オプティマイザへと提供し；前記通信ポートを介して前記２値オプティマイザから少なくとも１つの対応する解を取得し、前記少なくとも１つの対応する解を用いて収束が検出されるまで新たなラグランジュ乗数のセットを生成するための命令と、
収束が検出された後に、対応する 前記２値多項的に制約された多項計画問題 のラグランジュ双対の知られている最良の主双対及び 前記２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するための命令
とを含む、メモリ部と；
前記中央処理装置と前記表示装置と前記通信ポートと前記メモリ部とを相互接続するためのデータバス
とを含む、デジタルコンピュータ。
【０２１３】
項１２
コンピュータ実行可能命令を格納するための不揮発性コンピュータ可読記憶媒体であって、該命令を実行すると、２値多項的に制約された多項計画問題 のラグランジュ双対を解くための方法をデジタルコンピュータに行わせるのであり、該方法は：
２値多項的に制約された多項計画問題を取得するステップと、
収束が検出されるまでは反復的に：
ラグランジュ乗数のセットを提供し、
これらのラグランジュ乗数における 前記２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、
前記制約無しの２次計画問題 を２値オプティマイザへと提供し、
前記２値オプティマイザから少なくとも１つの対応する解を取得し、
前記少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと、
収束が検出された後に、対応する 前記２値多項的に制約された多項計画問題 のラグランジュ双対の知られている最良の主双対及び 前記２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するステップ
とを含む、媒体。
【０２１４】
項１３
２値多項的に制約された多項計画問題 のラグランジュ双対を解くための方法であって、該方法は：
２値多項的に制約された多項計画問題 を取得するステップと；
収束が検出されるまでは反復的に、
ラグランジュ乗数のセットを提供し、
提供されたラグランジュ乗数の前記セットにおける 前記２値多項的に制約された多項計画問題 のラグランジュ緩和を表す 制約無しの２値２次計画問題 を提供し、
前記制約無しの２値２次計画問題 を２値オプティマイザに提供し、
前記２値オプティマイザから少なくとも１つの対応する解を取得し、
前記少なくとも１つの対応する解を用いて新たなラグランジュ乗数のセットを生成するステップと；
収束後に、対応する 前記２値多項的に制約された多項計画問題 の前記ラグランジュ双対の知られている最良の主双対及び 前記２値多項的に制約された多項計画問題 の知られている最良の実行可能解の全てを提供するステップ
とを含む、方法。
【０２１５】
項１４
項１〜１０及び１３のいずれか１つに記載の方法において、前記２値オプティマイザは量子アニーラを含む、方法。
【０２１６】
項１５
項１１に記載のデジタルコンピュータにおいて、前記２値オプティマイザは量子アニーラを含む、デジタルコンピュータ。
【０２１７】
項１６
項１２に記載の不揮発性コンピュータ可読記憶媒体において、前記２値オプティマイザは量子アニーラを含む、媒体。
【図１】
2019512134.tif 000031
【図２】
2019512134.tif 000032
【図３】
2019512134.tif 000033
【図４】
2019512134.tif 000034
【図５】
2019512134.tif 000035
【図６】
2019512134.tif 000036
【国際調査報告】
2019512134.tif 000037
2019512134.tif 000038
2019512134.tif 000039