JP7243203B2

JP7243203B2 - 最適化装置、最適化システム、最適化方法、及びプログラム

Info

Publication number: JP7243203B2
Application number: JP2019005310A
Authority: JP
Inventors: 智志桐生; 拓也渡辺; 哲郎松井
Original assignee: Fuji Electric Co Ltd
Current assignee: Fuji Electric Co Ltd
Priority date: 2019-01-16
Filing date: 2019-01-16
Publication date: 2023-03-22
Anticipated expiration: 2039-01-16
Also published as: JP2020113190A

Description

本発明は、最適化装置、最適化システム、最適化方法、及びプログラムに関する。

複数の生産者が生産する資源（例えば、電力、ガス、蒸気等）を複数の需要家に配分する場合にコストが最適となるように決定するシステムや、生産ラインで生産される製品についての供給量を配分する場合に目的関数を設定して最適化問題を解くことで最適な供給量の配分を決定するシステムが一般的に知られている（例えば、非特許文献１及び２）。これらの最適化システムでは、最適化問題を解く際に、分枝限定法やメタヒューリスティックス等のアルゴリズム、又はこれらのアルゴリズムに基づいた最適化ソルバを使用して、最適解を計算している。

一方で、量子ゲートマシンやイジングマシン（量子アニーリングマシン、コヒーレントイジングマシン、量子ニューラルネットワークマシン、デジタル回路によるイジングマシン等）といった、量子コンピューティングを実現する装置（以降、「量子コンピューティング装置」という。）を使用して、組み合わせ最適化問題を解く方法が知られている（例えば、非特許文献３乃至８）。また、ＤＮＮ（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.

ここで、一般に、最適化システムでは、システムの要求仕様を満たすように、最適化問題を所定の時間内に解く必要がある。しかしながら、例えば、最適化問題が大規模かつ複雑になると計算時間が増大してしまい、要求仕様を満たせなくなってしまう場合があった。

これに対して、量子コンピューティング装置により最適化問題を解くことができれば計算時間を大幅に削減することができるが、最適化問題の決定変数が連続値又は整数値である場合（つまり、決定変数がバイナリ変数でない場合）には、量子コンピューティング装置により最適化問題を解くことができなかった。

本発明は、上記の点に鑑みてなされたもので、決定変数がバイナリ変数でない最適化問題を高速に解くことを目的とする。

上記目的を達成するため、本発明の実施の形態における最適化装置は、混合整数計画問題が入力されると、前記混合整数計画問題の決定変数のうち、連続値又は整数値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手段と、前記組み合わせ最適化問題の最適解を量子コンピューティング装置に計算させる計算手段と、前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手段と、を有することを特徴とする。

決定変数がバイナリ変数でない最適化問題を高速に解くことができる。

本実施形態に係る最適化システムの全体構成の一例を示す図である。本実施形態に係る最適化装置のハードウェア構成の一例を示す図である。本実施形態に係る最適化装置の機能構成の一例を示す図である。本実施形態に係る最適化処理の一例を示すフローチャートである。実施例１における系統モデルを示す図である。実施例１における最適化結果を示す図である。実施例２における最適化結果を示す図である。

以下、本発明の実施の形態（以降、「本実施形態」とも表す。）について説明する。本実施形態では、決定変数（の一部）がバイナリ変数でない混合整数計画問題が与えられた場合に、量子コンピュータ等を使用して、この混合整数計画問題を高速に解くことが可能な最適化システム１について説明する。なお、混合整数計画問題とは、整数値を取る変数と実数値を取る変数とが混在している最適化問題のことである。

ここで、本実施形態では、特に言及した場合を除き、混合整数計画問題は、以下で表されるものとする。

ここで、E(x,y)は目的関数、g(x,y)≦0及びh(x,y)=0は制約条件、xは実数値を取る決定変数x_kを要素とするベクトル、yは0又は1のいずれかを取る決定変数

を要素とするベクトル、N_xはxの次元数（要素数）、N_yはyの次元数（要素数）である。例えば、或る需給系統の最適化問題を考える場合、Eはコスト、x_kは設備が生産する資源の供給量、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）、ＯＳ上で動作する各種アプリケーションプログラム、本実施形態を実現するプログラム等がある。

本実施形態に係る最適化装置１０は、図２に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。なお、図２では、最適化装置１０が１台のコンピュータで実現される場合のハードウェア構成例を示したが、これに限られない。最適化装置１０は、例えば、複数台のコンピュータで実現されていてもよい。

＜最適化装置１０の機能構成＞
次に、本実施形態に係る最適化装置１０の機能構成について、図３を参照しながら説明する。図３は、本実施形態に係る最適化装置１０の機能構成の一例を示す図である。

図３に示すように、本実施形態に係る最適化装置１０は、入力部１０１と、バイナリ変換部１０２と、組み合わせ最適化計算部１０３と、連続変換部１０４と、出力部１０５とを有する。これら各部は、例えば、最適化装置１０にインストールされた１以上のプログラムが、ＣＰＵ１７に実行させる処理により実現される。

入力部１０１は、少なくとも一部の決定変数がバイナリ変数でない混合整数計画問題を入力する。なお、入力部１０１は、このような混合整数計画問題を補助記憶装置１８等から読み込むことで入力してもよいし、通信Ｉ／Ｆ１４を介して接続される他の装置から受信することで入力してもよい。

バイナリ変換部１０２は、入力部１０１が入力した混合整数計画問題の決定変数のうち、バイナリ変数でない決定変数（つまり、連続値である決定変数）をバイナリ変数の組み合わせに変換する。すなわち、バイナリ変換部１０２は、上記の数１に示す混合整数計画問題の決定変数x_kを、或る関数f_kを用いてx_k=f_k(s_k), k=1,2,・・・,N_xとなるように、N_k個のバイナリ変数を要素とするベクトルs_kに変換する。言い換えれば、バイナリ変換部１０２は、各決定変数x_kが、或る関数f_kと、N_k個のバイナリ変数を要素とするベクトルs_kとを用いて表現できるように、f_k及びs_kを決定する。これにより、混合整数計画問題が、決定変数がバイナリ変数の組み合わせ最適化問題に変換される。

ここで、上記の数１に示す混合整数計画問題の決定変数x_kを、バイナリ変数を要素とするベクトルs_kに変換することで、この混合整数計画問題は、以下の組み合わせ最適化問題に変換される。

ここで、E´(S,y)は目的関数、g´(S,y)≦0及びh´(S,y)=0は制約条件、Sはバイナリ変数（を要素とするベクトル）s_kを要素とする配列（又はテンソル）、s_kはバイナリ変数s_kmを要素とするベクトル、N_kはs_kの次元数（要素数）である。

組み合わせ最適化計算部１０３は、上記の数２に示す組み合わせ最適化問題の計算を計算機３０に要求する。これにより、例えば量子コンピュータ等の量子コンピューティング装置又は組み合わせ最適化問題の計算に特化した計算機である計算機３０によって当該組み合わせ最適化問題が高速に計算される。そして、組み合わせ最適化計算部１０３は、この計算結果（組み合わせ最適化結果）を計算機３０から受信する。以降では、組み合わせ最適化をS^opt及びy^optと表す。すなわち、組み合わせ最適化結果は、

と表される。

連続変換部１０４は、組み合わせ最適化結果S^optから、混合整数計画問題の決定変数x_kの最適値を計算する。これは、

により計算することができる。これにより、上記の数１に示す混合整数計画問題の最適化結果x^opt及びy^optが得られる。

出力部１０５は、最適化結果を端末２０に出力する。これにより、端末２０には、最適化結果が表示される。なお、出力部１０５は、最適化結果を表示装置１２に出力して表示させてもよいし、補助記憶装置１８に出力して保存してもよい。また、出力部１０５は、最適化結果を出力する際に、任意の処理（例えば、端末２０や表示装置１２にグラフ形式で表示されるようにする処理や表形式で表示されるようにする処理、又は暗号化や圧縮して補助記憶装置１８に保存されるようにする処理等）を施してもよい。

＜最適化処理＞
次に、決定変数がバイナリ変数でない混合整数計画問題が最適化装置１０に与えられた場合に、量子コンピュータ等である計算機３０を使用して、この混合整数計画問題を高速に解く処理（最適化処理）について、図４を参照しながら説明する。図４は、本実施形態に係る最適化処理の一例を示すフローチャートである。

ステップＳ１０１：入力部１０１は、少なくとも一部の決定変数がバイナリ変数でない混合整数計画問題を入力する。

ステップＳ１０２：バイナリ変換部１０２は、上記のステップＳ１０１で入力された混合整数計画問題の決定変数のうち、バイナリ変数でない決定変数x_kをバイナリ変数の組み合わせに変換する。これにより、混合整数計画問題が、決定変数がバイナリ変数の組み合わせ最適化問題に変換される。

ここで、バイナリ変換部１０２は、例えば、以下の変換方法１～４のいずれかの方法によりx_kを、バイナリ変数を要素とするベクトルs_kに変換する。

（変換方法１）
決定変数x_kが、x_k ^low≦x_k≦x_k ^highの範囲の値を取る場合（つまり、x_kの定義域がx_k ^low≦x_k≦x_k ^highである場合）、x_k ^low≦w_km≦x_k ^highとなる変換パラメータw_km, m=1,2,・・・,N_kを導入し、x_k=f_k(s_k)を

として、このf_kによりx_kをs_kに変換する（つまり、変換パラメータw_kmを重みとして、N_k個のバイナリ変数の重み付け和を用いてx_kを表現する。）。なお、上述したように、s_kはs_km∈{0,1}, m=1,2,・・・,N_kを要素とするベクトルである。また、N_kはx_kの変換に使用するバイナリ変数の数（つまり、離散化粒度）を表すパラメータである。

ここで、変換パラメータw_kmは、

とする（つまり、x_kの定義域を均等に分割するようなw_kmを用いる。）。また、組み合わせ最適化問題の制約条件として、

を追加する。

（変換方法２）
決定変数x_kが、x_k ^low≦x_k≦x_k ^highの範囲の値を取る場合、上記の変換方法１と同様に、上記の数６により、x_kをs_kに変換する。

ただし、変換方法２では、変換パラメータw_kmを

とする。なお、変換方法２では制約条件の追加は不要である。

（変換方法３）
決定変数x_kが、y_k×x_k ^low≦x_k≦y_k×x_k ^highの範囲の値を取る場合（つまり、例えば、y_kが設備の稼働状態を表し、稼働停止（y_k=0）及び稼働中（y_k=1）を考慮する場合）、x_k ^low≦w_km≦x_k ^highとなる変換パラメータw_km, m=1,2,・・・,N_kを導入し、x_k=f_k(s_k)を

として、このf_kによりx_kをs_kに変換する。

ここで、変換パラメータw_kmは、

を追加する。

（変換方法４）
決定変数x_kが、y_k×x_k ^low≦x_k≦y_k×x_k ^highの範囲の値を取る場合、上記の変換方法３と同様に、上記の数１０により、x_kをs_kに変換する。

ただし、変換方法４では、変換パラメータw_kmを

とする。なお、変換方法４では制約条件の追加は不要である。

なお、本実施形態では、上記の数１に示す混合整数計画問題が与えられるものとしたが、混合整数計画問題は、より一般的には、以下のように表すことができる。

ここで、z_k´は整数値を取る決定変数である。例えば、或る需給系統の最適化問題を考える場合、z_k´は設備の離散的な出力値が挙げられる。

このような場合には、z_k´もバイナリ変数の組み合わせに変換する必要がある。バイナリ変換部１０２は、例えば、以下の変換方法５又は６の方法によりz_k´を、バイナリ変数s_k´m（m=1,2,・・・,N_k´）を要素とするベクトルs_k´に変換すればよい。

（変換方法５）
決定変数z_k´が、z_k´ ^low≦z_k´≦z_k´ ^highの範囲の値を取る場合、z_k´=f_k´(s_k´)を

として、このf_k´によりz_k´をs_k´に変換する。

ここで、N_k´は

となるように選択する。

（変換方法６）
決定変数z_k´が、y_k´×z_k´ ^low≦z_k´≦y_k´×z_k´ ^highの範囲の値を取る場合、z_k´=f_k´(s_k´)を

として、このf_k´によりz_k´をs_k´に変換する。

なお、N_k´の選択方法については変換方法５と同様である。

（変換方法７）
決定変数z_k´が、z_k´ ^low≦z_k´≦z_k´ ^highの範囲の値を取る場合、z_k´=f_k´(s_k´)を

とする（つまり、x_kの定義域を均等に分割するように変換をする。）。また、組み合わせ最適化問題の制約条件として、

を追加する。

（変換方法８）
決定変数z_k´が、y_k´×z_k´ ^low≦z_k´≦y_k´×z_k´ ^highの範囲の値を取る場合、z_k´=f_k´(s_k´)を

として、このf_k´によりz_k´をs_k´に変換する。

なお、追加する制約条件は変換方法７と同様である。

ステップＳ１０３：組み合わせ最適化計算部１０３は、上記のステップＳ１０２の変換により得られた組み合わせ最適化問題の計算を計算機３０に要求する。例えば、計算機３０の計算資源がクラウドサービス等として利用可能である場合には、組み合わせ最適化計算部１０３は、ＷｅｂＡＰＩ等を利用して、組み合わせ最適化問題の計算を計算機３０に要求することができる。

これにより、例えば量子コンピュータ等の量子コンピューティング装置又は組み合わせ最適化問題の計算に特化した計算機である計算機３０によって当該組み合わせ最適化問題が高速に計算される。なお、量子コンピュータ等の量子コンピューティング装置を使用して組み合わせ最適化問題を計算する方法の詳細については、例えば、非特許文献３乃至５を参照されたい。

そして、組み合わせ最適化計算部１０３は、計算機３０による組み合わせ最適化結果S^opt及びy^optを計算機３０から受信する。

ステップＳ１０４：連続変換部１０４は、組み合わせ最適化結果S^optから、混合整数計画問題の決定変数x_kの最適値を計算する。これは、上述したように、

ステップＳ１０５：出力部１０５は、最適化結果x^opt及びy^optを端末２０に出力する。なお、上述したように、最適化結果x^opt及びy^optは、表示装置１２や補助記憶装置１８に出力されてもよいし、任意の処理が施された後に出力されてもよい。

以上のように、本実施形態に係る最適化装置１０は、混合整数計画問題の決定変数のうちのバイナリ変数でない決定変数を、複数のバイナリ変数の組み合わせにより表現することで、当該混合整数計画問題を組み合わせ最適化問題に変換する。そして、本実施形態に係る最適化装置１０は、この組み合わせ最適化問題を、量子コンピュータ等の量子コンピューティング装置や組み合わせ最適化問題の計算に特化した計算機である計算機３０に計算させる。これにより、本実施形態に係る最適化システム１では、決定変数の一部がバイナリ変数でない混合整数計画問題が与えられた場合に、この混合整数計画問題を高速に解くことが可能となる。したがって、本実施形態に係る最適化システム１によれば、例えば、最適化対象が大規模な場合や複雑である場合等であっても、少ない計算時間で最適解を得ることができるようになる。

＜実施例１＞
以降では、実施例１として、本実施形態に係る最適化システム１により混合整数計画問題を解くことで、エネルギープラントの最適運転計画を得る場合について説明する。本実施例では、図５に示す系統モデルを最適化対象とする。図５は、実施例１における系統モデルを示す図である。

図５に示す系統モデルには、１台のガスタービン、１台のボイラ、２台のターボ冷凍機、２台の蒸気吸収式冷凍機、及び１台の蓄熱槽の７台の機器が含まれる。この系統モデルではガスタービン、ボイラ、ターボ冷凍機及び蒸気吸収式冷凍機がエネルギー（電気、蒸気及び熱（冷熱））を供給している。このとき、本実施例では、各エネルギーの需給バランスと各機器の制約とを考慮した上で、コスト（電力購入コスト及びガス購入コスト）が最小となるように、各機器が稼働させるか否か及びどれだけエネルギーを生産及び供給するかを計画する。

図５に示す系統モデルでは、負荷として、電力負荷、熱負荷（冷水）及び蒸気負荷の３種類がある。また、各機器は、一度稼働（又は停止）したら一定期間稼働（又は停止）させ続ける必要があるものとする。

このとき、電力購入コストとガス購入コストとの和

を目的関数とする。ここで、

とする。また、

とする。N_tはターボ冷凍機の台数であり、本実施例ではN_t=2である。なお、ガス購入単価は一定でC_Fr ⁱ=59.8[＼/Nm3]、Iは最適化で考慮する時間断面の最大値でI=24であるものとする。電力購入単価は以下の表１であるものとする。

また、購入電力E_r ⁱは以下により表されるものとする。

ここで、f_tj(x_tj ⁱ)はj番目のターボ冷凍機の消費電力であり、

と表されるものとする。また、f_ge(x_g ⁱ)はガスタービンの発電量であり、

と表されるものとする。E_L ⁱは時刻iにおける電力負荷であり、以下の表２であるものとする。

なお、購入電力が0以上となるように、

であるものとする。

このとき、ターボ冷凍機及び蒸気吸収式冷凍機の熱出力[MJ/h]と、ボイラ及びガスタービンのガス消費量[Nm3/h]とを全時間断面分（i=1,2,・・・,24）まとめた変数（連続変数）を決定変数Xとする。すなわち、N_sを蒸気吸収式冷凍機の台数（つまり、本実施例ではN_s=2）として

とすれば、決定変数Xは、

である。

また、ターボ冷凍機、蒸気吸収式冷凍機、ボイラ、及びガスタービンの稼働中を1、稼働停止を0として、全時間断面分（i=1,2,・・・,24）まとめた変数（バイナリ変数）を決定変数Yとする。すなわち、

とすれば、決定変数Yは、

である。

上記の数２２に示す目的関数を最適化する際には、各機器の上下限制約と、蒸気に関する制約条件と、供給する熱量（冷熱）と消費する熱量（冷熱）とのバランスに関する制約条件と、連続稼働・停止時間に関する制約条件とを満たす必要がある。

各機器の上下限制約は、以下であるものとする。

ここで、

であり、本実施例では、

であるものとする。また、f_bはボイラにおける消費ガス量と蒸気生成量と関係式であり、

であるものとする。なお、a_bはボイラにおける消費ガス量と蒸気生成量との特性係数ある。

蒸気に関する制約条件は、以下であるものとする。

ここで、f_gsはガスタービンにおける消費ガス量と蒸気生成量との関係式であり、

であるものとする。なお、a_gsはガスタービンにおける消費ガス量と蒸気生成量との特性係数である。

また、f_sjはj番目の蒸気吸収式冷凍機における熱出力と消費蒸気量との関係式であり、

であるものとする。なお、a_sj及びb_sjはj番目の蒸気吸収式冷凍機における熱出力と消費蒸気量との特性係数である。

供給する熱量（冷熱）と消費する熱量（冷熱）とのバランスに関する制約条件（すなわち、蓄熱槽に入力される冷熱量と出力される冷熱量とがバランスしていることを表す制約条件）は、以下であるものとする。

ここで、

である。本実施例では、

であるものとする。上記の数４０に示す制約条件は、最終時間断面以外のi=1,・・・,I-1と、最終時間断面のi=Iとでそれぞれ以下の上下限制約がある。

ここで、

である。本実施例では、

であるものとする。なお、最終時間断面のi=Iにおける上下限制約は、最終時間断面i=Iで冷熱を使い切らないようにするための制約である。

連続稼働・停止時間に関する制約条件は、以下であるものとする。

ここで、L_tjはj番目のターボ冷凍機の連続稼働時間・連続停止時間、L_sjはj番目の蒸気吸収式冷凍機の連続稼働時間・連続停止時間、L_gはガスタービンの連続稼働時間・連続停止時間、L_bはボイラの連続稼働時間・連続停止時間である。本実施例では、L_t1=2, L_t2=2, L_s1=2, L_s2=2, L_g=2, L_b=2であるものとする。

以上で定式化した混合整数計画問題が最適化装置１０に与えられると、入力部１０１が当該混合整数計画問題を入力し（図４のステップＳ１０１）、バイナリ変換部１０２が決定変数Xをバイナリ変数（の組み合わせ）に変換する（図４のステップＳ１０２）。ここで、本実施例では、離散化粒度N_k=5として、変換方法３により変換するものとする。この場合、バイナリ変換部１０２は、j番目のターボ冷凍機の変換パラメータw_tjm、j番目の蒸気吸収式冷凍機の変換パラメータw_sjm、ガスタービンの変換パラメータw_gm、及びボイラの変換パラメータw_bmをそれぞれ以下により計算することができる。

この計算結果をまとめると以下の表３になる。

なお、本実施例では離散化粒度N_kは全ての変数（つまり、決定変数Xの全ての要素）で固定の共通の値としているが、これに限られず、例えば、変数によってN_kの値を変えてもよい。また、変換パラメータは重みとして使用できるビット数に応じて、例えば、四捨五入等の処理によって簡略化してもよい。

バイナリ変換部１０２は、上記で計算した変換パラメータを用いて、以下により各決定変数（Xの各要素である変数）をバイナリ変数の組み合わせに変換する。

ここで、

がバイナリ変数である。

また、バイナリ変換部１０２は、組み合わせ最適化問題の制約条件として、以下を追加する。なお、これらの制約条件は、各機器が能力を超えた性能を発揮できないことを表す。

これにより、混合整数計画問題が、決定変数がバイナリ変数の組み合わせ最適化問題に変換される。

そして、組み合わせ最適化計算部１０３が当該組み合わせ最適化問題を計算機３０に計算させて（図４のステップＳ１０３）、この計算結果（組み合わせ最適化結果）から連続変換部１０４が混合整数計画問題の決定変数の最適値を計算し（図４のステップＳ１０４）、出力部１０５が当該最適値（最適化結果）を出力する（ステップＳ１０５）。

ここで、本実施例における最適化結果を図６に示す。図６は、実施例１における最適化結果を示す図である。なお、図６におけるトータルコストは、ガス購入コストと電力購入コストとの和である。

図６に示すように、i=1～24までのトータルコストの和は、4085527[＼]である。一方で、従来技術を用いて、決定変数が連続変数のまま最適化を行った場合、そのコストは4043150[＼]であった。したがって、本実施形態に係る最適化装置１０によれば、連続変数のまま最適化を行った場合と近い最適値が高速に得られることがわかる。

なお、例えば、量子化粒度N_k=100として、本実施形態に係る最適化装置１０により最適化を行った場合は、4045713[＼]であった。したがって、量子化粒度N_kの値を大きくし、バイナリ変数の数を増加させると、より高い精度で最適値が得られることがわかる。

なお、本実施例では、或る時刻t´において、決定変数X、Yの最適値を計算する場合について説明したが、例えば、時刻t´毎に、決定変数X、Yの最適値を繰り返し計算してもよい。すなわち、或る時間区間（例えば、制御周期等）を表すインデックスをt´、時刻t´における決定変数をX_t´、Y_t´として、時刻t´毎に、決定変数をX_t´、Y_t´の最適値を計算してもよい。

＜実施例２＞
以降では、実施例２として、実施例１と同じ系統モデルを用いて、図４のステップＳ１０２で離散化粒度N_k=5、変換方法４により変換する場合について説明する。この場合、バイナリ変換部１０２は、j番目のターボ冷凍機の変換パラメータw_tjm、j番目の蒸気吸収式冷凍機の変換パラメータw_sjm、ガスタービンの変換パラメータw_gm、及びボイラの変換パラメータw_bmをそれぞれ以下により計算する。

なお、本実施例においても、実施例１と同様に時刻t´毎に繰り返し、最適化計算を行ってもよい。

この計算結果をまとめると以下の表４になる。

なお、実施例１と異なり、実施例２では制約条件の追加は不要である。

このとき、図４のステップＳ１０３～ステップＳ１０５を行った後の本実施例の最適化結果を図７に示す。図７は、実施例２における最適化結果を示す図である。

図７に示すように、i=1～24までのトータルコストの和は、4047190[＼]である。このように、変換方法４を用いることで、変換方法３を用いた場合と比較して、より高い精度で最適値が得られることがわかる。

なお、上述したように、本実施形態では、計算機３０が最適化装置１０と一体となっていてもよい。この場合、例えば、組み合わせ最適化計算部１０３のみが量子コンピュータ等で実現されており、他の機能部（入力部１０１、バイナリ変換部１０２、連続変換部１０４、及び出力部１０５）はＣＰＵ１７で実現されていてもよいし、全ての機能部（入力部１０１、バイナリ変換部１０２、組み合わせ最適化計算部１０３、連続変換部１０４、及び出力部１０５）が量子コンピュータ等で実現されていてもよい。又は、例えば、組み合わせ最適化計算部１０３を含む一部の機能部のみが量子コンピュータ等で実現されていており、他の機能部はＣＰＵ１７で実現されていてもよい。

本発明は、具体的に開示された上記の各実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。

１最適化システム
１０最適化装置
２０端末
３０計算機
１０１入力部
１０２バイナリ変換部
１０３組み合わせ最適化計算部
１０４連続変換部
１０５出力部

Claims

混合整数計画問題が入力されると、前記混合整数計画問題の連続値又はバイナリ値を取る決定変数のうち、連続値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手段と、
前記組み合わせ最適化問題の最適解を量子コンピューティング装置に計算させる計算手段と、
前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手段と、
を有し、
前記第１の変換手段は、
前記連続値を取る決定変数の定義域を複数の区間に分割する点列と、複数のバイナリ変数とを用いて、前記点列を重みとする前記複数のバイナリ変数の重み付け和により前記連続値を取る決定変数を離散化する、ことを特徴とする最適化装置。
前記点列は、
前記連続値を取る決定変数の定義域を均等に複数の区間に分割する点列、又は、等比数列で表される点列のいずれかである、ことを特徴とする請求項１に記載の最適化装置。
前記第１の変換手段は、
前記重み付け和の各重みが、前記連続値を取る決定変数の定義域を複数の区間に均等に分割する点列である場合、前記組み合わせ最適化問題の制約条件として、前記複数のバイナリ変数の合計が１以下であることを表す制約条件を追加する、ことを特徴とする請求項２に記載の最適化装置。
前記重み付け和の合計値は、前記連続値を取る決定変数の定義域の範囲と一致する、ことを特徴とする請求項２又は３に記載の最適化装置。
前記計算手段は、
前記組み合わせ最適化問題の最適解を、前記量子コンピューティング装置又は組み合わせ最適化問題の計算に特化した計算機のいずれかに計算させる、ことを特徴とする請求項１乃至４の何れか一項に記載の最適化装置。
前記量子コンピューティング装置には、量子コンピュータが含まれる、ことを特徴とする請求項１乃至５の何れか一項に記載の最適化装置。
前記混合整数計画問題の最適解又は前記混合整数計画問題の最適解に所定の処理を施した結果を、前記最適化装置が備える表示装置又は前記最適化装置とは異なる他の装置が備える表示装置に表示させる、ことを特徴とする請求項１乃至６の何れか一項に記載の最適化装置。
最適化装置と、量子コンピューティング装置と、端末装置とが含まれる最適化システムであって、
前記最適化装置は、
混合整数計画問題が入力されると、前記混合整数計画問題の連続値又はバイナリ値を取る決定変数のうち、連続値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手段と、
前記組み合わせ最適化問題の最適解を、通信ネットワークを介して接続される前記量子コンピューティング装置に計算させる計算手段と、
前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手段と、
前記混合整数計画問題の最適解を、通信ネットワークを介して接続される前記端末装置に表示させる表示手段と、
を有し、
前記第１の変換手段は、
前記連続値を取る決定変数の定義域を複数の区間に分割する点列と、複数のバイナリ変数とを用いて、前記点列を重みとする前記複数のバイナリ変数の重み付け和により前記連続値を取る決定変数を離散化する、ことを特徴とする最適化システム。
混合整数計画問題が入力されると、前記混合整数計画問題の連続値又はバイナリ値を取る決定変数のうち、連続値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手順と、
前記組み合わせ最適化問題の最適解を量子コンピューティング装置に計算させる計算手順と、
前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手順と、
をコンピュータが実行し、
前記第１の変換手順は、
前記連続値を取る決定変数の定義域を複数の区間に分割する点列と、複数のバイナリ変数とを用いて、前記点列を重みとする前記複数のバイナリ変数の重み付け和により前記連続値を取る決定変数を離散化する、ことを特徴とする最適化方法。
混合整数計画問題が入力されると、前記混合整数計画問題の連続値又はバイナリ値を取る決定変数のうち、連続値を取る決定変数を離散化し、前記混合整数計画問題を組み合わせ最適化問題に変換する第１の変換手順と、
前記組み合わせ最適化問題の最適解を量子コンピューティング装置に計算させる計算手順と、
前記組み合わせ最適化問題の最適解を、前記混合整数計画問題の最適解に変換する第２の変換手順と、
をコンピュータに実行させ、
前記第１の変換手順は、
前記連続値を取る決定変数の定義域を複数の区間に分割する点列と、複数のバイナリ変数とを用いて、前記点列を重みとする前記複数のバイナリ変数の重み付け和により前記連続値を取る決定変数を離散化する、ことを特徴とするプログラム。