(57)【要約】【課題】計算量を抑えながら、最適化問題の解を求めることができる。【解決手段】最適化問題再定式化部１３０が、処理対象の最適化問題を、離散変数についての制約と連続変数についての制約とが分離している最適化問題に再定式化する。離散変数最適化部１６０が、連続変数をある点に固定して、再定式化した最適化問題における離散変数について最適化を行う。連続変数最適化部１８０が、離散変数をある点に固定して、再定式化した最適化問題における連続変数について最適化を行う。絡み変更部２００が、再定式化した最適化問題における、離散変数と連続変数が掛け合わされている項の影響力を表す絡み係数を変更する。管理部１５０が、予め定められた停止条件を満たすまで、離散変数最適化部１６０、連続変数最適化部１８０、及び絡み変更部２００の各処理を繰り返させる。【選択図】図１
2020144529.tif 000002
【特許請求の範囲】
【請求項１】
離散変数と連続変数を含む二次計画問題であって、かつ、前記離散変数についての制約と前記連続変数についての制約とが分離している二次計画問題に定式化可能な最適化問題に対して、解を出力する問題求解装置であって、
処理対象の最適化問題を、前記離散変数についての制約と前記連続変数についての制約とが分離している最適化問題に再定式化する最適化問題再定式化部と、
前記連続変数をある点に固定して、前記再定式化した最適化問題における前記離散変数について最適化を行う離散変数最適化部と、
前記離散変数をある点に固定して、前記再定式化した最適化問題における前記連続変数について最適化を行う連続変数最適化部と、
前記再定式化した最適化問題における、前記離散変数と前記連続変数が掛け合わされている項の影響力を表す絡み係数を変更する絡み変更部と、
予め定められた停止条件を満たすまで、前記離散変数最適化部による最適化、前記連続変数最適化部による最適化、前記絡み変更部による変更を繰り返させる管理部と、
を含む問題求解装置。
【請求項２】
前記離散変数についての制約であって、不等式を含む制約のうち、現時点での解において満たさない制約及び等式で満される制約を、有効な制約として推定する有効制約推定部を更に含み、
前記管理部は、予め定められた停止条件を満たすまで、前記離散変数最適化部による最適化、前記連続変数最適化部による最適化、前記絡み変更部による変更、及び前記有効制約推定部による推定を繰り返させる請求項１記載の問題求解装置。
【請求項３】
前記離散変数最適化部は、イジングマシンを用いて、前記再定式化した最適化問題における離散変数について最適化を行う請求項１又は２記載の問題求解装置。
【請求項４】
離散変数と連続変数を含む二次計画問題であって、かつ、前記離散変数についての制約と前記連続変数についての制約とが分離している二次計画問題に定式化可能な最適化問題に対して、解を出力する問題求解装置における問題求解方法であって、
最適化問題再定式化部が、処理対象の最適化問題を、前記離散変数についての制約と前記連続変数についての制約とが分離している最適化問題に再定式化し、
離散変数最適化部が、前記連続変数をある点に固定して、前記再定式化した最適化問題における前記離散変数について最適化を行い、
連続変数最適化部が、前記離散変数をある点に固定して、前記再定式化した最適化問題における前記連続変数について最適化を行い、
絡み変更部が、前記再定式化した最適化問題における、前記離散変数と前記連続変数が掛け合わされている項の影響力を表す絡み係数を変更し、
管理部が、予め定められた停止条件を満たすまで、前記離散変数最適化部による最適化、前記連続変数最適化部による最適化、前記絡み変更部による変更を繰り返させる
問題求解方法。
【請求項５】
有効制約推定部が、前記離散変数についての制約であって、不等式を含む制約のうち、解において等式を満たす制約を、有効な制約として推定することを更に含み、
前記管理部が繰り返させることでは、予め定められた停止条件を満たすまで、前記離散変数最適化部による最適化、前記連続変数最適化部による最適化、前記絡み変更部による変更、及び前記有効制約推定部による推定を繰り返させる請求項４記載の問題求解方法。
【請求項６】
前記離散変数最適化部が最適化を行うことでは、イジングマシンを用いて、前記再定式化した最適化問題における離散変数について最適化を行う請求項４又は５記載の問題求解方法。
【請求項７】
離散変数と連続変数を含む二次計画問題であって、かつ、前記離散変数についての制約と前記連続変数についての制約とが分離している二次計画問題に定式化可能な最適化問題に対して、解を出力する問題求解処理を行うためのプログラムであって、
コンピュータに、
処理対象の最適化問題を、前記離散変数についての制約と前記連続変数についての制約とが分離している最適化問題に再定式化し、
前記連続変数をある点に固定して、前記再定式化した最適化問題における前記離散変数について最適化を行い、
前記離散変数をある点に固定して、前記再定式化した最適化問題における前記連続変数について最適化を行い、
前記再定式化した最適化問題における、前記離散変数と前記連続変数が掛け合わされている項の影響力を表す絡み係数を変更し、
予め定められた停止条件を満たすまで、前記離散変数についての最適化、前記連続変数についての最適化、及び前記絡み係数の変更を繰り返させる
ことを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、問題求解装置、方法、及びプログラムに係り、特に、最適化問題の解を求める問題求解装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
制御最適化やスケジューリング最適化等の応用をもつ、0-1混合整数二次計画問題に対する既存の解法としては、厳密解法である分枝限定法（非特許文献１）やヒューリスティック解法であるAlternating Direction Method of Multipliers (ADMM)が挙げられる（非特許文献２）。分枝限定法は各離散変数に対して、場合分けを行いながら大域的最適解を求める手法である。ADMMは、問題を変形させ、その拡張ラグランジュ関数に対して各変数を交互に最適化するものである。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Lawler, E. L., Wood, D. E. (1966). Branch-and-bound methods: A survey. Operations research, 14(4), 699-719.
【非特許文献２】Takapoui, R., Moehle, N., Boyd, S., Bemporad, A. (2017). A simple effective heuristic for embedded mixed-integer quadratic programming. International Journal of Control, 1-11.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、上記の従来技術には以下の未解決の点がある。
【０００５】
厳密解法である分枝限定法は離散変数一つ一つに関して場合分けを行う手法であるため、計算量が指数関数的に増大してしまう。ヒューリスティック解法であるADMMは最終的な解が制約を満たさない場合や悪い目的関数値をもつ解に到達する場合がある。
【０００６】
本発明は、上記事情を鑑みて成されたものであり、計算量を抑えながら、最適化問題の解を求めることができる問題求解装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、第１の態様に係る問題求解装置は、離散変数と連続変数を含む二次計画問題であって、かつ、前記離散変数についての制約と前記連続変数についての制約とが分離している二次計画問題に定式化可能な最適化問題に対して、解を出力する問題求解装置であって、処理対象の最適化問題を、前記離散変数についての制約と前記連続変数についての制約とが分離している最適化問題に再定式化する最適化問題再定式化部と、前記連続変数をある点に固定して、前記再定式化した最適化問題における前記離散変数について最適化を行う離散変数最適化部と、前記離散変数をある点に固定して、前記再定式化した最適化問題における前記連続変数について最適化を行う連続変数最適化部と、前記再定式化した最適化問題における、前記離散変数と前記連続変数が掛け合わされている項の影響力を表す絡み係数を変更する絡み変更部と、予め定められた停止条件を満たすまで、前記離散変数最適化部による最適化、前記連続変数最適化部による最適化、前記絡み変更部による変更を繰り返させる管理部と、を含んで構成されている。
【０００８】
第２の態様に係る問題求解方法は、離散変数と連続変数を含む二次計画問題であって、かつ、前記離散変数についての制約と前記連続変数についての制約とが分離している二次計画問題に定式化可能な最適化問題に対して、解を出力する問題求解装置における問題求解方法であって、最適化問題再定式化部が、処理対象の最適化問題を、前記離散変数についての制約と前記連続変数についての制約とが分離している最適化問題に再定式化し、離散変数最適化部が、前記連続変数をある点に固定して、前記再定式化した最適化問題における前記離散変数について最適化を行い、連続変数最適化部が、前記離散変数をある点に固定して、前記再定式化した最適化問題における前記連続変数について最適化を行い、絡み変更部が、前記再定式化した最適化問題における、前記離散変数と前記連続変数が掛け合わされている項の影響力を表す絡み係数を変更し、管理部が、予め定められた停止条件を満たすまで、前記離散変数最適化部による最適化、前記連続変数最適化部による最適化、前記絡み変更部による変更を繰り返させる。
【０００９】
第３の発明に係るプログラムは、離散変数と連続変数を含む二次計画問題であって、かつ、前記離散変数についての制約と前記連続変数についての制約とが分離している二次計画問題に定式化可能な最適化問題に対して、解を出力する問題求解処理を行うためのプログラムであって、コンピュータに、処理対象の最適化問題を、前記離散変数についての制約と前記連続変数についての制約とが分離している最適化問題に再定式化し、前記連続変数をある点に固定して、前記再定式化した最適化問題における前記離散変数について最適化を行い、前記離散変数をある点に固定して、前記再定式化した最適化問題における前記連続変数について最適化を行い、前記再定式化した最適化問題における、前記離散変数と前記連続変数が掛け合わされている項の影響力を表す絡み係数を変更し、予め定められた停止条件を満たすまで、前記離散変数についての最適化、前記連続変数についての最適化、及び前記絡み係数の変更を繰り返させることを実行させるためのプログラムである。
【発明の効果】
【００１０】
本発明の一態様に係る問題求解装置、方法、及びプログラムによれば、計算量を抑えながら、最適化問題の解を求めることができる、という効果が得られる。
【図面の簡単な説明】
【００１１】
【図１】本発明の第１の実施の形態に係る問題求解装置の構成を示すブロック図である。
【図２】問題パラメータ蓄積部の一例を示す図である。
【図３】最適化問題パラメータ蓄積部の一例を示す図である。
【図４】離散変数値蓄積部の一例を示す図である。
【図５】連続変数値蓄積部の一例を示す図である。
【図６】パラメータ蓄積部の一例を示す図である。
【図７】決定変数値蓄積部の一例を示す図である。
【図８】問題求解装置として機能するコンピュータの一例の概略ブロック図である。
【図９】本発明の第１の実施の形態に係る問題求解装置における問題求解処理ルーチンを示すフローチャートである。
【図１０】問題パラメータ蓄積部の一例を示す図である。
【図１１】最適化問題パラメータ蓄積部の一例を示す図である。
【図１２】離散変数値蓄積部の一例を示す図である。
【図１３】連続変数値蓄積部の一例を示す図である。
【図１４】パラメータ蓄積部の一例を示す図である。
【図１５】決定変数値蓄積部の一例を示す図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１３】
＜本発明の実施の形態に係る概要＞
まず、本発明の実施の形態における概要を説明する。
【００１４】
本発明の実施の形態では、最適化問題を連続変数に関わる部分と離散変数に関わる部分に分割し、反復的にそれらを解いていくことによって最終的な解を求める。離散変数部分に関する最適化問題については、有効な制約を推定することで問題を適切に変形させる。これにより、イジングマシンが使用できる問題形式になるため、高速に問題を解くことが可能になる。また、目的関数に対して適切に障壁関数を設定することで、解に制約を満たすように働きかけることが可能となる。さらに、目的関数において連続変数と離散変数が掛け合わされている部分に、係数パラメータを導入することで、その部分の影響力を反復ごとに変化させる。その結果、比較的良い目的関数値をもつ最終的な解を得ることができる。
【００１５】
ここで、イジングマシンとは、組合せ最適化問題をイジングモデルで表現し、組合せ最適化問題を解決するマシンの総称（参考文献１）である。具体的なイジングマシンとしては、D-wave （参考文献２）、富士通デジタルアニーラ（参考文献２）、CMOS アニーリングマシン（参考文献４）、LASOLV （参考文献５）などが挙げられる。
【００１６】
［参考文献１］ 産総研：量子アニーリングマシンを使いこなす共通ソフトウェア基盤の研究開発に採択（最終閲覧日：2018 年1 月25 日）https://www.aist.go.jp/aist j/press release/pr2018/pr20181009/pr20181009.html#b
［参考文献２］D-wave The quantum computing Company（ 最終閲覧日：2018 年1 月25 日） https://www.dwavesys.com/home
［参考文献３］デジタルアニーラ- 富士通の新アーキテクチャコンピュータ: Fujitsu Japan（最終閲覧日：2018 年1 月25 日） http://www.fujitsu.com/jp/digitalannealer/
［参考文献４］ニュースリリース：2018 年9 月19 日：日立- 日立製作所（ 最終閲覧日：2018 年1 月25 日） http://www.hitachi.co.jp/New/cnews/month/2018/09/0919.html
［参考文献５］ 光を使った新しいコンピュータ「LASOLV」（ 最終閲覧日：2018 年1 月25 日） http://www.ntt.co.jp/event/2018/pdf/ceatec18/10 future-tech ntt.pdf
【００１７】
イジングマシンで解くことが可能な問題は以下のような無制約0-1 整数二次計画問題である。
【００１８】
【数１】
2020144529.tif 000003
【００１９】
ここで、
2020144529.tif 000004
はn×nの定行列、
2020144529.tif 000005
はn次元の定ベクトルである。
【００２０】
［第１の実施の形態］
＜本発明の第１の実施の形態に係る問題求解装置の構成＞
次に、本発明の実施の形態に係る問題求解装置の構成について説明する。図１に示すように、本発明の実施の形態に係る問題求解装置１０は、ＣＰＵと、ＲＡＭと、後述する問題求解処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この問題求解装置１０は、機能的には図１に示すように操作部１１０と、演算部２０と、出力部２５０とを備えている。
【００２１】
操作部１１０は、離散変数についての制約と連続変数についての制約が分離している0-1混合整数二次計画問題に定式化可能な最適化問題を、処理対象として受け付ける。ここで、0-1混合整数二次計画問題とは、離散変数と連続変数の双方を変数として持ち、離散変数が０又は１である二次計画問題である。
【００２２】
具体的には、以下のような問題を受け付ける。
【００２３】
【数２】
2020144529.tif 000006
(1)
【００２４】
但し、決定変数は
2020144529.tif 000007
であり、定数は
2020144529.tif 000008
2020144529.tif 000009
である。また、
2020144529.tif 000010
であり、全てのi、j について、
2020144529.tif 000011
である。ここで、新たな離散変数
2020144529.tif 000012
と等式制約
2020144529.tif 000013
を導入すれば、
2020144529.tif 000014
は
2020144529.tif 000015
と変更することができるため、上記の問題において、
2020144529.tif 000016
とおいても一般性を失わない。
【００２５】
上記の問題形式に変更できる応用には、異なる動力をもつ車両の動力配分決定問題（参考文献８）、経済給電のための最適化問題（参考文献９）、発電所のスケジューリング問題（参考文献１０）や車両の最適経路問題（参考文献１１）など、多くの問題が存在する。
【００２６】
［参考文献８］Boyd, S.,Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
［参考文献９］Papageorgiou, L. G., Fraga, E. S. (2007). A mixed integer quadratic programming formulation for the economic dispatch of generators with prohibited operating zones. Electric power systems research, 77(10), 1292-1296.
［参考文献１０］Catalao, J. P. D. S., Pousinho, H. M. I., Mendes, V. M. F. (2010). Scheduling of head-dependent cascaded hydro systems: Mixed-integer quadratic programming approach. Energy Conversion and Management, 51(3), 524-530.
［参考文献１１］Schouwenaars, T., De Moor, B., Feron, E., How, J. (2001). Mixed integer programming for multi-vehicle path planning. In Control Conference (ECC), 2001 European (pp. 2603-2608). IEEE.
【００２７】
演算部２０は、問題パラメータ蓄積部１２０、最適化問題再定式化部１３０、最適化問題パラメータ蓄積部１４０、最適化部１００、及び決定変数値蓄積部２４０を含んで構成されている。
【００２８】
最適化部１００は、管理部１５０、離散変数最適化部１６０、離散変数値蓄積部１７０、連続変数最適化部１８０、連続変数値蓄積部１９０、絡み変更部２００、パラメータ蓄積部２１０、有効制約推定部２２０、及び停止条件判定部２３０を備えている。
【００２９】
最適化問題再定式化部１３０は、受け付けた最適化問題を別の問題形式へ変形するように再定式化する。離散変数最適化部１６０は、再定式化された問題から離散変数部分についてのみ切り出した問題を変形し、イジングマシンで解く。連続変数最適化部１８０は、再定式化された問題から連続変数部分についてのみ切り出した問題を、古典コンピュータで解く。絡み変更部２００は、離散変数と連続変数が掛け合わされている項の影響力を変化させることで、最終的な解が極端に悪い解となることを防ぐ。有効制約推定部２２０は、離散変数に関する不等式で解において等式が成り立つものを推定することで、離散変数最適化部１６０で元の問題をイジングマシンで解くことができる問題に変形することが可能となる。停止条件判定部２３０は停止条件を満たすか否かを判定し、停止条件が満たされる場合、反復を終了させる。管理部１５０は、離散変数最適化部１６０、連続変数最適化部１８０、絡み変更部２００、有効制約推定部２２０、及び停止条件判定部２３０を反復的に呼び出し、実行する。
【００３０】
次に、問題求解装置１０の各部の詳細な説明を以下に記載する。
【００３１】
問題パラメータ蓄積部１２０は、上記最適化問題における定数パラメータを格納しており、問題求解装置１０からの要求に従い定数パラメータを読み出し、最適化問題再定式化部１３０に送信する。具体的には、最適化問題(1) の定数パラメータである
2020144529.tif 000017
2020144529.tif 000018
の情報である。問題パラメータ蓄積部１２０に蓄積されるものの例を図２に示す。
【００３２】
最適化問題再定式化部１３０は、問題パラメータ蓄積部１２０から送信された問題パラメータを用いて、離散変数についての制約と連続変数についての制約が分離している0-1 混合整数二次計画問題へと定式化を行う。以下、定式化の方法の一例について説明する。
【００３３】
まず、十分大きな定数Mとスラック変数
2020144529.tif 000019
を導入することで、離散変数についての制約と連続変数についての制約とが分離するように、最適化問題(1)を以下のように定式化することができる。
【００３４】
【数３】
2020144529.tif 000020
（２）
【００３５】
この問題は、離散変数についての制約と連続変数についての制約とが分離している0-1 混合整数二次計画問題であり、決定変数ｘ、ｓを決定変数ｘと再定義し、定数に変更を行うことで以下のような問題形式に変換することができる。
【００３６】
【数４】
2020144529.tif 000021
【００３７】
このとき、決定変数は
2020144529.tif 000022
であり、定数は
2020144529.tif 000023
2020144529.tif 000024
である。
【００３８】
このようにして最適化問題再定式化部１３０により再定式化された最適化問題(2)は最適化問題パラメータ蓄積部１４０へと格納される。最適化問題パラメータ蓄積部１４０に蓄積されるものの例を図３に示す。最適化問題パラメータ蓄積部１４０は問題求解装置１０の要求に従い、最適化問題パラメータを読み出し、管理部１５０に送信する。
【００３９】
管理部１５０では、後述する離散変数と連続変数を交互に最適化するアルゴリズムの手順に沿って、離散変数最適化部１６０、連続変数最適化部１８０、絡み変更部２００、有効制約推定部２２０、停止条件判定部２３０を呼び出し、停止条件判定部２３０において停止条件が満たされたとみなされたとき、決定変数値蓄積部２４０に、得られた解を格納する。以下、具体的なアルゴリズムを与える。
【００４０】
まず、離散変数最適化部１６０は、連続変数をある点に固定したときの、最適化問題(2)における離散変数を最適化する。最適化問題(2)の連続変数を
2020144529.tif 000025
と固定し、定数項を取り除き、
2020144529.tif 000026
に係数η をつけると、以下のような最適化問題となる。
【００４１】
【数５】
2020144529.tif 000027
【００４２】
ここで、ηは連続変数と離散変数の掛け合わされている項の影響力の度合いを変化させるものであり、ηが大きければ大きいほど、連続変数
2020144529.tif 000028
を考慮している問題となる。この係数ηは絡み変更部２００によってパラメータ蓄積部２１０に蓄積されているものを参照したものである。
【００４３】
さらに、離散変数最適化部１６０は、上記の最適化問題（２）を、各反復でイジングマシンで解くために以下のように変更する。
【００４４】
【数６】
2020144529.tif 000029
【００４５】
ここで、
2020144529.tif 000030
の項は等式制約に関する障壁関数であり、ペナルティパラメータμ1が十分大きいとき解は等式制約を満たす。
【００４６】
2020144529.tif 000031
の項は不等式制約に関する障壁関数であり、ペナルティパラメータμ2 が十分大きいとき解は
2020144529.tif 000032
について
2020144529.tif 000033
または
2020144529.tif 000034
をなるべく満たすように決定される。ここで、
2020144529.tif 000035
は不等式制約の中で有効と推定される制約の添え字集合であり、有効制約推定部２２０によってパラメータ蓄積部２１０に蓄積されたものを参照したものである。この問題は0-1変数のみの無制約二次計画問題であるため、各イジングマシンを用いて解くことができる。
【００４７】
離散変数における不等式制約については、新たに変数を導入することで等式制約に変換する手法（参考文献１２）が既に考案されているが、上記の有効な制約を推定する手法は新たに変数を導入する必要が無く、変数の数に制限のあるイジングマシン上で実装を行いやすいという特徴をもつ。
【００４８】
次に、連続変数最適化部１８０は、離散変数を固定したときの、最適化問題における連続変数を最適化する。元の最適化問題(2) の離散変数を
2020144529.tif 000036
と固定し、定数項を取り除き、
2020144529.tif 000037
に係数ηをつけると、以下のような最適化問題となる。
【００４９】
【数７】
2020144529.tif 000038
【００５０】
このとき、η が大きければ大きいほど、離散変数
2020144529.tif 000039
を考慮している問題となる。この係数ηは絡み変更部２００によって、パラメータ蓄積部２１０に蓄積されているものを参照したものである。
【００５１】
上記の最適化問題は
2020144529.tif 000040
が半正定値対称行列であるとき、凸二次計画問題であり、主双対内点法などの各種内点法を用いて解くことができる。
【００５２】
以上の離散変数部分の最適化と連続変数部分の最適化に加え、各パラメータの更新を行う、後述のアルゴリズム中では、
2020144529.tif 000041
の部分で、絡み変更部２００が絡みの係数ηを逐次更新している。このようにして離散変数と連続変数が掛け合わされている項の影響力を段々と大きくしていくことで極端に悪い解へと収束してしまうことを防ぐ。
【００５３】
また、有効制約推定部２２０は、離散変数に関する制約であって、不等式を含む制約のうち、現時点での解において満たさない制約及び等式で満たされる制約を、有効な制約として推定する。具体的には、有効制約推定部２２０は、有効と推定される制約の集合
2020144529.tif 000042
を、現時点の離散変数の値zkにおいて等式で満たされる制約と、満たしていない制約とからなる集合としている。離散変数に関して最適化を行う際には
2020144529.tif 000043
について
2020144529.tif 000044
であるときも、この制約に対応する障壁関数の値は0となる。そのため、
2020144529.tif 000045
について
2020144529.tif 000046
となる場合が生じるので，不必要な制約は次の反復で有効と推定される制約集合から外れることになる。このアルゴリズムを用いることによって、最適化問題(2)、すなわち最適化問題(1) の解を求めることができる。
【００５４】
具体的なアルゴリズムは以下のようなものとなる。
【００５５】
【数８】
2020144529.tif 000047
【００５６】
離散変数値蓄積部１７０は、各反復において離散変数最適化部１６０によって計算された離散変数
2020144529.tif 000048
を記憶する。連続変数値蓄積部１９０は、各反復において連続変数最適化部１８０によって計算された連続変数
2020144529.tif 000049
を記憶する。パラメータ蓄積部２１０は各反復において絡み変更部２００によって計算されたパラメータηk+1と有効制約推定部２２０によって計算されたパラメータ
2020144529.tif 000050
を記憶する。離散変数値蓄積部１７０に蓄積するデータの例を図４に示す。連続変数値蓄積部１９０に蓄積するデータの例を図５に示す。パラメータ蓄積部２１０に蓄積するデータの例を図６に示す。
【００５７】
出力部２５０は、決定変数値蓄積部２４０に格納された解を読み込み、それを出力する。決定変数値蓄積部２４０に蓄積するデータの例を図７に示す。
【００５８】
問題求解装置１０は、一例として、図８に示すコンピュータ８４によって実現される。コンピュータ８４は、ＣＰＵ８６、メモリ８８、プログラム８２を記憶した記憶部９２、モニタを含む表示部９４、及びキーボードやマウスを含む入力部９６を含んでいる。ＣＰＵ８６、メモリ８８、記憶部９２、表示部９４、及び入力部９６はバス９８を介して互いに接続されている。
【００５９】
記憶部９２はＨＤＤ、ＳＳＤ、フラッシュメモリ等によって実現される。記憶部９２には、コンピュータ８４を問題求解装置１０として機能させるためのプログラム８２が記憶されている。ＣＰＵ８６は、プログラム８２を記憶部９２から読み出してメモリ８８に展開し、プログラム８２を実行する。なお、プログラム８２をコンピュータ可読媒体に格納して提供してもよい。
【００６０】
＜本発明の第１の実施の形態に係る問題求解装置１０の作用＞
次に、本発明の実施の形態に係る問題求解装置１０の作用について説明する。問題求解装置１０において、操作部１１０は、離散変数についての制約と連続変数についての制約が分離している0-1混合整数二次計画問題に定式化可能な最適化問題を、処理対象として受け付けると、処理対象の最適化問題における定数パラメータを問題パラメータ蓄積部１２０に格納する。そして、問題求解装置１０は、図９に示す問題求解処理ルーチンを実行する。
【００６１】
まず、ステップＳ１００では、最適化問題再定式化部１３０は、処理対象の最適化問題における定数パラメータを取得する。
【００６２】
ステップＳ１０２では、最適化問題再定式化部１３０は、問題パラメータ蓄積部１２０から送信された問題パラメータを用いて、離散変数についての制約と連続変数についての制約が分離している0-1 混合整数二次計画問題へと定式化を行う。
【００６３】
ステップＳ１０４では、管理部１５０は、離散変数と連続変数、絡みの係数、及び有効制約を初期化する。
【００６４】
ステップＳ１０６では、離散変数最適化部１６０は、離散変数と連続変数、絡みの係数、及び有効制約に基づいて、連続変数をある点に固定したときの、上記ステップＳ１０２で定式化された最適化問題における離散変数を最適化する。
【００６５】
ステップＳ１０８では、連続変数最適化部１８０は、離散変数と連続変数、絡みの係数、及び有効制約に基づいて、離散変数を固定したときの、上記ステップＳ１０２で定式化された最適化問題における連続変数を最適化する。
【００６６】
ステップＳ１１０では、絡み変更部２００が、離散変数と連続変数が掛け合わされている項の影響力を段々と大きくするように絡みの係数ηを更新する。
【００６７】
ステップＳ１１２では、有効制約推定部２２０は、離散変数に関する制約であって、不等式を含む制約のうち、現時点での離散変数の値において満たさない制約及び等式で満たされる制約を、有効な制約として推定する。
【００６８】
ステップＳ１１４では、停止条件判定部２３０が、停止条件を満たすかを判定し、停止条件を満たしていれば、管理部１５０が、ステップＳ１１６へ移行し、条件を満たしていなければ、管理部１５０が、ステップＳ１０６〜Ｓ１１４の処理を繰り返す。
【００６９】
ステップＳ１１６では、出力部２５０は、上記ステップＳ１０６、Ｓ１０８で最終的に得られた連続変数及び離散変数である解を読み込み、それを出力し、問題求解処理ルーチンを終了する。
【００７０】
以上説明したように、本発明の第１の実施の形態に係る問題求解装置は、処理対象の最適化問題を、離散変数についての制約と連続変数についての制約とが分離している最適化問題に再定式化し、イジングマシンを用いて、連続変数をある点に固定して、再定式化した最適化問題における離散変数について最適化を行うことと、古典コンピュータを用いて、離散変数をある点に固定して、再定式化した最適化問題における連続変数について最適化を行うことを繰り返す。これにより、計算量を抑えながら、最適化問題の解を求めることができる。
【００７１】
また、イジングマシンを活用することによって計算量を抑えることができるため、高速な求解が可能となる。また、反復解法であることを利用して、有効な制約を推定していくことで障壁関数の導入が可能となり、解に制約を満たさせることができる。
【００７２】
また、再定式化した最適化問題における、離散変数と連続変数が掛け合わされている項の影響力を表す絡み係数を変更することを反復毎に行うことにより、悪い局所解に陥ることを防ぎ、最終的な目的関数値も良い値となる。
【００７３】
［第２の実施の形態］
第２の実施の形態では、処理対象となる最適化問題として、エンジンと電力の二つを動力として持つ車両の動力配分スケジューリング問題を考える。この最適化問題は既に既存の文献（参考文献１３）で定式化されている、以下のような最適化問題である。
【００７４】
【数９】
2020144529.tif 000051
(3)
【００７５】
但し、
2020144529.tif 000052
である。
【００７６】
［参考文献１３］Boyd, S., Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
【００７７】
決定変数は各t に対する
2020144529.tif 000053
であり、それぞれ時刻t におけるバッテリーの残量、エンジンによる動力量、電力による動力量、エンジンの電源のON-OFF を表す変数である。定数は
2020144529.tif 000054
であり、それぞれ残存電力に関するコスト係数、電力の最大保有量、終端時刻、エンジンの起動にかかるコスト係数、各時刻に対する動力需要量、エンジンの最大動力量、エンジンの動力量に対するコスト関数の二次の係数、エンジンの動力量に対するコスト関数の一次の係数、エンジンの起動中にかかる固定コスト量を表している。目的関数については、
2020144529.tif 000055
が終端時刻の電力の残量が少ないと増大するコスト関数、
2020144529.tif 000056
がエンジンによる出力にかかるコスト関数、
2020144529.tif 000057
がエンジンの起動にかかるコスト関数となっている。制約については、一つ目が電力残量の動的システム、二つ目が動力需要を総動力量が上回るための制約、三つめがエンジンによる動力量に対する制約となっている。
【００７８】
＜本発明の第２の実施の形態に係る問題求解装置の構成＞
次に、本発明の第２の実施の形態に係る問題求解装置の構成について説明する。なお、本発明の第２の実施の形態に係る問題求解装置の構成は、第１の実施の形態と同様であるため、同一符号を付して詳細な説明を省略する。
【００７９】
問題パラメータ蓄積部１２０は上記最適化問題における定数パラメータを格納しており、問題求解装置１０からの要求に従い定数パラメータを読み出し、最適化問題再定式化部１３０に送信する。具体的には、最適化問題(3) の定数パラメータである
2020144529.tif 000058
およびt = 0, 1,...,T-1 におけるPtdesの情報である。問題パラメータ蓄積部１２０に蓄積されるものの例を図１０に示す。
【００８０】
最適化問題再定式化部１３０は、問題パラメータ蓄積部１２０から送信された問題パラメータを用いて、離散変数と連続変数について制約が分離している0-1 混合整数二次計画問題へと定式化を行う。以下、定式化の方法の一例について説明する。
【００８１】
十分大きな定数M を導入することで、最適化問題(3) は以下のように定式化することができる。
【００８２】
【数１０】
2020144529.tif 000059
【００８３】
この問題は離散変数と連続変数について制約が分離している0-1 混合整数二次計画問題であり、正しい変換を行うことで以下のような問題形式に変換することができる。
【００８４】
【数１１】
2020144529.tif 000060
(4)
【００８５】
このとき、決定変数は
2020144529.tif 000061
であり、定数は
2020144529.tif 000062
である。
【００８６】
以下、離散変数に関する等式の項が無いことと、連続変数部分の最適化が内点法で解くことができることを除き、上記第１の実施の形態と同一である。
【００８７】
このようにして最適化問題再定式化部１３０により再定式化された最適化問題(4) は最適化問題パラメータ蓄積部１４０へと格納される。蓄積されるものの例を図１１に示す。
【００８８】
最適化問題パラメータ蓄積部１４０は問題求解装置１０の要求に従い、最適化問題パラメータを読み出し、管理部１５０に送信する。
【００８９】
管理部１５０は、後述する離散変数と連続変数を交互に最適化するアルゴリズムの手順に沿って、離散変数最適化部１６０、連続変数最適化部１８０、絡み変更部２００、有効制約推定部２２０、停止条件判定部２３０を呼び出し、停止条件判定部２３０において反復の回数が最大反復回数に達したとみなされたとき、決定変数値蓄積部２４０に得られた解を格納する。以下、具体的なアルゴリズムを与える。
【００９０】
まず、離散変数最適化部１６０は、連続変数をある点に固定したときの、最適化問題(4)における離散変数を最適化する。具体的には、最適化問題(4) の連続変数を
2020144529.tif 000063
と固定し、定数項を取り除き、
2020144529.tif 000064
に係数ηをつけると、以下のような最適化問題となる。
【００９１】
【数１２】
2020144529.tif 000065
【００９２】
ここで、ηは連続変数と離散変数の掛け合わされている項の影響力の度合いを変化させるものであり、ηが大きければ大きいほど、連続変数
2020144529.tif 000066
を考慮している問題となる。
【００９３】
さらに、上記の問題を各反復でイジングマシンで解くために以下のように変更する。
【００９４】
【数１３】
2020144529.tif 000067
【００９５】
ここで、
2020144529.tif 000068
の項は不等式制約に関する障壁関数であり、ペナルティパラメータμ2が十分大きいとき解は
2020144529.tif 000069
について
2020144529.tif 000070
をなるべく満たすように決定される。また、
2020144529.tif 000071
は不等式制約の中で有効と推定される制約の添え字集合であり、アルゴリズム中の各反復において更新される。
【００９６】
この問題は0-1 変数のみの無制約二次計画問題であるため、各イジングマシンを用いて解くことができる。
【００９７】
離散変数における不等式制約については、新たに変数を導入することで等式制約に変換する手法（参考文献１２）が既に考案されているが、上記の有効な制約を推定する手法は新たに変数を導入する必要が無く、変数の数に制限のあるイジングマシン上で実装を行いやすいという特徴をもつ。
【００９８】
次に、連続変数最適化部１８０は、離散変数を固定したときの、最適化問題（４）における連続変数を最適化する。元の問題(4) の離散変数を
2020144529.tif 000072
と固定し、定数項を取り除き、
2020144529.tif 000073
に係数ηをつけると、以下のような最適化問題となる。
【００９９】
【数１４】
2020144529.tif 000074
【０１００】
このとき、ηが大きければ大きいほど、離散変数zを考慮している問題となる。
【０１０１】
上記の最適化問題は問題(3) の特性より、P1 が半正定値対称行列であるため、凸二次計画問題である。そのため、主双対内点法などの各種内点法を用いて解くことができる。
【０１０２】
以上の離散変数部分の最適化と連続変数部分の最適化に加え、各パラメータの更新を行う具体的なアルゴリズムは以下のようなものとなる。
【０１０３】
【数１５】
2020144529.tif 000075
【０１０４】
上記のアルゴリズム中では、有効と推定される制約の集合
【０１０５】
を、現在の離散変数の値zkにおいて有効である制約と満たしていない制約の集合としている。離散変数に関して最適化を行う際には
2020144529.tif 000076
について
2020144529.tif 000077
であるときも、この制約に対応する障壁関数の値は0となる。そのため、
2020144529.tif 000078
について
2020144529.tif 000079
となる場合が生じるので，不必要な制約は次の反復で有効と推定される制約集合から外れることになる。このアルゴリズムを用いることによって、最適化問題(4)、すなわち最適化問題(3) の解を求めることができる。
【０１０６】
離散変数値蓄積部１７０は各反復において、離散変数最適化部１６０によって計算された離散変数
2020144529.tif 000080
を記憶する。連続変数値蓄積部１９０は各反復において連続変数最適化部１８０によって計算された連続変数
2020144529.tif 000081
を記憶する。問題パラメータ蓄積部１２０は各反復において絡み変更部２００によって計算されたパラメータηk+1と有効制約推定部２２０によって計算されたパラメータ
2020144529.tif 000082
を記憶する。最適化問題パラメータ蓄積部１４０に蓄積するデータの例を図１１に示す。離散変数値蓄積部１７０に蓄積するデータの例を図１２に示す。連続変数値蓄積部１９０に蓄積するデータの例を図１３に示す。パラメータ蓄積部２１０に蓄積するデータの例を図１４に示す。
【０１０７】
出力部２５０は、決定変数値蓄積部２４０に格納された解を読み込み、それを出力する。決定変数値蓄積部２４０に蓄積するデータの例を図１５に示す。
【０１０８】
なお、第２の実施の形態に係る問題求解装置１０の他の構成及び作用については、第１の実施の形態と同様の構成となるため、説明を省略する。
【０１０９】
以上説明したように、本発明の第２の実施の形態に係る問題求解装置は、処理対象の最適化問題を、離散変数についての制約と連続変数についての制約とが分離している最適化問題に再定式化し、イジングマシンを用いて、連続変数をある点に固定して、再定式化した最適化問題における離散変数について最適化を行うことと、古典コンピュータを用いて、離散変数をある点に固定して、再定式化した最適化問題における連続変数について最適化を行うことを繰り返す、これにより、計算量を抑えながら、最適化問題の解を求めることができる。
【０１１０】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【０１１１】
１０   問題求解装置
２０   演算部
８２   プログラム
８４   コンピュータ
１００ 最適化部
１１０ 操作部
１２０ 問題パラメータ蓄積部
１３０ 最適化問題再定式化部
１４０ 最適化問題パラメータ蓄積部
１５０ 管理部
１６０ 離散変数最適化部
１７０ 離散変数値蓄積部
１８０ 連続変数最適化部
１９０ 連続変数値蓄積部
２００ 絡み変更部
２１０ パラメータ蓄積部
２２０ 有効制約推定部
２３０ 停止条件判定部
２４０ 決定変数値蓄積部
２５０ 出力部
【図１】
2020144529.tif 000083
【図２】
2020144529.tif 000084
【図３】
2020144529.tif 000085
【図４】
2020144529.tif 000086
【図５】
2020144529.tif 000087
【図６】
2020144529.tif 000088
【図７】
2020144529.tif 000089
【図８】
2020144529.tif 000090
【図９】
2020144529.tif 000091
【図１０】
2020144529.tif 000092
【図１１】
2020144529.tif 000093
【図１２】
2020144529.tif 000094
【図１３】
2020144529.tif 000095
【図１４】
2020144529.tif 000096
【図１５】
2020144529.tif 000097