(57)【要約】  受付部８１は、ｎ×ｎの正方行列Ａおよびｎ次元ベクトルｂを用いて、ｚＴＡｚ＋ｂＴｚで表されるＢＱＰに定式化可能な最適化問題を受け付ける。条件記憶部８２は、正の重み付き有向グラフの特性を表わす特性条件を記憶する。最適化部８３は、最適化問題を特性条件に基づいて変形し、変形された問題をネットワークフローの最小カット問題として解くことにより受け付けた最適化問題を解く。
2017199753.tif 000002
【特許請求の範囲】
【請求項１】
ｎ×ｎの正方行列Ａおよびｎ次元ベクトルｂを用いて
【数５６】
2017199753.tif 000058
で表されるＢＱＰに定式化可能な最適化問題を受け付ける受付部と、
正の重み付き有向グラフの特性を表わす特性条件を記憶する条件記憶部と、
受け付けた最適化問題を解く最適化部とを備え、
前記受付部は、前記式ＡにおけるＢＱＰが、ＣをＮ×Ｎの組合せとした場合における式Ｂ
【数５７】
2017199753.tif 000059
で示す制約を満たす最適化問題を受け付け、
前記最適化部は、前記最適化問題を前記特性条件に基づいて変形し、変形された問題をネットワークフローの最小カット問題として解くことにより受け付けた最適化問題を解く
ことを特徴とする最適化システム。
【請求項２】
条件記憶部は、Ａの要素ａｉｊ、ｂの要素ｂｉである場合における式Ｃ
【数５８】
2017199753.tif 000060
を定義した場合における、式Ｄ
【数５９】
2017199753.tif 000061
で表される特性条件を記憶する
請求項１記載の最適化システム。
【請求項３】
受付部は、総売上を最大にする複数の商品の価格を最適化する最適化問題、および、制約として１以上の価格の候補を受け付け、
最適化部は、前記受け付けた制約のもとで前記最適化問題を解く
請求項１または請求項２記載の最適化システム。
【請求項４】
最適化部は、正方行列Ａの全ての要素が非負であるとの制約のもとで、受け付けた最適化問題を解く
請求項１から請求項３のうちのいずれか１項に記載の最適化システム。
【請求項５】
ｎ×ｎの正方行列Ａおよびｎ次元ベクトルｂを用いて
【数６０】
2017199753.tif 000062
で表されるＢＱＰに定式化可能な最適化問題のうち、当該式ＡにおけるＢＱＰが、ＣをＮ×Ｎの組合せとした場合における式Ｂ
【数６１】
2017199753.tif 000063
で示す制約を満たす最適化問題を受け付け、
正の重み付き有向グラフの特性を表わす特性条件に基づいて前記最適化問題を変形し、変形された問題をネットワークフローの最小カット問題として解くことにより受け付けた最適化問題を解く
ことを特徴とする最適化方法。
【請求項６】
最適化部は、Ａの要素ａｉｊ、ｂの要素ｂｉである場合における式Ｃ
【数６２】
2017199753.tif 000064
を定義した場合、式Ｄ
【数６３】
2017199753.tif 000065
で表される特性条件に基づいて最適化問題を変形する
請求項５記載の最適化システム。
【請求項７】
コンピュータに、
ｎ×ｎの正方行列Ａおよびｎ次元ベクトルｂを用いて
【数６４】
2017199753.tif 000066
で表されるＢＱＰに定式化可能な最適化問題のうち、当該式ＡにおけるＢＱＰが、ＣをＮ×Ｎの組合せとした場合における式Ｂ
【数６５】
2017199753.tif 000067
で示す制約を満たす最適化問題を受け付ける受付処理、および、
正の重み付き有向グラフの特性を表わす特性条件に基づいて前記最適化問題を変形し、変形された問題をネットワークフローの最小カット問題として解くことにより受け付けた最適化問題を解く最適化処理
を実行させるための最適化プログラム。
【請求項８】
コンピュータに、
最適化処理で、Ａの要素ａｉｊ、ｂの要素ｂｉである場合における式Ｃ
【数６６】
2017199753.tif 000068
を定義した場合、式Ｄ
【数６７】
2017199753.tif 000069
で表される特性条件に基づいて最適化問題を変形させる
請求項７記載の最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＢＱＰ（binary quadratic programming）の最適化を行う最適化システム、最適化方法および最適化プログラムに関する。
【背景技術】
【０００２】
各種リソースを適切に利用できるようにするため、各種の最適化方法が提案されている。最適化が利用される例として、例えば、商品の価格の最適化や、在庫量の最適化などが挙げられる。【０００３】
非特許文献１には、最適化方法の一例として、ＢＱＰが記載されている。ＢＱＰは、最適化する対象を汎用的に定式化できるものであり、例えば、変数に相互関係があるような複雑な問題の最適化にも用いることが可能である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】片山謙吾、成久洋之、“バイナリ二次計画問題に対する局所探索法について”、岡山理科大学紀要、第35号、A、pp.179-187、1999
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＢＱＰは、ＮＰ困難な問題として知られている。そのため、コンピュータが非特許文献１に記載された方法を用いてＢＱＰの最適化処理を実行しようとすると、対象となる情報が多くなった場合など、効率的に最適化処理を実行することが難しいという技術的問題がある。【０００６】
一方、現実の世界では、最適化対象の特性に応じて想定される制約により、必ずしも厳密解を求める必要がない場面も存在する。例えば、ある商品の価格を値下げした場合、値下げした商品の売上が上がる一方で、同種の他の商品の売上が下がるといった関係が存在する。このような関係は、最適化対象の特性に応じて想定される制約であり、最適化の速度を向上させるために有効なものである。【０００７】
そこで、本発明は、より効率的にＢＱＰの最適化処理を実行することができる最適化システム、最適化方法および最適化プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明による最適化システムは、ｎ×ｎの正方行列Ａおよびｎ次元ベクトルｂを用いて、
【数１】
2017199753.tif 000003
で表されるＢＱＰに定式化可能な最適化問題を受け付ける受付部と、正の重み付き有向グラフの特性を表わす特性条件を記憶する条件記憶部と、受け付けた最適化問題を解く最適化部とを備え、受付部が、式ＡにおけるＢＱＰが、ＣをＮ×Ｎの組合せとした場合における式Ｂ
【数２】
2017199753.tif 000004
で示す制約を満たす最適化問題を受け付け、最適化部が、最適化問題を特性条件に基づいて変形し、変形された問題をネットワークフローの最小カット問題として解くことにより受け付けた最適化問題を解くことを特徴とする。【０００９】
また、本発明による最適化方法は、ｎ×ｎの正方行列Ａおよびｎ次元ベクトルｂを用いて、上記式Ａで表されるＢＱＰに定式化可能な最適化問題のうち、その式ＡにおけるＢＱＰが、ＣをＮ×Ｎの組合せとした場合における上記式Ｂで示す制約を満たす最適化問題を受け付け、正の重み付き有向グラフの特性を表わす特性条件に基づいて最適化問題を変形し、変形された問題をネットワークフローの最小カット問題として解くことにより受け付けた最適化問題を解くことを特徴とする。【００１０】
また、本発明による最適化プログラムは、コンピュータに、ｎ×ｎの正方行列Ａおよびｎ次元ベクトルｂを用いて上記式Ａで表されるＢＱＰに定式化可能な最適化問題のうち、その式ＡにおけるＢＱＰが、ＣをＮ×Ｎの組合せとした場合における上記式Ｂで示す制約を満たす最適化問題を受け付ける受付処理、および、正の重み付き有向グラフの特性を表わす特性条件に基づいて最適化問題を変形し、変形された問題をネットワークフローの最小カット問題として解くことにより受け付けた最適化問題を解く最適化処理を実行させることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、コンピュータが非特許文献１に記載された方法を用いてＢＱＰの最適化処理を実行する場合と比較して、コンピュータがより効率的にＢＱＰの最適化処理を実行することができる。また、ＢＱＰの最適化処理を実行するコンピュータの性能を向上することができるという技術的効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】本発明による最適化システムの第１の実施形態の構成例を示すブロック図である。
【図２】第１の実施形態の最適化システム１００の動作例を示すフローチャートである。
【図３】第１の実施形態の最適化部３０の動作例を示すフローチャートである。
【図４】第２の実施形態の最適化部３０の動作例を示すフローチャートである。
【図５】第３の実施形態の最適化部３０の動作例を示すフローチャートである。
【図６】第３の実施形態の変形例における最適化部３０の動作例を示すフローチャートである。
【図７】第３の実施形態の変形例における最適化部３０の動作例を示すフローチャートである。
【図８】本発明による最適化システムの概要を示すブロック図である。
【発明を実施するための形態】
【００１３】
以下、本発明の実施形態を図面を参照して説明する。
【００１４】
実施形態１．
本実施形態の最適化システムは、ＢＱＰに定式化可能な問題を最適化するものである。本実施形態の最適化システムは、以下の式１で表されるＢＱＰに定式化可能な問題を受け付ける。
【００１５】
【数３】
2017199753.tif 000005
【００１６】
式１において、Ａは、ｎ×ｎの正方行列であり、ｂはｎ次元ベクトルである。また、Ｃは、Ｃ⊆Ｎ×Ｎ（ただし、Ｎ＝｛１，２，…，ｎ｝）である。以下、Ａの要素をａｉｊと記し、ｂの要素をｂｉと記す。また、ｚは、各制約を示す。
【００１７】
以下の説明では、総売上を最大化するように複数の商品の価格を最適化する最適化問題を想定する。すなわち、本実施形態では、最適化システムは、複数の商品の売上の予測に基づいて、総売上を最大化するように複数の商品の価格を最適化するものとする。このとき、ｚの制約は、例えば、選択できる価格戦略のビジネス制約（各商品の価格候補、値引き可能商品の組み合わせなど）に対応する。
【００１８】
例えば、ある小売店において、この先一ヶ月のサンドイッチ群の売上高の総和を最大にする場合を考える。サンドイッチ群は、サンドイッチＡ、Ｂ、ＣおよびＤの４種類のサンドイッチを含むとする。この場合、サンドイッチ群の売上高の総和、すなわち、サンドイッチＡ、Ｂ、ＣおよびＤの４つのサンドイッチの売上高の総和が最大化されるように、サンドイッチＡ，Ｂ、ＣおよびＤのそれぞれの販売価格を最適化するという問題を解くことになる。
【００１９】
ここでは、サンドイッチＡの売上数量を予測するための予測モデルについて例示する。サンドイッチＡの売上数量は、サンドイッチＡ自体の販売価格の影響を受けると考えられる。また、サンドイッチＡの売上数量は、サンドイッチＡと共に商品棚に陳列されるサンドイッチ、すなわちサンドイッチＢ、ＣおよびＤの販売価格の影響も受けると考えられる。その小売店に来店する顧客は、商品棚に同時に陳列されるサンドイッチＡ、Ｂ、ＣおよびＤのうちから、好ましいサンドイッチを選択的に購入すると考えられるからである。
【００２０】
この状況で、例えば、サンドイッチＢが大安売りされている日を想定する。普段はサンドイッチＡを好んで購入する顧客であっても、このような日にはサンドイッチＡではなくサンドイッチＢを選択して購入する可能性がある。顧客（人間）が一度に食することができるサンドイッチの量には限りがあるので、一般的な顧客がサンドイッチＡとＢの両方を購入しようと考える可能性は低いからである。
【００２１】
この場合、結果的には、サンドイッチＢが安売りされていることにより、サンドイッチＡの売上数量が減ることになる。このような関係は、カニバリゼーション（市場の共食い関係）の関係と呼ばれる。
【００２２】
すなわち、このカニバリゼーションとは、ある商品の価格を下げると、その商品の売上量は上がる一方で、他の競合商品（性質や特徴が互いに類似した複数の商品）の売上量が減少するような関係である。
【００２３】
したがって、サンドイッチＡの売上数量ＳＡ（被説明変数）を予測する予測モデルは、例えば、サンドイッチＡの価格ＰＡ、サンドイッチＢの価格ＰＢ、サンドイッチＣの価格ＰＣおよびサンドイッチＤの価格ＰＤを説明変数として含む関数として表すことができる。
【００２４】
すなわち、上記予測モデルは、被説明変数（本実施形態においてはサンドイッチの売上数量）および説明変数（本実施形態においては、そのサンドイッチの販売価格および競合するサンドイッチの販売価格等）に基づいて学習され、被説明変数と説明変数との間の関係を示し、説明変数の関数で表されるものである。
【００２５】
本実施形態の最適化システムは、目的とする内容、すなわち、サンドイッチＡ、Ｂ、ＣおよびＤのそれぞれの販売価格（すなわち、ＰＡ、ＰＢ、ＰＣおよびＰＤ）の最適化を行う。具体的には、最適化システムは、目的変数（すなわち、ＰＡ、ＰＢ、ＰＣおよびＰＤ）等に対して定められた各種制約条件を満たしつつ、目的関数（すなわち、サンドイッチ群の売上高の総和）の値が最大になるように、目的変数（すなわち、ＰＡ、ＰＢ、ＰＣおよびＰＤ）の値を最適化する。
【００２６】
ここで、最適化対象のインデックスの集合を｛ｍ｜ｍ＝１，…，Ｍ｝と記す。本具体例では、最適化対象は各商品の価格であり、Ｍは商品数に対応する。また、各最適化対象ｍについて予測する内容をＳｍと記す。上述する例では、Ｓｍは、商品ｍの売上数量に対応する。また、各最適化対象ｍについて最適化する内容（すなわち、最適化の目的変数）をＰｍまたはＰ´ｍと記す。上述する例では、Ｐｍは、商品ｍの価格に対応する。線形回帰を使用してＳｍ（例えば、売上数量（需要））とＰｍ（例えば、価格）との依存関係をモデル化すると、Ｓｍを予測する予測モデルは、例えば、以下に例示する式２で表される。
【００２７】
【数４】
2017199753.tif 000006
【００２８】
式２において、ｆｄは特徴生成関数であり、Ｐ´ｍに対する変換を表わす。また、Ｄは特徴生成関数の数を示し、Ｐ´ｍに対して行われる変換の数を示す。ｆｄの内容は任意であり、例えば、線形変換を行う関数であってもよく、対数や多項式のような非線形変換を行う関数であってもよい。上述するように、Ｐｍが商品ｍの価格であり、Ｓｍが商品ｍの売上数量を示す場合、ｆｄは、例えば、価格に関する売上の反応を表わす。売上の反応とは、例えば、ある程度の値下げをすると売上の反応が良くなる、または、反応が悪くなる、値下げに応じて売上数量が二乗になる、などが挙げられる。
【００２９】
また、式２において、ｇｄは、外的特徴（上述する例の場合、天候など）であり、Ｄ´は、外的特徴の数である。なお、外的特徴に関しては、事前に変換をしておいてもよい。また、式２におけるα、β、γは、それぞれ機械学習の結果得られる回帰式の定数項および係数である。これまでの説明から明らかである通り、予測モデルは、被説明変数（Ｓｍ）および説明変数（Ｐｍや、各種外的特徴など）に基づいて学習され、被説明変数と説明変数との間の関係を示し、説明変数の関数で表されるものである。
【００３０】
また、商品の売上は、商品の価格と商品の売上数量の積の総和で表されるため、最適化システムは、例えば、以下の式３で表わされる目的関数を最適化することになる。
【００３１】
【数５】
2017199753.tif 000007
【００３２】
なお、このような最適化を行う過程において、上記で述べた機械学習に基づく予測モデルが、非線形な基底関数に基づく場合がある。例えば、上記で述べた価格の予測問題について、機械学習に基づく予測モデルへ入力する特徴量として、価格の二乗や価格の対数変換といった非線形変換を行うとする。この場合、数理最適化の目的関数（将来のある期間の売上）は、価格を複雑に非線形変換した特徴量の関数になるため、一般的な方法を用いて、このような数理最適化を効率的に解くことは難しい。
【００３３】
一方、商品の価格は連続した値を取るが、実際には、価格の候補は有限の個数に収まることが多い。そこで、最適化する内容のインデックスの集合を｛ｋ｜ｋ＝１，…，Ｋ｝とする。上述する例では、Ｋは価格の候補の数に対応する。例えば、商品「サンドイッチＡ」の価格の候補が、“割引なし、１％割引、２％割引および５％割引”の４つである場合、Ｋ＝４である。また、商品ｍの最適化する内容の候補の集合を、以下に示すように、上付きバーを付したＰｍｋと記す。上述する例では、上付きバーを付したＰｍｋは、商品ｍについての価格の候補を示す。
【００３４】
【数６】
2017199753.tif 000008
【００３５】
また、ｍのｋ番目のインジケータをＺｍｋと記す。ここで、Ｚｍｋは、以下の条件を満たす。
【００３６】
【数７】
2017199753.tif 000009
【００３７】
このように定義した場合、商品ｍの価格Ｐｍは、以下に例示する式４で定義される。
【００３８】
【数８】
2017199753.tif 000010
【００３９】
このとき、上述する式２は、以下のように変形可能である。
【００４０】
【数９】
2017199753.tif 000011
【００４１】
また、上述する式３は、以下に例示する式５のように変形可能である。なお、式５において、Ｚ＝（Ｚ１１，…，Ｚ１Ｋ，…，ＺＭＫ）である。
【００４２】
【数１０】
2017199753.tif 000012
【００４３】
また、上記式５は、さらに、以下の式６のように変形可能である。
【００４４】
【数１１】
2017199753.tif 000013
【００４５】
ここで、[Ｑ]ｉ，ｊは行列Ｑの（ｉ，ｊ）番目の要素であり、［ｒ］ｉはベクトルｒのｉ番目の要素である。したがって、上述するＱは、対称行列ではなく、半正定値ではない。したがって、価格の候補を離散的に定めることで、価格の最適化問題は、ＢＱＰに変形可能である。
【００４６】
さらに、混合整数計画緩和を用いて、上述する式５で特定される最適化問題を解くとする。上付きバーを付した新たな変数Ｚｉ，ｊを用いた場合、以下の式７で例示する変形処理が行われる。
【００４７】
【数１２】
2017199753.tif 000014
【００４８】
ここで、最適解において、上付きバーを付した変数Ｚｉ，ｊがＺｉＺｊをとる、以下の式８で示す制約が定義される。
【００４９】
【数１３】
2017199753.tif 000015
【００５０】
上述する式８に示す等式を追加することにより、上述する式７を以下に例示する式９のように新たに定式化できる。
【００５１】
【数１４】
2017199753.tif 000016
【００５２】
なお、制約条件数を減らして計算を効率化するために、上述する式９の条件から以下の不等式が削除されてもよい。
【００５３】
【数１５】
2017199753.tif 000017
【００５４】
このように、売上の合計を最大化するように各商品の価格を最適化する最適化問題は、以下の式１で表されるＢＱＰに定式化可能な問題と言える。
【００５５】
図１は、本発明による最適化システムの第１の実施形態の構成例を示すブロック図である。本実施形態の最適化システム１００は、受付部１０と、記憶部２０と、最適化部３０と、出力部４０とを備えている。
【００５６】
受付部１０は、上記式１で表されるＢＱＰに定式化可能な最適化問題を受け付ける。具体的には、受付部１０は、式１におけるＢＱＰのｚが式１の制約条件を満たす最適化問題を受け付ける。各商品の価格を最適化する最適化問題は、上述するように上記式１で表されるＢＱＰに定式化可能である。そのため、受付部１０は、総売上を最大にする複数の商品の価格を最適化する最適化問題、および、制約として１以上の価格の候補を受け付けてもよい。
【００５７】
なお、受付部１０が受け付ける最適化問題は、上記内容に限定されない。例えば、線形回帰関数の積和や、１−ｏｆ−Ｋ制約を有するＢＱＰなども、上記式１で表されるＢＱＰに定式化可能な最適化問題である。そのため、受付部１０は、これらで定式化される最適化問題を受け付けてもよい。
【００５８】
記憶部２０は、受け付けた最適化問題を解くための制約条件を記憶する。本実施形態では、記憶部２０は、正の重み付き有向グラフの特性を表わす条件（以下、特性条件と記す。）を記憶する。
【００５９】
以下の説明では、正の重み付き有向グラフをＧ＝（Ｖ，Ｅ，ｗ）で表す。Ｖは、有限の頂点の集合であり、ソース（源点）ｓおよびシンク（沈点）ｔは、いずれもＶに含まれる。Ｅは、有向エッジの集合であり、Ｅ⊆Ｖ×Ｖである。また、ｗは、Ｅの正の容量関数（Ｅ→Ｒ＞０）である。
【００６０】
頂点の数をＮとした場合、本実施形態では、ＶおよびＥを、それぞれ、以下の式１０のように定義する。
【００６１】
【数１６】
2017199753.tif 000018
【００６２】
ここで、Ｍ１およびＭ２は、エッジの集合であり、以下の式１１を満たす。
【００６３】
【数１７】
2017199753.tif 000019
【００６４】
また、各エッジに付与される値ｐｉおよびｑｉを、それぞれ、以下の式１２のように定義する。
【００６５】
【数１８】
2017199753.tif 000020
【００６６】
さらに、ｐｉおよびｑｉを用いて、各エッジの重みｗ（ｉ，ｊ）を、以下の式１３のように定義する。ここで、Ｌは、ユーザ等により定められる定数である。
【００６７】
【数１９】
2017199753.tif 000021
【００６８】
本実施形態では、記憶部２０は、上記式１０から式１３で表される特性条件を記憶する。記憶部２０は、例えば、磁気ディスク装置により実現される。
【００６９】
最適化部３０は、受け付けた最適化問題を解く。本実施形態の最適化部３０は、受け付けた最適化問題を、記憶部２０に記憶された特性条件に基づいて変形し、変形された最適化問題をネットワークフローの最小カット問題として解くことにより最適化する。なお、受け付けた最適化問題がＢＱＰに定式化されていない場合、最適化部３０は、その最適化問題をＢＱＰに変形してもよい。
【００７０】
また、本実施形態では、以下の式１４で示す制約が適用される。商品の価格最適化の場合、この制約（すなわち、ａｉｊが非負）とは、各商品が競合関係（ある商品の価格を下げると、他の商品が売れなくなる）にあることに対応する。
【００７１】
【数２０】
2017199753.tif 000022
【００７２】
まず、最適化部３０は、上記式１で表されるＢＱＰを、以下の式１５のように変形する。
【００７３】
【数２１】
2017199753.tif 000023
【００７４】
そして、最適化部３０は、受け付けた最適化問題を変形した上記式１５を、記憶部２０に記憶された特性条件に基づいて変形する。具体的には、最適化部３０は、最適化問題を以下の式１６のように変形する。
【００７５】
【数２２】
2017199753.tif 000024
【００７６】
ここで、Ｕとｚとの関係を以下に示す式１７で定める。
【００７７】
【数２３】
2017199753.tif 000025
【００７８】
この場合、Ｌを十分大きな値に定義すると、以下の式１８で表される正の重み付き有向グラフＧの最小カット問題（ｃＧ（Ｕ）。ただし、Ｕはｓ−ｔカット）は、以下の式１９に示す最適化問題と等価になる。すなわち、最小カット問題の最適解および最適値は、上記式１に示す問題のものと一致する。
【００７９】
【数２４】
2017199753.tif 000026
【００８０】
このようにして、最適化部３０は、ＢＱＰから変形された問題をネットワークフローの最小カット問題として解くことにより、受け付けた最適化問題を解く。そのため、一般的なＢＱＰを最適化する場合と比較し、より効率的に最適化を行うことができる。
【００８１】
出力部４０は、最適化の結果を出力する。例えば、最適化部３０が、受け付けた１以上の価格の候補を制約として、総売上を最大にする複数の商品の価格を最適化する最適化問題を解いた場合、出力部４０は、最適解として求めた各商品の価格を出力してもよい。
【００８２】
受付部１０と、最適化部３０と、出力部４０とは、プログラム（最適化プログラム）に従って動作するコンピュータのＣＰＵによって実現される。例えば、プログラムは、記憶部２０に記憶され、ＣＰＵは、そのプログラムを読み込み、プログラムに従って、受付部１０、最適化部３０および出力部４０として動作してもよい。また、受付部１０と、最適化部３０と、出力部４０とは、それぞれが専用のハードウェアで実現されていてもよい。
【００８３】
また、各装置の各構成要素の一部又は全部は、汎用または専用の回路（circuitry ）、プロセッサ等やこれらの組合せによって実現されもよい。これらは、単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。各装置の各構成要素の一部又は全部は、上述した回路等とプログラムとの組合せによって実現されてもよい。
【００８４】
また、各装置の各構成要素の一部又は全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は、集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントアンドサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【００８５】
次に、本実施形態の最適化システムの動作を説明する。図２は、第１の実施形態の最適化システム１００の動作例を示すフローチャートである。まず、受付部１０は、上記式１で表されるＢＱＰに定式化可能な最適化問題を受け付ける（ステップＳ１１）。
【００８６】
最適化部３０は、記憶部２０に記憶された正の重み付き有向グラフの特性を表わす特性条件を読み取る（ステップＳ１２）。
【００８７】
そして、最適化部３０は、受け付けた最適化問題を特性条件に基づいて変形し（ステップＳ１３）、変形された問題をネットワークフローの最小カット問題として解くことにより、受け付けた最適化問題を解く（ステップＳ１４）。
【００８８】
図３は、最適化部３０の動作例を示すフローチャートである。最適化部３０は、記憶部２０に記憶された正の重み付き有向グラフの特性を表わす特性条件として、上記式１０から式１３で表される特性条件を読み取る。このことにより、最適化部３０は、記憶部２０に記憶された上記式１０から式１３で表されるような正の重み付き有向グラフＧを構築する（ステップＳ２１）。
【００８９】
次に、最適化部３０は、Ｇの最小ｓ−ｔカット問題を解くことで、Ｕを最小ｓ−ｔカットとする（ステップＳ２２）。そして、最適化部３０は、上記式１７が成り立つようにｚ（ｚ∈｛０，１｝ｎ）を固定する（ステップＳ２３）。
【００９０】
以上のように、本実施形態では、受付部１０が、上記式１で表されるＢＱＰに定式化可能な最適化問題を受け付け、最適化部３０が、正の重み付き有向グラフＧの特性を表わす特性条件に基づいて、受け付けた最適化問題を変形し、変形された問題をネットワークフローの最小カット問題として解くことにより受け付けた最適化問題を解く。このように、ＢＱＰの最適化処理を実行する一般的なコンピュータと比較して、本実施形態に係る最適化システムは、その動作が異なるため、より効率的に最適化処理を実行することができる。
【００９１】
すなわち、本願発明では、最適化システムとして、単なるＢＱＰの最適化装置ではなく、ネットワークフローの最小カット問題を解くことが可能な装置（例えば、ＣＰＵ）と、正の重み付き有向グラフの特性条件を記憶した記憶部２０とが協働した情報処理装置を実現しているとも言える。よって、ＢＱＰを解く一般的な装置と比較し、コンピュータの性能を格段に向上させている。
【００９２】
なお、本実施形態の説明では、総売上を最大化する商品の価格を決定する事案に最適化システムを適用した。他にも、本実施形態の最適化システムを、例えば、商品の棚割りを最適化する事案に適用してもよい。例えば、Ｐを商品の価格とし、Ｈを棚の位置とし、θｍをパラメータとすると、商品ｍの売上数量Ｓｍの予測モデルは、例えば、以下のような線形回帰モデルで表すことができる。
【００９３】
Ｓｍ＝ｌｉｎｅａｒ＿ｒｅｇｒｅｓｓｉｏｎ(Ｐ，Ｈ，θｍ)
【００９４】
このとき、最適化部３０は、ＰおよびＨについて、売上（具体的には、商品ｍの価格Ｐｍと売上数量Ｓｍとの積の総和）を最大にするように最適化すればよい。また、この場合も、任意のビジネス制約（例えば、価格の条件など）が設定されてもよい。
【００９５】
また、上述した棚割り以外にも、小売価格最適化、ホテル部屋価格最適化、航空券価格最適化、駐車場料金最適化、キャンペーン最適化など、商材（サービス、製品いずれも含む）の価格と、商材の需要（複数の商材の価格の関数）との積で表される目的関数の最適化に、本願発明の最適化システムを適用可能である。
【００９６】
実施形態２．
次に、本発明による最適化システムの第２の実施形態を説明する。第２の実施形態の構成は、第１の実施形態と同様である。第１の実施形態では、受付部１０が上記式１で表されるＢＱＰに定式化可能な最適化問題を受け付ける場合について説明した。
【００９７】
ここで、最適化問題が、上記式１に示す制約に加え、以下の式２０に示す制約を満たす場合、上記式１をより効率よく解くことが可能である。そこで、本実施形態では、以下の式２０に示す制約を満たす場合の最適化部３０による最適化方法を説明する。
【００９８】
【数２５】
2017199753.tif 000027
【００９９】
始めに、有向グラフＨ＝（Ｎ，Ｃ）を定義する。本実施形態において、Ｎは頂点の集合を表わし、Ｃはエッジの集合を表わす。Ｎに含まれる頂点で構成される有向閉路ｎ１，ｎ２，…，ｎｋ，ｎ１を有向グラフが含む場合、上記式１の問題は、上記式２０の制約を含むことになる。すなわち、これは、ｚｎ１＝ｚｎ２＝…＝ｚｎｋを意味するものである。
【０１００】
Ｈの強連結成分にｎ１，ｎ２，…，ｎｋが含まれている場合にのみ、ｎ１，ｎ２，…，ｎｋ，ｎ１は、有向閉路を構成する。そのため、同じ連結成分に含まれる変数は、同じ値を取る必要がある。そのため、Ｈの強連結成分の分解は、以下の式２１で与えられる。
【０１０１】
【数２６】
2017199753.tif 000028
【０１０２】
そのため、各Ｎｋの変数の集合を１つの変数とみなすことにより、上記式１のＢＱＰは、より小さなＢＱＰに縮小させることが可能である。縮小後のＢＱＰは、以下の式２２で表される。
【０１０３】
【数２７】
2017199753.tif 000029
【０１０４】
式２２において、Ａ´は、Ｋ×Ｋの正方行列であり、ｂ´はＫ次元ベクトルである。また、Ｃ´は、Ｃ´⊆｛１，…，Ｋ｝×｛１，…，Ｋ｝である。なお、Ａ´、ｂ´およびＣ´は、以下に示す式２３および式２４によって定義される。
【０１０５】
【数２８】
2017199753.tif 000030
【０１０６】
このように強連結成分の分解を定義することにより、頂点の集合｛１，…Ｋ｝およびエッジの集合Ｃ´によって与えられる有向グラフは、有向閉路を含まなくなる。そのため、Ｈが非環式グラフであると想定しても一般性を失わない。
【０１０７】
ここで、上記式１のＡを、（Ａ＋ＡＴ）／２と置き換えることが可能である。全てのｚ（ｚ∈Ｒｎ）について、ｚＴＡｚ＝ｚＴ（Ａ＋ＡＴ）ｚ／２が成り立つからである。したがって、Ａを対称行列と想定しても一般性を失わない。
【０１０８】
上記式１で示される問題の目的関数は、以下の式２５で表される。
【数２９】
2017199753.tif 000031
【０１０９】
各ｚｉ∈｛０，１｝について、ｚｉｚｉ＝ｚｉが成り立つ。さらに、ｚｉ≦ｚｊの場合、ｚｉｚｊ＝ｚｉが得られる。よって、上記式１で示される問題の許容解ｚについて、目的関数の値は、ＡおよびｂをＡ´およびｂ´に置き換えた後も変わらない。ここで、置き換えられるＡ´およびｂ´は、以下の式２６および式２７で定義されるものである。
【０１１０】
【数３０】
2017199753.tif 000032
【０１１１】
ここで、Ｐｉ⊆Ｎは、以下の式２８で与えられる。
【０１１２】
【数３１】
2017199753.tif 000033
【０１１３】
このように、Ａおよびｂを置き換えることで、Ａの要素のうち０でない要素の数を減らすことができるため、問題の複雑性を抑えることが可能になる。すなわち、最適化部３０が、このように変形された問題を最適化するため、より効率的に最適化を行うことができる。
【０１１４】
次に、本実施形態の最適化システムの動作を説明する。図４は、本実施形態の最適化部３０の動作例を示すフローチャートである。最適化部３０は、有向グラフＨ＝（Ｎ，Ｃ）の強連結成分の分解を計算し（ステップＳ３１）、上記式２３および式２４に記載されているように、各成分を１つの変数にする（ステップＳ３２）。最適化部３０は、行列Ａを左右対称とする。すなわち、最適化部３０は、Ａを（Ａ＋ＡＴ）／２で再定義する（ステップＳ３３）。最適化部３０は、上記式２８で定義されるＰｉ⊆Ｎを計算し（ステップＳ３４）、上記式２６および式２７に記載されたＡおよびｂを再定義する（ステップＳ３５）。
【０１１５】
以上のように、本実施形態では、上記式２０に示す制約のもと、上記式１の問題のＡおよびｂを、有向グラフＨの強連結成分を分解することにより再定義する。このような再定義により、問題の複雑性を抑えることが可能になるため、より効率的に最適化を行うことができる。
【０１１６】
また、上記の式１４で示す制約が成立していない場合であっても、本実施形態で示すようにＡおよびｂを再定義することにより、上記の式１４で示す制約を満たすようになる可能性もある。
【０１１７】
なお、強連結成分は、例えば、Ｔａｒｊｉｎのアルゴリズムでは、Ｏ（ｎ＋｜Ｃ｜）のオーダで計算される。より効率よく計算するため、最適化部３０は、以下の式２９に示す性質を用いて｛Ｐｉ｝ｎｉ＝１を計算してもよい。
【０１１８】
【数３２】
2017199753.tif 000034
【０１１９】
実施形態３．
次に、本発明による最適化システムの第３の実施形態を説明する。第３の実施形態の構成も、第１の実施形態と同様である。第１の実施形態では、最適化部３０が上記の式１４で示す制約を満たすＢＱＰを解く場合について説明した。すなわち、あるｉおよびｊについてａｉｊ＜０の場合、最適化部３０は、上記式１で示される問題を第１の実施形態で説明した方法によって最適化することはできない。そこで、本実施形態では、この場合（ａｉｊ＜０になるｉ，ｊが存在する場合）でも近似的に最適解を求める方法を説明する。
【０１２０】
本実施形態では、以下の式３０で示す線形項によりａｉｊｚｉｚｊを近似する。なお、式３０において、０≦α≦１である。
【０１２１】
【数３３】
2017199753.tif 000035
【０１２２】
ここで、行列ＡをＡ＋∈Ｒｎ×ｎ≧０とＡ−∈Ｒｎ×ｎ≧０に分解することを考える。具体的には、Ａ＋＝（ａｉｊ＋）∈Ｒｎ×ｎ，Ａ−＝（ａｉｊ−）∈Ｒｎ×ｎであり、ａｉｊ＋とａｉｊ−が以下の式３１で与えられる場合、最適化部３０は、Ａ＋−Ａ−＝ＡになるようにＡを分解する。
【０１２３】
【数３４】
2017199753.tif 000036
【０１２４】
この場合、上記式１で示される問題の目的関数は、以下の式３２で表される。
【０１２５】
【数３５】
2017199753.tif 000037
【０１２６】
任意の実数値α∈［０，１］は、以下の式３３を満たす。
【０１２７】
【数３６】
2017199753.tif 000038
【０１２８】
よって、以下の式３４を満たす任意のＢ＝（ｂｉｊ）∈Ｒ≧０は、以下の式３５を満たす。
【０１２９】
【数３７】
2017199753.tif 000039
【０１３０】
【数３８】
2017199753.tif 000040
【０１３１】
したがって、以下の式３６に示す問題の最適値は、上記式１で示される問題の最適値の上界になる。
【０１３２】
【数３９】
2017199753.tif 000041
【０１３３】
ここで、Ｂ＝Ａ−／２と定義する。すると、上記式３６の目的関数から、上記式１の目的関数を減算した関数は、以下の式３７になる。
【０１３４】
【数４０】
2017199753.tif 000042
【０１３５】
したがって、上記式１の目的関数の最適解をｚ＊とし、上記式３６の目的関数の最適解をｚ上付きチルダとすると、以下に示す式３８の関係が保証される。
【０１３６】
【数４１】
2017199753.tif 000043
【０１３７】
上述する議論により、以下のような、上記式１の問題の許容解を計算するための多項式時間アルゴリズムが存在することが分かる。
【０１３８】
【数４２】
2017199753.tif 000044
【０１３９】
そこで、本実施形態の最適化部３０は、上記式３６に示す問題をネットワークフローの最小カット問題として解くことにより、受け付けた最適化問題の近似解を算出する。
【０１４０】
次に、本実施形態の最適化システムの動作を説明する。図５は、本実施形態の最適化部３０の動作例を示すフローチャートである。まず、最適化部３０は、有向グラフＨ＝（Ｎ，Ｃ）から有向閉路を除外し（ステップＳ４１）、二次項を減少させる。次に、最適化部３０は、Ｂ＝Ａ−／２とする上記式３６の緩和問題を定義する（ステップＳ４２）。
【０１４１】
次に、最適化部３０は、第１の実施形態で説明したネットワークフローの最小カット問題を解く方法（より具体的には、図３のフローチャートに示す方法）を用いて、上記式３６の問題を解き、ｚの上付きハット（以下、単にｚハットと記す。）を上記式３６の最適解とする（ステップＳ４３）。
【０１４２】
その後、出力部４０は、ｚハットおよびｚハットに関する上記式１の問題の目的関数の値（上記式１の問題の最適値の下界）を出力し（ステップＳ４４）、また、上記式３６の値（上界）を出力する（ステップＳ４５）。
【０１４３】
以上のように、本実施形態では、最適化部３０が、上記式１に示す問題を式３６に示す問題に緩和して最適化する。よって、上記の式１４で示す制約を満たさない場合であっても、多項式時間で上記式１の問題の最適解の近似値を求めることが可能になる。
【０１４４】
次に、本実施形態の最適化システムの変形例を説明する。第３の実施形態では、図５に例示するアルゴリズムに基づいて近似値を算出する方法を説明した。本変形例では、上記式１に示す問題の双対問題を考え、ネットワークの重み付けを変化させながら繰り返し最小カット問題を解くことにより、図５に例示するアルゴリズムよりもより適切な解を求める方法を説明する。
【０１４５】
以下に示す式３９により、φ：｛０，１｝ｎ×［０，１］ｎ×ｎ→Ｒを定義する。
【０１４６】
【数４３】
2017199753.tif 000045
【０１４７】
式３９において、Ａ−○Ｂは、アダマール積、すなわち、（Ａ−○Ｂ）ｉｊ＝（Ａ−）ｉｊ・（Ｂ）ｉｊを表わす。また、以下の式４０に示す関係が満たされるため、φについて、以下の式４１が得られる。
【０１４８】
【数４４】
2017199753.tif 000046
【０１４９】
ここで、Ｒを上記式１の問題の許容解とすると、上記式１の最適値は、以下の式４２のように表される。
【０１５０】
【数４５】
2017199753.tif 000047
【０１５１】
ここで、以下の式４３が成り立つため、最適化部３０は、以下の式４４に示す問題を解くことにより、上記式１の問題の最適値の上界を得ることができる。なお、ψ：［０，１］ｎ×ｎ→Ｒは、以下の式４５で定義される。
【０１５２】
【数４６】
2017199753.tif 000048
【０１５３】
与えられるＢに対し、最適化部３０は、ｚ＊∈ａｒｇｍａｘｚφ（ｚ，Ｂ）およびψ（Ｂ）を計算する。さらに、最適化部３０は、∇Ｂφ（ｚ＊，Ｂ）を以下の式４６で計算する。
【０１５４】
【数４７】
2017199753.tif 000049
【０１５５】
このとき、上記式４４に示す問題の最適解は、以下の式４７で示す範囲にあることが保証される。
【０１５６】
【数４８】
2017199753.tif 000050
【０１５７】
このことから、最適化部３０は、上記式４４の問題についての楕円体法を構築することが可能である。これは、上記式４４の問題が多項式時間で解けることを意味する。そこで、最適化部３０は、構築した楕円体法に基づいて上記式１の最適化する。
【０１５８】
なお、実際には楕円体法は低速である。そこで、最適化部３０は、Ｂに関し、よりシンプルな勾配降下アルゴリズムを用いてもよい。この場合、最適化部３０は、各ステップｔに対する検索方法Ｓｔを、以下の式４８および式４９によって定義する。
【０１５９】
【数４９】
2017199753.tif 000051
【０１６０】
また、最適化部３０は、ステップサイズηｔを、以下の式５０によって定義する。なお、式５０において、ｓ＝ｔ＋（定数）である。
【０１６１】
【数５０】
2017199753.tif 000052
【０１６２】
そして、Ｐｒｏｊ［０，１］（Ｂ）は、以下の式５１で定義される。
【０１６３】
【数５１】
2017199753.tif 000053
【０１６４】
このように定義することで、最適化部３０は、勾配降下アルゴリズムを用いて上記式１の最適化をすることが可能になる。
【０１６５】
次に、本変形例の最適化システムの動作を説明する。図６および図７は、本変形例の最適化部３０の動作例を示すフローチャートである。まず、Ｂ１を以下に示す式５２のように定め（ステップＳ５０）、最適化部３０は、以下のステップＳ５１からステップＳ５７までの処理を繰り返す。
【０１６６】
【数５２】
2017199753.tif 000054
【０１６７】
まず、最適化部３０は、第１の実施形態で最適化問題を解くために用いられるアルゴリズム（具体的には、図２のフローチャートに例示するアルゴリズム）を用いて、ｚｔ∈ａｒｇｍａｘｚφ（ｚ，Ｂｔ）を計算する（ステップＳ５１）。また、最適化部３０は、以下の式５３を用いてｖａｌｕｅｔとｕｂｔを計算する（ステップＳ５２）。
【０１６８】
【数５３】
2017199753.tif 000055
【０１６９】
算出したｕｂｔとｖａｌｕｅｔとの差が予め定めた値εより小さい、または、ｔが予め定めた最大値Ｔｍａｘ以下の場合（ステップＳ５３におけるＹＥＳ）、最適化部３０は、ｚｔ、ｖａｌｕｅｔおよびｕｂｔを結果とする（ステップＳ５４）。
【０１７０】
一方、ステップＳ５３におけるＮＯの場合において、ｔ＞２、ｕｂｔ＝ｕｂｔ−２かつｕｂｔ≦ｕｂｔ−１の場合（ステップＳ５５におけるＹＥＳ）、ループを抜け、ステップＳ５８に移る。一方、ステップＳ５５におけるＮＯの場合、最適化部３０は、Ｂｔ＋１を、以下の式５４で定義する（ステップＳ５６）。そして、最適化部３０は、ｔを１インクリメントし（ステップＳ５７）、ステップＳ５１からの処理を繰り返す。
【０１７１】
【数５４】
2017199753.tif 000056
【０１７２】
ステップＳ５１からステップＳ５７のループのあと、最適化部３０は、ｓに１をセットする（ステップＳ５８）。以降、最適化部３０は、以下のステップＳ５９からステップＳ６５までの処理を繰り返す。
【０１７３】
まず、最適化部３０は、上記の式４８から式５０を用いて、検索方法Ｓｔおよびステップサイズηｔを計算する（図７におけるステップＳ５９）。次に、最適化部３０は、Ｂｔ＋１を、以下の式５５で定義する（ステップＳ６０）。
【０１７４】
【数５５】
2017199753.tif 000057
【０１７５】
最適化部３０は、第１の実施形態で最適化問題を解くために用いられるアルゴリズム（具体的には、図２のフローチャートに例示するアルゴリズム）を用いて、ｚｔ∈ａｒｇｍａｘｚφ（ｚ，Ｂｔ）を計算する（ステップＳ６１）。また、最適化部３０は、上記式５３を用いてｖａｌｕｅｔとｕｂｔを計算する（ステップＳ６２）。
【０１７６】
算出したｕｂｔとｖａｌｕｅｔとの差が予め定めた値εより小さい、または、ｔが予め定めた最大値Ｔｍａｘ以下の場合（ステップＳ６３におけるＹＥＳ）、最適化部３０は、ｚｔ、ｖａｌｕｅｔおよびｕｂｔを結果とする（ステップＳ６４）。
【０１７７】
一方、ステップＳ６３におけるＮＯの場合、最適化部３０は、ｔおよびｓをそれぞれ１インクリメントし（ステップＳ６５）、ステップＳ５９以降の処理を繰り返す。
【０１７８】
以上のように、本変形例では、上記式１に示す問題の双対問題を考え、最適化部３０がネットワークの重み付けを変化させながら繰り返し最小カット問題を解く。そのため、図５に例示するアルゴリズムよりも計算時間はかかる一方で、より適切な解を求めることが可能になる。
【０１７９】
次に、本発明の概要を説明する。図８は、本発明による最適化システムの概要を示すブロック図である。本発明による最適化システム８０（例えば、最適化システム１００）は、ｎ×ｎの正方行列Ａおよびｎ次元ベクトルｂを用いて、上記式Ａで表されるＢＱＰに定式化可能な最適化問題（例えば、上記の式１）を受け付ける受付部８１（例えば、受付部１０）と、正の重み付き有向グラフ（例えば、Ｇ＝（Ｖ，Ｅ，ｗ））の特性を表わす特性条件（例えば、上記式１０から式１３で表される特性条件）を記憶する条件記憶部８２（例えば、記憶部２０）と、受け付けた最適化問題を解く最適化部８３（例えば、最適化部３０）とを備えている。
【０１８０】
受付部８１は、式ＡにおけるＢＱＰが、ＣをＮ×Ｎの組合せとした場合における上記式Ｂで示す制約を満たす最適化問題を受け付け、最適化部８３は、最適化問題を特性条件に基づいて変形し、変形された問題をネットワークフローの最小カット問題として解くことにより受け付けた最適化問題を解く。
【０１８１】
そのような構成により、より効率的にＢＱＰの最適化を行うことができる。
【０１８２】
具体的には、条件記憶部８２は、Ａの要素ａｉｊ、ｂの要素ｂｉである場合における上記式１１および式１２を定義した場合における、上記式１０および式１３で表される特性条件を記憶してもよい。
【０１８３】
また、受付部８１は、総売上を最大にする複数の商品の価格を最適化する最適化問題、および、制約として１以上の価格の候補を受け付け、最適化部８３は、受け付けた制約のもとで最適化問題を解いてもよい。そのような場合、価格最適化問題をより高速に解くことが可能になる。
【０１８４】
また、最適化部は、正方行列Ａの全ての要素が非負であるとの制約（例えば、上記式１４で示す制約）のもとで、受け付けた最適化問題を解いてもよい。
【０１８５】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１８６】
この出願は、２０１６年５月１８日に出願された米国仮出願第６２／３３８，０２０号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１８７】
１０  受付部
２０  記憶部
３０  最適化部
４０  出力部
【図１】
2017199753.tif 000070
【図２】
2017199753.tif 000071
【図３】
2017199753.tif 000072
【図４】
2017199753.tif 000073
【図５】
2017199753.tif 000074
【図６】
2017199753.tif 000075
【図７】
2017199753.tif 000076
【図８】
2017199753.tif 000077
【国際調査報告】
2017199753.tif 000078
2017199753.tif 000079
2017199753.tif 000080
2017199753.tif 000081