(57)【要約】【課題】決定変数がバイナリ変数でない最適化問題を高速に解くこと。【解決手段】最適化装置は、混合整数計画問題が入力されると、前記混合整数計画問題の決定変数のうち、連続値又は整数値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手段と、前記組み合わせ最適化問題の最適解を量子コンピューティング装置に計算させる計算手段と、前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手段と、を有することを特徴とする。【選択図】図２
2020113190.tif 000002
【特許請求の範囲】
【請求項１】
混合整数計画問題が入力されると、前記混合整数計画問題の決定変数のうち、連続値又は整数値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手段と、
前記組み合わせ最適化問題の最適解を量子コンピューティング装置に計算させる計算手段と、
前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手段と、
を有することを特徴とする最適化装置。
【請求項２】
前記第１の変換手段は、
複数のバイナリ変数の重み付け和を用いて、前記連続値又は整数値を取る決定変数を離散化する、ことを特徴とする請求項１に記載の最適化装置。
【請求項３】
前記重み付け和の各重みは、
前記連続値又は整数値を取る決定変数の定義域を均等に分割する点列、又は、等比数列で表される点列のいずれかである、ことを特徴とする請求項２に記載の最適化装置。
【請求項４】
前記第１の変換手段は、
前記重み付け和の各重みが、前記連続値又は整数値を取る決定変数の定義域を均等に分割する点列である場合、前記組み合わせ最適化問題の制約条件として、前記複数のバイナリ変数の合計が１以下であることを表す制約条件を追加する、ことを特徴とする請求項３に記載の最適化装置。
【請求項５】
前記重み付け和の合計値は、前記連続値又は整数値を取る決定変数の定義域の範囲と一致する、ことを特徴とする請求項２乃至４の何れか一項に記載の最適化装置。
【請求項６】
前記計算手段は、
前記組み合わせ最適化問題の最適解を、前記量子コンピューティング装置又は組み合わせ最適化問題の計算に特化した計算機のいずれかに計算させる、ことを特徴とする請求項１乃至５の何れか一項に記載の最適化装置。
【請求項７】
前記量子コンピューティング装置には、量子コンピュータが含まれる、ことを特徴とする請求項１乃至６の何れか一項に記載の最適化装置。
【請求項８】
前記混合整数計画問題の最適解又は前記混合整数計画問題の最適解に所定の処理を施した結果を、前記最適化装置が備える表示装置又は前記最適化装置とは異なる他の装置が備える表示装置に表示させる、ことを特徴とする請求項１乃至７の何れか一項に記載の最適化装置。
【請求項９】
最適化装置と、量子コンピューティング装置と、端末装置とが含まれる最適化システムであって、
前記最適化装置は、
混合整数計画問題が入力されると、前記混合整数計画問題の決定変数のうち、連続値又は整数値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手段と、
前記組み合わせ最適化問題の最適解を、通信ネットワークを介して接続される前記量子コンピューティング装置に計算させる計算手段と、
前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手段と、
前記混合整数計画問題の最適解を、通信ネットワークを介して接続される前記端末装置に表示させる表示手段と、
を有することを特徴とする最適化システム。
【請求項１０】
混合整数計画問題が入力されると、前記混合整数計画問題の決定変数のうち、連続値又は整数値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手順と、
前記組み合わせ最適化問題の最適解を量子コンピューティング装置に計算させる計算手順と、
前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手順と、
をコンピュータが実行することを特徴とする最適化方法。
【請求項１１】
混合整数計画問題が入力されると、前記混合整数計画問題の決定変数のうち、連続値又は整数値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手順と、
前記組み合わせ最適化問題の最適解を量子コンピューティング装置に計算させる計算手順と、
前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手順と、
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置、最適化システム、最適化方法、及びプログラムに関する。
【背景技術】
【０００２】
複数の生産者が生産する資源（例えば、電力、ガス、蒸気等）を複数の需要家に配分する場合にコストが最適となるように決定するシステムや、生産ラインで生産される製品についての供給量を配分する場合に目的関数を設定して最適化問題を解くことで最適な供給量の配分を決定するシステムが一般的に知られている（例えば、非特許文献１及び２）。これらの最適化システムでは、最適化問題を解く際に、分枝限定法やメタヒューリスティックス等のアルゴリズム、又はこれらのアルゴリズムに基づいた最適化ソルバを使用して、最適解を計算している。
【０００３】
一方で、量子ゲートマシンやイジングマシン（量子アニーリングマシン、コヒーレントイジングマシン、量子ニューラルネットワークマシン、デジタル回路によるイジングマシン等）といった、量子コンピューティングを実現する装置（以降、「量子コンピューティング装置」という。）を使用して、組み合わせ最適化問題を解く方法が知られている（例えば、非特許文献３乃至８）。また、ＤＮＮ（Deep Neural Network）の結合係数の組み合わせを量子コンピューティング装置により最適化する方法が知られている（例えば、特許文献１）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１７−５９０７１号公報
【非特許文献】
【０００５】
【非特許文献１】鈴木亮平，岡本卓，「エネルギープラント運用計画のための最適化ベンチマーク問題」，平成24年電気学会電子・情報・システム部門大会，ｐｐ３１８−３２１
【非特許文献２】岡本卓，足立直紀，鈴木亮平，小圷成一，平田廣則，「エネルギープラント運用計画問題と最適化手法の適用例」，平成２６年電気学会全国大会，第４分冊，S21(17)−S21(20)
【非特許文献３】田中宗，「量子アニーリング技術の最前線」，平成３０年電気学会全国大会，第４分冊，S4(5)−S4(6)
【非特許文献４】宇都宮聖子，「量子コンピュータの新潮流：量子アニーリングとD-Wave」，人工知能Vol.29，No.2，pp190-194
【非特許文献５】塚本三六，高津求，松原聡，田村泰孝，「組み合わせ最適化問題向けハードウェアの高速化アーキテクチャー」，FUJITSU，Vol68，Vol.5，pp8-14
【非特許文献６】武居弘樹，稲垣卓弘，稲葉謙介，本庄利守，「複雑な組合わせ最適化問題を解く量子ニューラルネットワーク」，NTT技術ジャーナル
【非特許文献７】山岡雅直，吉村地尋，林真人，奥山 拓哉，青木秀貴，水野弘之，「AIの基礎研究  イジング計算機」，日立評論 2016.04，pp65-68
【非特許文献８】J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E.Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo,N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley,N. Tezak, W. J. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti, "Unsupervised Machine Learning on a Hybrid Quantum Computer", arXiv preprint arXiv:1712.05771, 2017.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ここで、一般に、最適化システムでは、システムの要求仕様を満たすように、最適化問題を所定の時間内に解く必要がある。しかしながら、例えば、最適化問題が大規模かつ複雑になると計算時間が増大してしまい、要求仕様を満たせなくなってしまう場合があった。
【０００７】
これに対して、量子コンピューティング装置により最適化問題を解くことができれば計算時間を大幅に削減することができるが、最適化問題の決定変数が連続値又は整数値である場合（つまり、決定変数がバイナリ変数でない場合）には、量子コンピューティング装置により最適化問題を解くことができなかった。
【０００８】
本発明は、上記の点に鑑みてなされたもので、決定変数がバイナリ変数でない最適化問題を高速に解くことを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明の実施の形態における最適化装置は、混合整数計画問題が入力されると、前記混合整数計画問題の決定変数のうち、連続値又は整数値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手段と、前記組み合わせ最適化問題の最適解を量子コンピューティング装置に計算させる計算手段と、前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手段と、を有することを特徴とする。
【発明の効果】
【００１０】
決定変数がバイナリ変数でない最適化問題を高速に解くことができる。
【図面の簡単な説明】
【００１１】
【図１】本実施形態に係る最適化システムの全体構成の一例を示す図である。
【図２】本実施形態に係る最適化装置のハードウェア構成の一例を示す図である。
【図３】本実施形態に係る最適化装置の機能構成の一例を示す図である。
【図４】本実施形態に係る最適化処理の一例を示すフローチャートである。
【図５】実施例１における系統モデルを示す図である。
【図６】実施例１における最適化結果を示す図である。
【図７】実施例２における最適化結果を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態（以降、「本実施形態」とも表す。）について説明する。本実施形態では、決定変数（の一部）がバイナリ変数でない混合整数計画問題が与えられた場合に、量子コンピュータ等を使用して、この混合整数計画問題を高速に解くことが可能な最適化システム１について説明する。なお、混合整数計画問題とは、整数値を取る変数と実数値を取る変数とが混在している最適化問題のことである。
【００１３】
ここで、本実施形態では、特に言及した場合を除き、混合整数計画問題は、以下で表されるものとする。
【００１４】
【数１】
2020113190.tif 000003
ここで、E(x,y)は目的関数、g(x,y)≦0及びh(x,y)=0は制約条件、xは実数値を取る決定変数xkを要素とするベクトル、yは0又は1のいずれかを取る決定変数
【００１５】
【数２】
2020113190.tif 000004
を要素とするベクトル、Nxはxの次元数（要素数）、Nyはyの次元数（要素数）である。例えば、或る需給系統の最適化問題を考える場合、Eはコスト、xkは設備が生産する資源の供給量、yは各設備の稼働状態（0が稼働停止、1が稼働中）、g(x,y)≦0及びh(x,y)=0は各設備の制約条件となる。
【００１６】
なお、便宜上、明細書のテキストでは、ベクトルを太字ではなく、通常の書体で表す。例えば、上記の数１に示すx、y、g及びhはいずれもベクトルであるが、明細書のテキストでは通常の書体で表す。
【００１７】
上記の数１では、x、y、g及びhはいずれもベクトルであるものとしたが、これに限られず、スカラーであってもよい。また、上記の数１では、目的関数を最小化する場合（つまり、最小化問題）を示しているが、本実施形態は、目的関数を最大化する場合（つまり、最大化問題）についても同様に適用することができる。
【００１８】
＜最適化システム１の全体構成＞
まず、本実施形態に係る最適化システム１の全体構成について、図１を参照しながら説明する。図１は、本実施形態に係る最適化システム１の全体構成の一例を示す図である。
【００１９】
図１に示すように、本実施形態に係る最適化システム１には、最適化装置１０と、端末２０と、計算機３０とが含まれる。また、最適化装置１０と、端末２０と、計算機３０とは、例えば、任意の通信ネットワークＮを介して通信可能に接続されている。
【００２０】
最適化装置１０は、決定変数（の一部）がバイナリ変数でない混合整数計画問題が与えられると、これらの決定変数をバイナリ変数の組み合わせに変換することで、当該混合整数計画問題を組み合わせ最適化問題に変換する。そして、最適化装置１０は、後述する計算機３０により組み合わせ最適化問題を解く。これにより、最適化装置１０は、決定変数がバイナリ変数でない混合整数計画問題を高速に解くことができる。なお、最適化結果は、例えば、後述する端末２０に出力される。
【００２１】
端末２０は、例えばユーザ等が利用するＰＣ（パーソナルコンピュータ）やスマートフォン等の端末装置である。端末２０は、例えば、最適化装置１０から最適化結果が出力されると、この最適化結果を表示する。
【００２２】
計算機３０は、量子コンピュータ等の量子コンピューティング装置である。なお、計算機３０は、例えば、組み合わせ最適化問題の計算に特化した計算機、組み合わせ最適化問題の計算を高速に実行可能な計算機等であってもよい。
【００２３】
なお、図１に示す最適化システム１の構成は一例であって、他の構成であってもよい。例えば、最適化システム１には、複数台の端末２０が含まれていてもよいし、又は端末２０が含まれていなくてもよい。また、例えば、計算機３０が最適化装置１０と一体となっていてもよい（つまり、最適化装置１０が量子コンピュータ等の量子コンピューティング装置であってもよい。）。
【００２４】
＜最適化装置１０のハードウェア構成＞
次に、本実施形態に係る最適化装置１０のハードウェア構成について、図２を参照しながら説明する。図２は、本実施形態に係る最適化装置１０のハードウェア構成の一例を示す図である。
【００２５】
図２に示すように、本実施形態に係る最適化装置１０は、入力装置１１と、表示装置１２と、外部Ｉ／Ｆ１３と、通信Ｉ／Ｆ１４と、ＲＯＭ（Read Only Memory）１５と、ＲＡＭ（Random Access Memory）１６と、ＣＰＵ（Central Processing Unit）１７と、補助記憶装置１８とを有する。これら各ハードウェアは、バス１９により相互に通信可能に接続されている。
【００２６】
入力装置１１は、例えば各種ボタンやタッチパネル、キーボード、マウス等であり、最適化装置１０に各種の操作を入力するのに用いられる。表示装置１２は、例えばディスプレイ等であり、最適化装置１０による各種の処理結果を表示する。なお、最適化装置１０は、入力装置１１及び表示装置１２の少なくとも一方を有していなくてもよい。
【００２７】
外部Ｉ／Ｆ１３は、外部装置とのインタフェースである。外部装置には、記録媒体１３ａ等がある。最適化装置１０は、外部Ｉ／Ｆ１３を介して、記録媒体１３ａの読み取りや書き込み等を行うことができる。記録媒体１３ａには、例えば、ＳＤメモリカード(SD memory card）やＵＳＢメモリ、ＣＤ（Compact Disk）、ＤＶＤ（Digital Versatile Disk）等がある。
【００２８】
通信Ｉ／Ｆ１４は、最適化装置１０が他の装置（例えば、端末２０や計算機３０等）とデータ通信を行うためのインタフェースである。
【００２９】
ＲＯＭ１５は、電源を切ってもデータを保持することができる不揮発性の半導体メモリである。ＲＡＭ１６は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＣＰＵ１７は、例えば補助記憶装置１８やＲＯＭ１５からプログラムやデータをＲＡＭ１６上に読み出して、各種処理を実行する演算装置である。
【００３０】
補助記憶装置１８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性のメモリである。補助記憶装置１８に格納されているプログラムやデータには、例えば、基本ソフトウェアであるＯＳ（Operating System）、ＯＳ上で動作する各種アプリケーションプログラム、本実施形態を実現するプログラム等がある。
【００３１】
本実施形態に係る最適化装置１０は、図２に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。なお、図２では、最適化装置１０が１台のコンピュータで実現される場合のハードウェア構成例を示したが、これに限られない。最適化装置１０は、例えば、複数台のコンピュータで実現されていてもよい。
【００３２】
＜最適化装置１０の機能構成＞
次に、本実施形態に係る最適化装置１０の機能構成について、図３を参照しながら説明する。図３は、本実施形態に係る最適化装置１０の機能構成の一例を示す図である。
【００３３】
図３に示すように、本実施形態に係る最適化装置１０は、入力部１０１と、バイナリ変換部１０２と、組み合わせ最適化計算部１０３と、連続変換部１０４と、出力部１０５とを有する。これら各部は、例えば、最適化装置１０にインストールされた１以上のプログラムが、ＣＰＵ１７に実行させる処理により実現される。
【００３４】
入力部１０１は、少なくとも一部の決定変数がバイナリ変数でない混合整数計画問題を入力する。なお、入力部１０１は、このような混合整数計画問題を補助記憶装置１８等から読み込むことで入力してもよいし、通信Ｉ／Ｆ１４を介して接続される他の装置から受信することで入力してもよい。
【００３５】
バイナリ変換部１０２は、入力部１０１が入力した混合整数計画問題の決定変数のうち、バイナリ変数でない決定変数（つまり、連続値である決定変数）をバイナリ変数の組み合わせに変換する。すなわち、バイナリ変換部１０２は、上記の数１に示す混合整数計画問題の決定変数xkを、或る関数fkを用いてxk=fk(sk), k=1,2,・・・,Nxとなるように、Nk個のバイナリ変数を要素とするベクトルskに変換する。言い換えれば、バイナリ変換部１０２は、各決定変数xkが、或る関数fkと、Nk個のバイナリ変数を要素とするベクトルskとを用いて表現できるように、fk及びskを決定する。これにより、混合整数計画問題が、決定変数がバイナリ変数の組み合わせ最適化問題に変換される。
【００３６】
ここで、上記の数１に示す混合整数計画問題の決定変数xkを、バイナリ変数を要素とするベクトルskに変換することで、この混合整数計画問題は、以下の組み合わせ最適化問題に変換される。
【００３７】
【数３】
2020113190.tif 000005
ここで、E´(S,y)は目的関数、g´(S,y)≦0及びh´(S,y)=0は制約条件、Sはバイナリ変数（を要素とするベクトル）skを要素とする配列（又はテンソル）、skはバイナリ変数skmを要素とするベクトル、Nkはskの次元数（要素数）である。
【００３８】
組み合わせ最適化計算部１０３は、上記の数２に示す組み合わせ最適化問題の計算を計算機３０に要求する。これにより、例えば量子コンピュータ等の量子コンピューティング装置又は組み合わせ最適化問題の計算に特化した計算機である計算機３０によって当該組み合わせ最適化問題が高速に計算される。そして、組み合わせ最適化計算部１０３は、この計算結果（組み合わせ最適化結果）を計算機３０から受信する。以降では、組み合わせ最適化をSopt及びyoptと表す。すなわち、組み合わせ最適化結果は、
【００３９】
【数４】
2020113190.tif 000006
と表される。
【００４０】
連続変換部１０４は、組み合わせ最適化結果Soptから、混合整数計画問題の決定変数xkの最適値を計算する。これは、
【００４１】
【数５】
2020113190.tif 000007
により計算することができる。これにより、上記の数１に示す混合整数計画問題の最適化結果xopt及びyoptが得られる。
【００４２】
出力部１０５は、最適化結果を端末２０に出力する。これにより、端末２０には、最適化結果が表示される。なお、出力部１０５は、最適化結果を表示装置１２に出力して表示させてもよいし、補助記憶装置１８に出力して保存してもよい。また、出力部１０５は、最適化結果を出力する際に、任意の処理（例えば、端末２０や表示装置１２にグラフ形式で表示されるようにする処理や表形式で表示されるようにする処理、又は暗号化や圧縮して補助記憶装置１８に保存されるようにする処理等）を施してもよい。
【００４３】
＜最適化処理＞
次に、決定変数がバイナリ変数でない混合整数計画問題が最適化装置１０に与えられた場合に、量子コンピュータ等である計算機３０を使用して、この混合整数計画問題を高速に解く処理（最適化処理）について、図４を参照しながら説明する。図４は、本実施形態に係る最適化処理の一例を示すフローチャートである。
【００４４】
ステップＳ１０１：入力部１０１は、少なくとも一部の決定変数がバイナリ変数でない混合整数計画問題を入力する。
【００４５】
ステップＳ１０２：バイナリ変換部１０２は、上記のステップＳ１０１で入力された混合整数計画問題の決定変数のうち、バイナリ変数でない決定変数xkをバイナリ変数の組み合わせに変換する。これにより、混合整数計画問題が、決定変数がバイナリ変数の組み合わせ最適化問題に変換される。
【００４６】
ここで、バイナリ変換部１０２は、例えば、以下の変換方法１〜４のいずれかの方法によりxkを、バイナリ変数を要素とするベクトルskに変換する。
【００４７】
（変換方法１）
決定変数xkが、xklow≦xk≦xkhighの範囲の値を取る場合（つまり、xkの定義域がxklow≦xk≦xkhighである場合）、xklow≦wkm≦xkhighとなる変換パラメータwkm, m=1,2,・・・,Nkを導入し、xk=fk(sk)を
【００４８】
【数６】
2020113190.tif 000008
として、このfkによりxkをskに変換する（つまり、変換パラメータwkmを重みとして、Nk個のバイナリ変数の重み付け和を用いてxkを表現する。）。なお、上述したように、skはskm∈{0,1}, m=1,2,・・・,Nkを要素とするベクトルである。また、Nkはxkの変換に使用するバイナリ変数の数（つまり、離散化粒度）を表すパラメータである。
【００４９】
ここで、変換パラメータwkmは、
【００５０】
【数７】
2020113190.tif 000009
とする（つまり、xkの定義域を均等に分割するようなwkmを用いる。）。また、組み合わせ最適化問題の制約条件として、
【００５１】
【数８】
2020113190.tif 000010
を追加する。
【００５２】
（変換方法２）
決定変数xkが、xklow≦xk≦xkhighの範囲の値を取る場合、上記の変換方法１と同様に、上記の数６により、xkをskに変換する。
【００５３】
ただし、変換方法２では、変換パラメータwkmを
【００５４】
【数９】
2020113190.tif 000011
とする。なお、変換方法２では制約条件の追加は不要である。
【００５５】
（変換方法３）
決定変数xkが、yk×xklow≦xk≦yk×xkhighの範囲の値を取る場合（つまり、例えば、ykが設備の稼働状態を表し、稼働停止（yk=0）及び稼働中（yk=1）を考慮する場合）、xklow≦wkm≦xkhighとなる変換パラメータwkm, m=1,2,・・・,Nkを導入し、xk=fk(sk)を
【００５６】
【数１０】
2020113190.tif 000012
として、このfkによりxkをskに変換する。
【００５７】
ここで、変換パラメータwkmは、
【００５８】
【数１１】
2020113190.tif 000013
とする（つまり、xkの定義域を均等に分割するようなwkmを用いる。）。また、組み合わせ最適化問題の制約条件として、
【００５９】
【数１２】
2020113190.tif 000014
を追加する。
【００６０】
（変換方法４）
決定変数xkが、yk×xklow≦xk≦yk×xkhighの範囲の値を取る場合、上記の変換方法３と同様に、上記の数１０により、xkをskに変換する。
【００６１】
ただし、変換方法４では、変換パラメータwkmを
【００６２】
【数１３】
2020113190.tif 000015
とする。なお、変換方法４では制約条件の追加は不要である。
【００６３】
なお、本実施形態では、上記の数１に示す混合整数計画問題が与えられるものとしたが、混合整数計画問題は、より一般的には、以下のように表すことができる。
【００６４】
【数１４】
2020113190.tif 000016
ここで、zk´は整数値を取る決定変数である。例えば、或る需給系統の最適化問題を考える場合、zk´は設備の離散的な出力値が挙げられる。
【００６５】
このような場合には、zk´もバイナリ変数の組み合わせに変換する必要がある。バイナリ変換部１０２は、例えば、以下の変換方法５又は６の方法によりzk´を、バイナリ変数sk´m（m=1,2,・・・,Nk´）を要素とするベクトルsk´に変換すればよい。
【００６６】
（変換方法５）
決定変数zk´が、zk´low≦zk´≦zk´highの範囲の値を取る場合、zk´=fk´(sk´)を
【００６７】
【数１５】
2020113190.tif 000017
として、このfk´によりzk´をsk´に変換する。
【００６８】
ここで、Nk´は
【００６９】
【数１６】
2020113190.tif 000018
となるように選択する。
【００７０】
（変換方法６）
決定変数zk´が、yk´×zk´low≦zk´≦yk´×zk´highの範囲の値を取る場合、zk´=fk´(sk´)を
【００７１】
【数１７】
2020113190.tif 000019
として、このfk´によりzk´をsk´に変換する。
【００７２】
なお、Nk´の選択方法については変換方法５と同様である。
【００７３】
（変換方法７）
決定変数zk´が、zk´low≦zk´≦zk´highの範囲の値を取る場合、zk´=fk´(sk´)を
【００７４】
【数１８】
2020113190.tif 000020
とする（つまり、xkの定義域を均等に分割するように変換をする。）。また、組み合わせ最適化問題の制約条件として、
【００７５】
【数１９】
2020113190.tif 000021
を追加する。
【００７６】
（変換方法８）
決定変数zk´が、yk´×zk´low≦zk´≦yk´×zk´highの範囲の値を取る場合、zk´=fk´(sk´)を
【００７７】
【数２０】
2020113190.tif 000022
として、このfk´によりzk´をsk´に変換する。
【００７８】
なお、追加する制約条件は変換方法７と同様である。
【００７９】
ステップＳ１０３：組み合わせ最適化計算部１０３は、上記のステップＳ１０２の変換により得られた組み合わせ最適化問題の計算を計算機３０に要求する。例えば、計算機３０の計算資源がクラウドサービス等として利用可能である場合には、組み合わせ最適化計算部１０３は、ＷｅｂＡＰＩ等を利用して、組み合わせ最適化問題の計算を計算機３０に要求することができる。
【００８０】
これにより、例えば量子コンピュータ等の量子コンピューティング装置又は組み合わせ最適化問題の計算に特化した計算機である計算機３０によって当該組み合わせ最適化問題が高速に計算される。なお、量子コンピュータ等の量子コンピューティング装置を使用して組み合わせ最適化問題を計算する方法の詳細については、例えば、非特許文献３乃至５を参照されたい。
【００８１】
そして、組み合わせ最適化計算部１０３は、計算機３０による組み合わせ最適化結果Sopt及びyoptを計算機３０から受信する。
【００８２】
ステップＳ１０４：連続変換部１０４は、組み合わせ最適化結果Soptから、混合整数計画問題の決定変数xkの最適値を計算する。これは、上述したように、
【００８３】
【数２１】
2020113190.tif 000023
により計算することができる。これにより、上記の数１に示す混合整数計画問題の最適化結果xopt及びyoptが得られる。
【００８４】
ステップＳ１０５：出力部１０５は、最適化結果xopt及びyoptを端末２０に出力する。なお、上述したように、最適化結果xopt及びyoptは、表示装置１２や補助記憶装置１８に出力されてもよいし、任意の処理が施された後に出力されてもよい。
【００８５】
以上のように、本実施形態に係る最適化装置１０は、混合整数計画問題の決定変数のうちのバイナリ変数でない決定変数を、複数のバイナリ変数の組み合わせにより表現することで、当該混合整数計画問題を組み合わせ最適化問題に変換する。そして、本実施形態に係る最適化装置１０は、この組み合わせ最適化問題を、量子コンピュータ等の量子コンピューティング装置や組み合わせ最適化問題の計算に特化した計算機である計算機３０に計算させる。これにより、本実施形態に係る最適化システム１では、決定変数の一部がバイナリ変数でない混合整数計画問題が与えられた場合に、この混合整数計画問題を高速に解くことが可能となる。したがって、本実施形態に係る最適化システム１によれば、例えば、最適化対象が大規模な場合や複雑である場合等であっても、少ない計算時間で最適解を得ることができるようになる。
【００８６】
＜実施例１＞
以降では、実施例１として、本実施形態に係る最適化システム１により混合整数計画問題を解くことで、エネルギープラントの最適運転計画を得る場合について説明する。本実施例では、図５に示す系統モデルを最適化対象とする。図５は、実施例１における系統モデルを示す図である。
【００８７】
図５に示す系統モデルには、１台のガスタービン、１台のボイラ、２台のターボ冷凍機、２台の蒸気吸収式冷凍機、及び１台の蓄熱槽の７台の機器が含まれる。この系統モデルではガスタービン、ボイラ、ターボ冷凍機及び蒸気吸収式冷凍機がエネルギー（電気、蒸気及び熱（冷熱））を供給している。このとき、本実施例では、各エネルギーの需給バランスと各機器の制約とを考慮した上で、コスト（電力購入コスト及びガス購入コスト）が最小となるように、各機器が稼働させるか否か及びどれだけエネルギーを生産及び供給するかを計画する。
【００８８】
図５に示す系統モデルでは、負荷として、電力負荷、熱負荷（冷水）及び蒸気負荷の３種類がある。また、各機器は、一度稼働（又は停止）したら一定期間稼働（又は停止）させ続ける必要があるものとする。
【００８９】
このとき、電力購入コストとガス購入コストとの和
【００９０】
【数２２】
2020113190.tif 000024
を目的関数とする。ここで、
【００９１】
【数２３】
2020113190.tif 000025
とする。また、
【００９２】
【数２４】
2020113190.tif 000026
とする。Ntはターボ冷凍機の台数であり、本実施例ではNt=2である。なお、ガス購入単価は一定でCFri=59.8[\/Nm3]、Iは最適化で考慮する時間断面の最大値でI=24であるものとする。電力購入単価は以下の表１であるものとする。
【００９３】
【表１】
2020113190.tif 000027
また、購入電力Eriは以下により表されるものとする。
【００９４】
【数２５】
2020113190.tif 000028
ここで、ftj(xtji)はj番目のターボ冷凍機の消費電力であり、
【００９５】
【数２６】
2020113190.tif 000029
と表されるものとする。また、fge(xgi)はガスタービンの発電量であり、
【００９６】
【数２７】
2020113190.tif 000030
と表されるものとする。ELiは時刻iにおける電力負荷であり、以下の表２であるものとする。
【００９７】
【表２】
2020113190.tif 000031
なお、購入電力が0以上となるように、
【００９８】
【数２８】
2020113190.tif 000032
であるものとする。
【００９９】
このとき、ターボ冷凍機及び蒸気吸収式冷凍機の熱出力[MJ/h]と、ボイラ及びガスタービンのガス消費量[Nm3/h]とを全時間断面分（i=1,2,・・・,24）まとめた変数（連続変数）を決定変数Xとする。すなわち、Nsを蒸気吸収式冷凍機の台数（つまり、本実施例ではNs=2）として
【０１００】
【数２９】
2020113190.tif 000033
とすれば、決定変数Xは、
【０１０１】
【数３０】
2020113190.tif 000034
である。
【０１０２】
また、ターボ冷凍機、蒸気吸収式冷凍機、ボイラ、及びガスタービンの稼働中を1、稼働停止を0として、全時間断面分（i=1,2,・・・,24）まとめた変数（バイナリ変数）を決定変数Yとする。すなわち、
【０１０３】
【数３１】
2020113190.tif 000035
とすれば、決定変数Yは、
【０１０４】
【数３２】
2020113190.tif 000036
である。
【０１０５】
上記の数２２に示す目的関数を最適化する際には、各機器の上下限制約と、蒸気に関する制約条件と、供給する熱量（冷熱）と消費する熱量（冷熱）とのバランスに関する制約条件と、連続稼働・停止時間に関する制約条件とを満たす必要がある。
【０１０６】
各機器の上下限制約は、以下であるものとする。
【０１０７】
【数３３】
2020113190.tif 000037
ここで、
【０１０８】
【数３４】
2020113190.tif 000038
であり、本実施例では、
【０１０９】
【数３５】
2020113190.tif 000039
であるものとする。また、fbはボイラにおける消費ガス量と蒸気生成量と関係式であり、
【０１１０】
【数３６】
2020113190.tif 000040
であるものとする。なお、abはボイラにおける消費ガス量と蒸気生成量との特性係数ある。
【０１１１】
蒸気に関する制約条件は、以下であるものとする。
【０１１２】
【数３７】
2020113190.tif 000041
ここで、fgsはガスタービンにおける消費ガス量と蒸気生成量との関係式であり、
【０１１３】
【数３８】
2020113190.tif 000042
であるものとする。なお、agsはガスタービンにおける消費ガス量と蒸気生成量との特性係数である。
【０１１４】
また、fsjはj番目の蒸気吸収式冷凍機における熱出力と消費蒸気量との関係式であり、
【０１１５】
【数３９】
2020113190.tif 000043
であるものとする。なお、asj及びbsjはj番目の蒸気吸収式冷凍機における熱出力と消費蒸気量との特性係数である。
【０１１６】
供給する熱量（冷熱）と消費する熱量（冷熱）とのバランスに関する制約条件（すなわち、蓄熱槽に入力される冷熱量と出力される冷熱量とがバランスしていることを表す制約条件）は、以下であるものとする。
【０１１７】
【数４０】
2020113190.tif 000044
ここで、
【０１１８】
【数４１】
2020113190.tif 000045
である。本実施例では、
【０１１９】
【数４２】
2020113190.tif 000046
であるものとする。上記の数４０に示す制約条件は、最終時間断面以外のi=1,・・・,I-1と、最終時間断面のi=Iとでそれぞれ以下の上下限制約がある。
【０１２０】
【数４３】
2020113190.tif 000047
ここで、
【０１２１】
【数４４】
2020113190.tif 000048
である。本実施例では、
【０１２２】
【数４５】
2020113190.tif 000049
であるものとする。なお、最終時間断面のi=Iにおける上下限制約は、最終時間断面i=Iで冷熱を使い切らないようにするための制約である。
【０１２３】
連続稼働・停止時間に関する制約条件は、以下であるものとする。
【０１２４】
【数４６】
2020113190.tif 000050
ここで、Ltjはj番目のターボ冷凍機の連続稼働時間・連続停止時間、Lsjはj番目の蒸気吸収式冷凍機の連続稼働時間・連続停止時間、Lgはガスタービンの連続稼働時間・連続停止時間、Lbはボイラの連続稼働時間・連続停止時間である。本実施例では、Lt1=2, Lt2=2, Ls1=2, Ls2=2, Lg=2, Lb=2であるものとする。
【０１２５】
以上で定式化した混合整数計画問題が最適化装置１０に与えられると、入力部１０１が当該混合整数計画問題を入力し（図４のステップＳ１０１）、バイナリ変換部１０２が決定変数Xをバイナリ変数（の組み合わせ）に変換する（図４のステップＳ１０２）。ここで、本実施例では、離散化粒度Nk=5として、変換方法３により変換するものとする。この場合、バイナリ変換部１０２は、j番目のターボ冷凍機の変換パラメータwtjm、j番目の蒸気吸収式冷凍機の変換パラメータwsjm、ガスタービンの変換パラメータwgm、及びボイラの変換パラメータwbmをそれぞれ以下により計算することができる。
【０１２６】
【数４７】
2020113190.tif 000051
この計算結果をまとめると以下の表３になる。
【０１２７】
【表３】
2020113190.tif 000052
なお、本実施例では離散化粒度Nkは全ての変数（つまり、決定変数Xの全ての要素）で固定の共通の値としているが、これに限られず、例えば、変数によってNkの値を変えてもよい。また、変換パラメータは重みとして使用できるビット数に応じて、例えば、四捨五入等の処理によって簡略化してもよい。
【０１２８】
バイナリ変換部１０２は、上記で計算した変換パラメータを用いて、以下により各決定変数（Xの各要素である変数）をバイナリ変数の組み合わせに変換する。
【０１２９】
【数４８】
2020113190.tif 000053
ここで、
【０１３０】
【数４９】
2020113190.tif 000054
がバイナリ変数である。
【０１３１】
また、バイナリ変換部１０２は、組み合わせ最適化問題の制約条件として、以下を追加する。なお、これらの制約条件は、各機器が能力を超えた性能を発揮できないことを表す。
【０１３２】
【数５０】
2020113190.tif 000055
これにより、混合整数計画問題が、決定変数がバイナリ変数の組み合わせ最適化問題に変換される。
【０１３３】
そして、組み合わせ最適化計算部１０３が当該組み合わせ最適化問題を計算機３０に計算させて（図４のステップＳ１０３）、この計算結果（組み合わせ最適化結果）から連続変換部１０４が混合整数計画問題の決定変数の最適値を計算し（図４のステップＳ１０４）、出力部１０５が当該最適値（最適化結果）を出力する（ステップＳ１０５）。
【０１３４】
ここで、本実施例における最適化結果を図６に示す。図６は、実施例１における最適化結果を示す図である。なお、図６におけるトータルコストは、ガス購入コストと電力購入コストとの和である。
【０１３５】
図６に示すように、i=1〜24までのトータルコストの和は、4085527[\]である。一方で、従来技術を用いて、決定変数が連続変数のまま最適化を行った場合、そのコストは4043150[\]であった。したがって、本実施形態に係る最適化装置１０によれば、連続変数のまま最適化を行った場合と近い最適値が高速に得られることがわかる。
【０１３６】
なお、例えば、量子化粒度Nk=100として、本実施形態に係る最適化装置１０により最適化を行った場合は、4045713[\]であった。したがって、量子化粒度Nkの値を大きくし、バイナリ変数の数を増加させると、より高い精度で最適値が得られることがわかる。
【０１３７】
なお、本実施例では、或る時刻t´において、決定変数X、Yの最適値を計算する場合について説明したが、例えば、時刻t´毎に、決定変数X、Yの最適値を繰り返し計算してもよい。すなわち、或る時間区間（例えば、制御周期等）を表すインデックスをt´、時刻t´における決定変数をXt´、Y t´として、時刻t´毎に、決定変数をXt´、Y t´の最適値を計算してもよい。
【０１３８】
＜実施例２＞
以降では、実施例２として、実施例１と同じ系統モデルを用いて、図４のステップＳ１０２で離散化粒度Nk=5、変換方法４により変換する場合について説明する。この場合、バイナリ変換部１０２は、j番目のターボ冷凍機の変換パラメータwtjm、j番目の蒸気吸収式冷凍機の変換パラメータwsjm、ガスタービンの変換パラメータwgm、及びボイラの変換パラメータwbmをそれぞれ以下により計算する。
【０１３９】
なお、本実施例においても、実施例１と同様に時刻t´毎に繰り返し、最適化計算を行ってもよい。
【０１４０】
【数５１】
2020113190.tif 000056
この計算結果をまとめると以下の表４になる。
【０１４１】
【表４】
2020113190.tif 000057
なお、実施例１と異なり、実施例２では制約条件の追加は不要である。
【０１４２】
このとき、図４のステップＳ１０３〜ステップＳ１０５を行った後の本実施例の最適化結果を図７に示す。図７は、実施例２における最適化結果を示す図である。
【０１４３】
図７に示すように、i=1〜24までのトータルコストの和は、4047190[\]である。このように、変換方法４を用いることで、変換方法３を用いた場合と比較して、より高い精度で最適値が得られることがわかる。
【０１４４】
なお、上述したように、本実施形態では、計算機３０が最適化装置１０と一体となっていてもよい。この場合、例えば、組み合わせ最適化計算部１０３のみが量子コンピュータ等で実現されており、他の機能部（入力部１０１、バイナリ変換部１０２、連続変換部１０４、及び出力部１０５）はＣＰＵ１７で実現されていてもよいし、全ての機能部（入力部１０１、バイナリ変換部１０２、組み合わせ最適化計算部１０３、連続変換部１０４、及び出力部１０５）が量子コンピュータ等で実現されていてもよい。又は、例えば、組み合わせ最適化計算部１０３を含む一部の機能部のみが量子コンピュータ等で実現されていており、他の機能部はＣＰＵ１７で実現されていてもよい。
【０１４５】
本発明は、具体的に開示された上記の各実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１４６】
１        最適化システム
１０      最適化装置
２０      端末
３０      計算機
１０１    入力部
１０２    バイナリ変換部
１０３    組み合わせ最適化計算部
１０４    連続変換部
１０５    出力部
【図１】
2020113190.tif 000058
【図２】
2020113190.tif 000059
【図３】
2020113190.tif 000060
【図４】
2020113190.tif 000061
【図５】
2020113190.tif 000062
【図６】
2020113190.tif 000063
【図７】
2020113190.tif 000064