(57)【特許請求の範囲】
【請求項１】
０又は１の値をとる最適化変数の各々と、前記最適化変数の各々を選択した場合のコスト値の各々と、前記最適化変数の各々に対する制約の各々とが与えられたときに、前記制約を満たしつつ、前記最適化変数を最適化するための整数計画問題を解く最適化問題解決装置であって、
貪欲法による山登り法に従って、前記制約を満たしつつ、予め定められた、前記最適化変数の各々及び前記コスト値の各々と、前記制約の各々に対する、前記制約を表す不等式制約を等式制約に変換するための補助変数と、前記制約の各々に対する、前記制約を満たさない度合いを表す違反度合いとを含む目的関数を最適化するように、前記最適化変数を選択して更新することを繰り返す更新部と、
予め定められた反復終了条件を満たすまで、前記更新部による更新を繰り返させる反復判定部と、
前記更新部による更新で前記目的関数の最適値が得られる毎に、前記目的関数の最適値を比較して、より良い前記目的関数の最適値が得られたときの前記最適化変数の各々の値を暫定解として保持する結果比較部と、を含み、
前記更新部は、
前記最適化変数の各々を初期化する初期化部と、
前記最適化変数の各々及び前記制約の各々に対する違反度合いに基づいて、前記目的関数を最適化するように、前記制約の各々に対する補助変数を更新する補助変数更新部と、
前記最適化変数の各々に基づいて、前記目的関数を最適化するように、前記制約の各々に対する違反度合いを更新する違反度合更新部と、
前記制約の各々に対する補助変数及び前記制約の各々に対する違反度合いに基づいて、前記最適化変数の値を変更することにより前記目的関数の値を最も良くする前記最適化変数を選択して更新する最適化変数更新部と、
前記最適化変数の値を変更しても前記目的関数の値が良くならず、かつ、前記制約の各々を満たすまで、前記補助変数更新部による更新、前記違反度合更新部による更新、及び最適化変数更新部による更新を繰り返させる終了判定部と、
を含む最適化問題解決装置。
【請求項２】
前記最適化変数更新部は、前記最適化変数を選択して更新したとき前記最適化変数の各々の値の組み合わせを表すｂｉｔ列についてハッシュ値を計算し、キャッシュテーブルにおいて、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されている場合に、前記最適化変数の各々の値の組み合わせを表すｂｉｔ列と、前記計算されたハッシュ値をアドレスとした位置に格納されているｂｉｔ列とが一致するか否かを判定し、一致すると判定された場合、前記更新部による処理を終了し、一致しないと判定された場合、前記キャッシュテーブルにおいて、前記計算されたハッシュ値をアドレスとした位置に、前記最適化変数の各々の値の組み合わせを表すｂｉｔ列を格納する請求項１に記載の最適化問題解決装置。
【請求項３】
０又は１の値をとる最適化変数の各々と、前記最適化変数の各々を選択した場合のコスト値の各々と、前記最適化変数の各々に対する制約の各々とが与えられたときに、前記制約を満たしつつ、前記最適化変数を最適化するための整数計画問題を解く最適化問題解決装置における最適化問題解決方法であって、
更新部が、貪欲法による山登り法に従って、前記制約を満たしつつ、予め定められた、前記最適化変数の各々及び前記コスト値の各々と、前記制約の各々に対する、前記制約を表す不等式制約を等式制約に変換するための補助変数と、前記制約の各々に対する、前記制約を満たさない度合いを表す違反度合いとを含む目的関数を最適化するように、前記最適化変数を選択して更新することを繰り返すステップと、
反復判定部が、予め定められた反復終了条件を満たすまで、前記更新部による更新を繰り返させるステップと、
結果比較部が、前記更新部による更新で前記目的関数の最適値が得られる毎に、前記目的関数の最適値を比較して、より良い前記目的関数の最適値が得られたときの前記最適化変数の各々の値を暫定解として保持するステップと、を含み、
前記更新部が更新するステップは、
初期化部が、前記最適化変数の各々を初期化するステップと、
補助変数更新部が、前記最適化変数の各々及び前記制約の各々に対する違反度合いに基づいて、前記目的関数を最適化するように、前記制約の各々に対する補助変数を更新するステップと、
違反度合更新部が、前記最適化変数の各々に基づいて、前記目的関数を最適化するように、前記制約の各々に対する違反度合いを更新するステップと、
最適化変数更新部が、前記制約の各々に対する補助変数及び前記制約の各々に対する違反度合いに基づいて、前記最適化変数の値を変更することにより前記目的関数の値を最も良くする前記最適化変数を選択して更新するステップと、
終了判定部が、前記最適化変数の値を変更しても前記目的関数の値が良くならず、かつ、前記制約の各々を満たすまで、前記補助変数更新部による更新、前記違反度合更新部による更新、及び最適化変数更新部による更新を繰り返させるステップと、
を含む最適化問題解決方法。
【請求項４】
前記最適化変数更新部が更新するステップは、前記最適化変数を選択して更新したとき前記最適化変数の各々の値の組み合わせを表すｂｉｔ列についてハッシュ値を計算し、キャッシュテーブルにおいて、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されている場合に、前記最適化変数の各々の値の組み合わせを表すｂｉｔ列と、前記計算されたハッシュ値をアドレスとした位置に格納されているｂｉｔ列とが一致するか否かを判定し、一致すると判定された場合、前記更新部による処理を終了し、一致しないと判定された場合、前記キャッシュテーブルにおいて、前記計算されたハッシュ値をアドレスとした位置に、前記最適化変数の各々の値の組み合わせを表すｂｉｔ列を格納する請求項３に記載の最適化問題解決方法。
【請求項５】
コンピュータを、請求項１又は請求項２に記載の最適化問題解決装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化問題解決装置、方法、及びプログラムに係り、特に、整数計画問題を解くための最適化問題解決装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
資源の割り当て問題、アルバイトのシフト作成、容器への詰め込み問題など、任意の制約の元で、設定した効用を最良にする解を得たいといった場面は、現実世界でしばしば起こる状況である。このような場合、例えば、現実世界の問題を数式に落とし込んで最適化問題として定式化し、その最適化問題を解くことで、現実世界の問題を効果的に実行する方法を獲得するといった方法論がある。
【０００３】
ここでは、特に０−１整数計画問題と呼ばれる組合せ最適化問題で定式化できる問題を対象とする。一般的な０−１整数計画問題で表現できる現実の問題は多岐にわたるため、効果的な解法を作成することができれば、現実世界の多くの問題を効率的に解くことができる場面が増えることが見込める。
【０００４】
０−１整数計画問題は、一般形として以下のような式で表現できる。
【０００５】
【数１】
0006628041.tif 000002
【０００６】
ここで、ｚｊは最適化したい変数である。ここでは、０−１整数計画問題のみにフォーカスを当てているため、ｚｊの取り得る値は、０または１のみである。この、０または１のみの値を取るということを、上記（１）式では
【０００７】
【数２】
0006628041.tif 000003
【０００８】
で表現している。また、最適化変数ｚｊの個数は、
【０００９】
【数３】
0006628041.tif 000004
【００１０】
個であり、全体で
【００１１】
【数４】
0006628041.tif 000005
【００１２】
である。ここでは、簡単のため、
【００１３】
【数５】
0006628041.tif 000006
【００１４】
と記述する。ただし、
【００１５】
【数６】
0006628041.tif 000007
【００１６】
は１から始まる連続した整数の集合とし、１から
【００１７】
【数７】
0006628041.tif 000008
【００１８】
までを含むものとする。また、
【００１９】
【数８】
0006628041.tif 000009
【００２０】
も同様に、それぞれ１から始まる連続した整数の集合とし、それぞれ、
【００２１】
【数９】
0006628041.tif 000010
【００２２】
までを含むものとする。
【００２３】
ｃｊはｚｊを選択した際のコスト値になっている。もしｃｊが負の値であれば、選択することによって加点される状況であると解釈できる。目的関数はΣｊｃｊｚｊであるので、コストの線形和が最も小さくなるように最適化変数ｚｊを選択する、すなわちｚｊ＝１とする問題といえる。ただし、最適化変数ｚｊは自由に選択できるわけではなく、与えられた制約を満たす組み合わせで選択しなくてはいけない。
【００２４】
上記０−１整数計画問題の解法は、特定の問題に特化して効率的に解く方法が数多く存在する。一般論として、多様な問題に対して総じて効率的に解ける方法論として、限定分枝法に基づく方法が広く用いられている。ただし、これは一般には汎用ソルバーと呼ばれ、事前にどのような問題が与えられるかわからない状況に対応することが主眼となっているため、事前に解きたい問題の性質がわかっている場合は、その解きたい問題に適した専用の解法を用いた方が圧倒的に効率的に解を得られる場合がある。
【先行技術文献】
【非特許文献】
【００２５】
【非特許文献１】Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning, 2011.
【発明の概要】
【発明が解決しようとする課題】
【００２６】
前述の通り、０−１整数計画問題を解くためアルゴリズムはこれまでに様々な方法論が提案され、それぞれの方法はそれぞれの得意な問題の領域が存在する。そこで、０−１整数計画問題と呼ばれる組合せ最適化問題に関して、特に大規模かつ実行可能解が容易に発見できないといった特徴を持つ最適化問題を効率的に解く課題に取り組む。
【００２７】
本発明は、上記事情を鑑みて成されたものであり、効率よく、整数計画問題を解くことができる最適化問題解決装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２８】
上記目的を達成するために、第１の発明に係る最適化問題解決装置は、０又は１の値をとる最適化変数の各々と、前記最適化変数の各々を選択した場合のコスト値の各々と、前記最適化変数の各々に対する制約の各々とが与えられたときに、前記制約を満たしつつ、前記最適化変数を最適化するための整数計画問題を解く最適化問題解決装置であって、貪欲法による山登り法に従って、前記制約を満たしつつ、予め定められた、前記最適化変数の各々及び前記コスト値の各々を含む目的関数を最適化するように、前記最適化変数を選択して更新することを繰り返す更新部と、予め定められた反復終了条件を満たすまで、前記更新部による更新を繰り返させる反復判定部と、前記更新部による更新で前記目的関数の最適値が得られる毎に、前記目的関数の最適値を比較して、より良い前記目的関数の最適値が得られたときの前記最適化変数の各々の値を暫定解として保持する結果比較部と、を含んで構成されている。
【００２９】
また、第１の発明に係る最適化問題解決装置において、前記目的関数は、前記制約の各々に対する、前記制約を表す不等式制約を等式制約に変換するための補助変数と、前記制約の各々に対する、前記制約を満たさない度合いを表す違反度合いとを更に含み、前記更新部は、前記最適化変数の各々を初期化する初期化部と、前記最適化変数の各々及び前記制約の各々に対する違反度合いに基づいて、前記目的関数を最適化するように、前記制約の各々に対する補助変数を更新する補助変数更新部と、前記最適化変数の各々に基づいて、前記目的関数を最適化するように、前記制約の各々に対する違反度合いを更新する違反度合更新部と、前記制約の各々に対する補助変数及び前記制約の各々に対する違反度合いに基づいて、前記最適化変数の値を変更することにより前記目的関数の値を最も良くする前記最適化変数を選択して更新する最適化変数更新部と、前記最適化変数の値を変更しても前記目的関数の値が良くならず、かつ、前記制約の各々を満たすまで、前記補助変数更新部による更新、前記違反度合更新部による更新、及び最適化変数更新部による更新を繰り返させる終了判定部とを含むようにしてもよい。
【００３０】
また、第１の発明に係る最適化問題解決装置において、前記最適化変数更新部は、前記最適化変数を選択して更新したとき前記最適化変数の各々の値の組み合わせを表すｂｉｔ列についてハッシュ値を計算し、キャッシュテーブルにおいて、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されている場合に、前記最適化変数の各々の値の組み合わせを表すｂｉｔ列と、前記計算されたハッシュ値をアドレスとした位置に格納されているｂｉｔ列とが一致するか否かを判定し、一致すると判定された場合、前記更新部による処理を終了し、一致しないと判定された場合、前記キャッシュテーブルにおいて、前記計算されたハッシュ値をアドレスとした位置に、前記最適化変数の各々の値の組み合わせを表すｂｉｔ列を格納するようにしてもよい。
【００３１】
第２の発明に係る最適化問題解決方法は、０又は１の値をとる最適化変数の各々と、前記最適化変数の各々を選択した場合のコスト値の各々と、前記最適化変数の各々に対する制約の各々とが与えられたときに、前記制約を満たしつつ、前記最適化変数を最適化するための整数計画問題を解く最適化問題解決装置における最適化問題解決方法であって、更新部が、貪欲法による山登り法に従って、前記制約を満たしつつ、予め定められた、前記最適化変数の各々及び前記コスト値の各々を含む目的関数を最適化するように、前記最適化変数を選択して更新することを繰り返すステップと、反復判定部が、予め定められた反復終了条件を満たすまで、前記更新部による更新を繰り返させるステップと、結果比較部が、前記更新部による更新で前記目的関数の最適値が得られる毎に、前記目的関数の最適値を比較して、より良い前記目的関数の最適値が得られたときの前記最適化変数の各々の値を暫定解として保持するステップと、を含んで実行することを特徴とする。
【００３２】
また、第２の発明に係る最適化問題解決方法において、前記目的関数は、前記制約の各々に対する、前記制約を表す不等式制約を等式制約に変換するための補助変数と、前記制約の各々に対する、前記制約を満たさない度合いを表す違反度合いとを更に含み、前記更新部が更新するステップは、初期化部が、前記最適化変数の各々を初期化するステップと、補助変数更新部が、前記最適化変数の各々及び前記制約の各々に対する違反度合いに基づいて、前記目的関数を最適化するように、前記制約の各々に対する補助変数を更新するステップと、違反度合更新部が、前記最適化変数の各々に基づいて、前記目的関数を最適化するように、前記制約の各々に対する違反度合いを更新するステップと、最適化変数更新部が、前記制約の各々に対する補助変数及び前記制約の各々に対する違反度合いに基づいて、前記最適化変数の値を変更することにより前記目的関数の値を最も良くする前記最適化変数を選択して更新するステップと、終了判定部が、前記最適化変数の値を変更しても前記目的関数の値が良くならず、かつ、前記制約の各々を満たすまで、前記補助変数更新部による更新、前記違反度合更新部による更新、及び最適化変数更新部による更新を繰り返させるステップと、を含んで実行してもよい。
【００３３】
また、第２の発明に係る最適化問題解決方法において、前記最適化変数更新部が更新するステップは、前記最適化変数を選択して更新したとき前記最適化変数の各々の値の組み合わせを表すｂｉｔ列についてハッシュ値を計算し、キャッシュテーブルにおいて、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されている場合に、前記最適化変数の各々の値の組み合わせを表すｂｉｔ列と、前記計算されたハッシュ値をアドレスとした位置に格納されているｂｉｔ列とが一致するか否かを判定し、一致すると判定された場合、前記更新部による処理を終了し、一致しないと判定された場合、前記キャッシュテーブルにおいて、前記計算されたハッシュ値をアドレスとした位置に、前記最適化変数の各々の値の組み合わせを表すｂｉｔ列を格納するようにしてもよい。
【００３４】
また、第３の発明に係るプログラムは、コンピュータを、第１の発明に係る最適化問題解決装置の各部として機能させるためのプログラムである。
【発明の効果】
【００３５】
本発明の最適化問題解決装置、方法、及びプログラムによれば、貪欲法による山登り法に従って、制約を満たしつつ、予め定められた、最適化変数の各々及びコスト値の各々を含む目的関数を最適化するように、最適化変数を選択して更新することを繰り返し、予め定められた反復終了条件を満たすまで、更新を繰り返させることにより、効率よく、整数計画問題を解くことができる、という効果が得られる。
【図面の簡単な説明】
【００３６】
【図１】本発明の実施の形態に係る最適化問題解決装置の構成を示すブロック図である。
【図２】本発明の実施の形態に係る最適化問題解決装置における更新部の構成を示すブロック図である。
【図３】本発明の実施の形態に係る最適化問題解決装置における最適化問題解決処理ルーチンを示すフローチャートである。
【図４】本発明の実施の形態に係る最適化問題解決装置における更新処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００３７】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００３８】
＜本発明の実施の形態に係る概要＞
【００３９】
まず、本発明の実施の形態における概要を説明する。
【００４０】
前述の通り、０−１整数計画問題を解くためアルゴリズムはこれまでに様々な方法論が提案され、それぞれの方法はそれぞれに好適な問題の領域が存在する。そこで、本発明の実施の形態では、０−１整数計画問題と呼ばれる組合せ最適化問題に関して、特に大規模かつ実行可能解が容易に発見できないといった特徴を持つ最適化問題を効率的に解く課題に取り組む。
【００４１】
まず、本発明の実施の形態において取り組む課題においては、実行可能解が容易に獲得できないという前提がある。そのため、初期値として実行可能解を適当に得てから開始するアルゴリズムを用いることはできない。そこで、本発明の実施の形態では、適当な初期値をランダムに与え、そこから目的関数の値がよくなる方向に変数を一つずつ更新する、貪欲山登り法（貪欲法による山登り法）を用いる。ただし、貪欲山登り法では、局所解に陥って、真の最適解を得られない可能性が高い。そこで、現時点の最良の解を保持しつつ、貪欲山登り法を複数回繰り返して、より良い解を更新していくような方法論を用いる。本実施の形態では、この手法を反復貪欲山登り法と呼ぶこととする。
【００４２】
次に、実行可能解が容易に得られないという性質に対処するために、最適化アルゴリズム中により制約を満たす方向へ最適化変数を更新するような仕組みを導入する。また、制約を満たす方向へ向かう強さをコントロールできる仕組みを導入してもよい。これにより、解の探索中に、より実行可能解を発見しやすく調整することができる。
【００４３】
反復貪欲山登り法では、個々の貪欲山登り法の計算途中では別の探索結果を全く考慮しない方式となる。これは、余計な通信コストが発生しないため、非常に効率的であるが、一方で、同じ領域を何度も探索してしまう可能性があるため、探索が非効率になる可能性がある。そこで、オプションとして、全ての貪欲山登り法で共有するブルームフィルタを作成し、個々の貪欲山登り法によって探索した領域を、擬似的に共有する方法を用いる。
【００４４】
上記の手法の利点を、以下の（１）から（３）に述べる。
【００４５】
（１）反復貪欲山登り法の利用（大規模問題への適用）
【００４６】
貪欲山登り法により、個々の計算処理が容易であるため、最適化変数が多くても対応可能となる。また、個々の計算量は変数の数に対して線形時間。付加効果として、分散並列処理に適した枠組みであるため、容易に並列計算が可能となる。
【００４７】
（２）拡張ラグランジュ緩和法による緩和問題、及びＡＤＭＭ最適化に基づくアルゴリズムの枠組みの利用（実行可能解を効果的に探索する効果）
【００４８】
拡張ラグランジュ緩和による制約の緩和を行うことで、より制約を満たす方向で探索を行うことができる。また、制約を満たす度合いを制御するパラメタを自然に導入することができる。そのため、例えば、探索最初は制約を満たす強さを弱めにしておき、探索が進むにつれて、より制約を満たす方向へ探索を進めるといった戦略を取ることも可能となる。これにより、実行可能解が容易に見つからないことに対処できる。
【００４９】
（３）キャッシュテーブルの利用（重複探索の削除による更なる大規模問題へ適用）
【００５０】
複数回の貪欲山登り法を用いるため、これまでに探索した領域を何度も探索してしまう可能性がある。よって、重複探索を簡単なキャッシュテーブルを用いて排除し、全体の計算量を削減することができる。
【００５１】
＜本発明の実施の形態に係る原理＞
【００５２】
次に、本発明の実施の形態における原理を説明する。
【００５３】
ここでは、上記（１）式１に示された０−１整数計画問題を解く例を用いて、本発明の実施の形態の原理を説明する。
【００５４】
まず、上記（１）式に書かれているように、制約には、等式制約と不等式制約の二種類が存在する。本発明の実施の形態では、計算アルゴリズムを効率化するために、全ての制約を一旦不等式制約に変換したのち、それらを補助変数付きの等式制約の形式に変換し、問題を再定式化する。
【００５５】
まず、第一に全ての制約を不等式制約に変換する。上記（１）式の等式制約は、二つの不等式制約で記述することができる。
【００５６】
【数１０】
0006628041.tif 000011
【００５７】
この二つの不等式制約が同時に満たされるのは、等式制約が満たされるのと等価である。上記（２）式を用いることで、等式制約を不等式制約で記述できるので、最適化問題の全ての制約は不等式制約によって表現できる。計算を簡単にするために、不等式制約の向きを「≦０」の形式で全て変換する。これは、両辺に−１を掛けることによって、容易に実現できる。よって、係数ａｉ，ｊとｂｉを再定義し、全ての制約は
【００５８】
【数１１】
0006628041.tif 000012
【００５９】
の形式で記述できることになる。
【００６０】
最後に、上記の不等式制約を、補助変数ξｉ≧０を導入して、以下の等式制約に変換する。
【００６１】
【数１２】
0006628041.tif 000013
【００６２】
補助変数ξｉは０以上の値をとるので、不等式制約が満たされている場合はξｉの値を調節することで、等式制約を満たしたと判定することができる。逆に、不等式制約が満たされていない場合は、ξｉ＝０とするのが最も等式制約に近い値となる。このように、補助変数付きの等式制約は元の不等式制約を満たしているか、いないかの判定を一致させることができる。
【００６３】
元の不等式制約の数が
【００６４】
【数１３】
0006628041.tif 000014
【００６５】
個、等式制約の数が
【００６６】
【数１４】
0006628041.tif 000015
【００６７】
個の時、等式制約は２倍になるので、最終的に得られる補助変数付きの等式制約の数は
【００６８】
【数１５】
0006628041.tif 000016
【００６９】
個になる。また、
【００７０】
【数１６】
0006628041.tif 000017
【００７１】
とおき、上記（１）式の最適化問題を以下の形式で再定義する。
【００７２】
【数１７】
0006628041.tif 000018
【００７３】
次に、上記（５）式について、拡張ラグランジュ緩和法を用いて、制約を緩和する。
【００７４】
【数１８】
0006628041.tif 000019
【００７５】
このとき、Ｌは緩和問題の目的関数である。また、αｉは、制約を違反している場合にどの程度強くその違反をコストとして計上するかを制御するための違反度合いを表すパラメタである。また、ρは、制約を満たす強さを表すパラメタであり、ρ＞０とする。
【００７６】
上記（６）式を解くために、非特許文献１で紹介されているＡＤＭＭに則って最適化を行う。目的関数の最適化は、以下で説明する反復貪欲山登り法における、［２］の貪欲山登り法において実行する。
【００７７】
まず、本発明の実施の形態で用いる反復貪欲山登り法について説明する。一般的に一回の貪欲山登り法では最適解を得ることは難しい。そこで、初期値をランダムにふって、複数回の貪欲法による山登り法を用いて、より精度の高い解を得る。下記［２−５］の終了判定を満たした際に、暫定解を保持するが、その暫定解は、実行可能解であることを想定している。よって、現在暫定解として保持している目的関数の値よりも、より良い目的関数の値を獲得した場合は、暫定解を書き換えてより良い解のみを保持する。このように、複数回行うことで、一回のときより悪い結果になることは絶対になく、必ず良いか同じ暫定解が得られる。また、個々の貪欲法による山登り法の試行は完全に独立に行うことができるため、昨今の複数の演算装置がある計算機を効率的に利用して最適解の探索を行うことができる。
【００７８】
反復貪欲山登り法としては、全体として以下［１］から［５］の処理を行う。
【００７９】
［１］：独立に貪欲山登り法を行うオブジェクトをＮ個計算機内に生成する。
［２］：個々のＮ個に対して、後述する貪欲山登り法を実行する。
［３］：終了条件を満たしたｎ番目の結果を受け取る。
［４］：現在の最良の解と、［３］で受け取ったｎ番目の解を比較し、より良い結果であれば、それを保持する。
［５］：事前に設定した規定回数Ｋ回の貪欲法を実行する場合、規定回数Ｋに満たなければ、新たに貪欲山登り法を行うオブジェクトを作成して追加する。そして、［２］に戻って、追加したオブジェクトを、新たなｎ番目の処理として実行する。
【００８０】
次に、上記［２］の貪欲山登り法の基本的な処理手順を、以下の［２−１］から［２−５］に示す。
【００８１】
［２−１］：初期化
初期状態として、各ｚｊにランダムに０または１を代入する。
［２−２］：ξｉの更新
補助変数ξｉを更新する。ただし、更新が必要なξｉは、［２−４］で更新されたｚｊのうち制約の式の係数ａｉ，ｊが非零のもののみである。
［２−３］：αｉの更新
パラメタαｉを更新する。ただし、更新が必要なαｉは、［２−４］で更新されたｚｊのうち制約の式の係数ａｉ，ｊが非零のもののみである。
［２−４］：ｚｊの更新
目的関数の値が最もよくなる一つの最適化変数ｚｊを選択し値を更新する。つまり現在の値が１なら０へ更新し、０であれば［２−１］へ更新する。
［２−５］：終了判定
最適化変数ｚｊの変更がすべて目的関数の値をよくしない場合、かつ、実行可能解なら、現在の解を保持して終了し、それ以外の場合であれば［２−２］へ戻る。
【００８２】
＜本発明の実施の形態に係る最適化問題解決装置の構成＞
【００８３】
次に、本発明の実施の形態に係る最適化問題解決装置の構成について説明する。本実施の形態の最適化問題解決装置は、上記（１）式のように、０又は１の値をとる最適化変数と、最適化変数ｚｊを選択した場合のコスト値ｃｊと、最適化変数ｚｊに対する制約の各々とが与えられたときに、制約を満たしつつ、最適化変数ｚｊを最適化するための整数計画問題を解く装置である。
【００８４】
図１に示すように、本発明の実施の形態に係る最適化問題解決装置１００は、ＣＰＵと、ＲＡＭと、後述する最適化問題解決処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この最適化問題解決装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００８５】
入力部１０は、貪欲山登り法を行うオブジェクトを生成する指令を受け付ける。
【００８６】
演算部２０は、オブジェクト生成部３０と、更新部３２１〜３２Ｎと、キャッシュテーブル３３と、結果比較部３４と、反復判定部３６とを含んで構成されている。
【００８７】
オブジェクト生成部３０は、貪欲山登り法を行うＮ個のオブジェクトを生成し、オブジェクトの各々を更新部３２１〜３２Ｎに出力する。
【００８８】
更新部３２１〜３２Ｎは、オブジェクト生成部３０で生成されたオブジェクトの各々について、貪欲法による山登り法に従って、制約を満たしつつ、予め定められた、最適化変数ｚｊ及びコスト値ｃｊの各々を含む、上記（６）式の目的関数を最適化するように、最適化変数を選択して更新することを繰り返す。また、更新部３２１〜３２Ｎは、並列処理により、各々独立して更新処理を行う。また、更新部３２１〜３２Ｎは既に探索した最適化変数ｚｊの値の組み合わせ（解候補）を、ハッシュ値をアドレスとしてキャッシュテーブル３３に保存する。これにより更新部３２１〜３２Ｎでは、既に探索した最適化変数ｚｊの領域を排除して更新処理を行うことができる。
【００８９】
また、更新部３２１〜３２Ｎの各々はそれぞれ、初期化部２３０と、補助変数更新部２３２と、違反度合更新部２３４と、最適化変数更新部と、終了判定部２３８との各部を含んで構成されている。更新部３２１〜３２Ｎの各部の処理については後述する。
【００９０】
キャッシュテーブル３３には、更新部３２１〜３２Ｎで探索された最適化変数ｚｊの値の組み合わせ（解候補）が、ハッシュ値をアドレスとした位置に格納されている。
【００９１】
結果比較部３４は、更新部３２１〜３２Ｎによる更新で目的関数の最適値が得られる毎に、目的関数の最適値を比較して、より良い目的関数の最適値が得られたときの最適化変数の各々の値を暫定解として保持する。
【００９２】
反復判定部３６は、予め定められた反復終了条件を満たすまで、更新部３２１〜３２Ｎによる更新を繰り返させる。ここでは、反復終了条件は規定回数Ｋ回分の更新処理が更新部３２１〜３２Ｎによって行われたこととする。
【００９３】
次に、更新部３２１〜３２Ｎの各部の処理について説明する。
【００９４】
初期化部２３０は、複数の最適化変数ｚｊの値をランダムに初期化する。よって、このときに、制約を満たしているかは考慮しない。また、実行可能解が容易に得られない問題では、初期化段階で実行可能解になっていることはほぼない。また、初期化部２３０は、制約の各々に対する違反度合いであるαｉを初期化する。例えば、αｉは０にすればよい。
【００９５】
補助変数更新部２３２は、初期化された、又は前回更新された複数の最適化変数ｚｊ及び制約の各々に対する違反度合いαｉに基づいて、上記（６）式の目的関数を最適化するように、制約の各々に対する補助変数ξｉを更新する。
【００９６】
補助変数更新部２３２は、具体的には以下に説明するように、ξｉの最適値を解析的に求める。まず、補助変数ξｉ以外の全ての変数を固定して考えた場合、補助変数ξｉの最適値は、目的関数の勾配
【００９７】
【数１９】
0006628041.tif 000020
【００９８】
が０になる時の値である。目的関数の補助変数ξｉに関する勾配
【００９９】
【数２０】
0006628041.tif 000021
【０１００】
は以下（７）式となる。
【０１０１】
【数２１】
0006628041.tif 000022
【０１０２】
このように、補助変数ξｉの最適値は解析的に求めることができる。上記（７）式からもわかるように、例えば、特定の最適化変数ｚｊしか更新されていない場合は、特定の補助変数ξｉの値は前回と全く同じ値であることがある。これは、ｉ番目の制約の最適化変数ｚｊの係数ａｉ，ｊがａｉ，ｊ＝０である場合に、ｚｊの変更はｉ番目の制約に何も影響を与え無いためである。
【０１０３】
よって、逆に言えば、ある一つの最適化変数ｚｊのみが更新された場合は、ａｉ，ｊ≠０の制約のみを更新すれば良い。また、その変化量は、ａｉ，ｊの増減のみである。つまり、この計算は非常に高速に計算できる。例えば、ａｉ，ｊ≠０の制約が１０個であった場合は、１０個の補助変数ξｉに対してαｉを増減すればよい。
【０１０４】
上述したように、補助変数更新部２３２は、初期化された、又は前回更新された複数の最適化変数ｚｊ及び制約の各々に対する違反度合いαｉに基づいて、上記（７）式に従って、制約の各々に対する補助変数ξｉを更新する。
【０１０５】
違反度合更新部２３４は、初期化された、又は前回更新された複数の最適化変数ｚｊに基づいて、上記（６）式の目的関数を最適化するように、制約の各々に対する違反度合いαｉを更新する。
【０１０６】
違反度合更新部２３４は、具体的には以下に説明するように、違反度合いαｉの最適値を求める。
【０１０７】
ここでは、制約の違反度合いを判定したいので、元の不等式制約の違反度を反映させたい。よって、便宜上ξｉ＝０とおいてαｉの更新式を考える。目的関数Ｌのαｉに関する勾配
【０１０８】
【数２２】
0006628041.tif 000023
【０１０９】
は以下（８）式となる。
【０１１０】
【数２３】
0006628041.tif 000024
【０１１１】
ここでは、ξｉのように解析解は求まらないため、勾配法による反復計算により最適値を求める方法を用いる。その際の更新式は以下（９）式のようになる。
【０１１２】
【数２４】
0006628041.tif 000025
【０１１３】
ただし、ηは学習率であり、０＜η＜１の範囲の値をとることとする。ここでの注意点は、αｉ≧０の制約があるので、違反度合いαｉは、必ず０以上の値をとるようになっている点である。
【０１１４】
この更新の意味は、Σｊａｉ，ｊｚｊ−ｂｉ＞０の場合は制約が満たされていないので、
【０１１５】
【数２５】
0006628041.tif 000026
【０１１６】
の値に応じて、拡張ラグランジュ緩和法における双対変数の値が増加する。つまり、ｉ番目の制約に重みが加算され、次にｚｊの更新候補を選択する際に、よりｉ番目の制約を満たすことを考慮して選択が行われる。逆に、Σｊａｉ，ｊｚｊ−ｂｉ≦０の場合は制約が満たされていることを意味する。注意点としては、Σｊａｉ，ｊｚｊ−ｂｉ≦０であるので、負の値であるから、
【０１１７】
【数２６】
0006628041.tif 000027
【０１１８】
の値に応じて、違反度合いαｉの値は減ることになる。つまり、ｉ番目の制約を満たすことを考慮する点において、制約を満たす度合いを多少減らすことを意味する。
【０１１９】
また、違反度合いαｉも補助変数ξｉと同様に、例えば、特定の最適化変数ｚｊしか更新されていない場合は、特定の
【０１２０】
【数２７】
0006628041.tif 000028
【０１２１】
の値は前回と全く同じ値となる。具体的には、ｉ番目の制約のｚｊの係数ａｉ，ｊがａｉ，ｊ＝０である場合に、ｚｊの変更はｉ番目の制約に何も影響を与えないため
【０１２２】
【数２８】
0006628041.tif 000029
【０１２３】
の値は変化しない。よって、このようなケースで計算量を削減するために、
【０１２４】
【数２９】
0006628041.tif 000030
【０１２５】
の値をキャッシュしておくこととする。このキャッシュを実現するには、
【０１２６】
【数３０】
0006628041.tif 000031
【０１２７】
個の実数を保存するメモリを用いれば足りるため、効率がよい。
【０１２８】
上述したように、違反度合更新部２３４は、初期化された、又は前回更新された複数の最適化変数ｚｊに基づいて、上記（９）式に従って、制約の各々に対する違反度合いαｉを更新する。
【０１２９】
最適化変数更新部２３６は、以下に説明するように、補助変数更新部２３２で更新された制約の各々に対する補助変数ξｉ、及び違反度合更新部２３４で更新された制約の各々に対する違反度合いαｉに基づいて、値を変更することにより上記（６）式の目的関数の値を最も良くする最適化変数ｚｊを選択して更新する。
【０１３０】
最適化変数更新部２３６では、具体的には、以下の第１及び第２の処理によって最適化変数ｚｊを更新する。第１の処理は、最も目的関数の値を減らせる変数を一つ選択する処理である。第２の処理は、第１の処理で選択する変数が既に探索済みか判定する処理である。
【０１３１】
最適化変数更新部２３６は、第１の処理において、一回の変更で最も目的関数の値を減らせる最適化変数を選択して更新する。最適化変数の取り得る値は、０または１なので、最適化変数の現在の値が１であれば０、０であれば１へ変更した際に、緩和問題の目的関数Ｌの値を最も多く減らせる最適化変数を一つ選択する最適化問題を解けばよい。よって、最適化変数ｚｊに対して、現在の値から、もう一方の値に変化させた際に目的関数がどのぐらい変化するかを計算する必要がある。まず、ある任意のｊを一つ選択する。このとき、対象とする最適化変数ｚｊがｚｊ＝１の時の目的関数の値
【０１３２】
【数３１】
0006628041.tif 000032
【０１３３】
と、ｚｊ＝０の時の目的関数の値
【０１３４】
【数３２】
0006628041.tif 000033
【０１３５】
は以下（１０）式で記述できる。
【０１３６】
【数３３】
0006628041.tif 000034
【０１３７】
ここで、
【数３４】
0006628041.tif 000035
【０１３８】
と
【０１３９】
【数３５】
0006628041.tif 000036
【０１４０】
との値を比較すると、右辺第３項までは全く同じであることがわかる。よって、現在ｚｊ＝１であり、これをｚｊ＝０に変更した際の目的関数の増減は以下（１１）式で求められる。
【０１４１】
【数３６】
0006628041.tif 000037
【０１４２】
ここで、先ほど上記（８）式において、
【０１４３】
【数３７】
0006628041.tif 000038
【０１４４】
とおいたので、上記（１１）式はさらに以下（１２）式のようにかける。
【０１４５】
【数３８】
0006628041.tif 000039
【０１４６】
ここで、あるｊに対して、ａｉ，ｊ≠０の数を
【０１４７】
【数３９】
0006628041.tif 000040
【０１４８】
と記述するとすれば、右辺第２項は
【０１４９】
【数４０】
0006628041.tif 000041
【０１５０】
回の足し算
【０１５１】
【数４１】
0006628041.tif 000042
【０１５２】
の部分と、
【０１５３】
【数４２】
0006628041.tif 000043
【０１５４】
のａｉ，ｊとの掛け算をし、最後にρとの掛け算の計算量でｚｊを変化させた際の目的関数の変化量を計算することができる。
【０１５５】
また、現在ｚｊ＝０であり、これをｚｊ＝１に変更した場合の目的関数の増減は、上記（１２）式の右辺の値に−１を掛けると、以下（１３）式となることは容易にわかる。
【０１５６】
【数４３】
0006628041.tif 000044
【０１５７】
次に、最適化変数更新部２３６は、第２の処理において、第１の処理で選択して更新した最適化変数ｚｊの各々の値の組み合わせ（解候補）が既に探索済みであるか否かを判定する。
【０１５８】
これは、解候補が、既に処理した更新部３２１〜３２Ｎのいずれかの処理部における処理で既に出現していた場合は、処理中の更新部におけるそこから先の処理は、解候補が以前に出現した際の組み合わせと完全に一致してしまうため、無駄な処理になってしまう。この無駄な処理を削減するため、既に探索済みかどうかを判定し、探索済みの場合は、最適化変数をこれ以上更新しないようにする。
【０１５９】
ここでは、第１の処理で選択した最適化変数ｚｊを更新したときの最適化変数ｚｊの各々の値の組み合わせ（現在の解候補）を表すｂｉｔ列について、ｂｉｔ列から任意のハッシュ値を計算し、キャッシュテーブル３３における、計算したハッシュ値をアドレスとした位置に、現在の解候補のｂｉｔ列を格納する。このキャッシュテーブル３３を使うことで任意の解候補が既に出現したかどうかの判定自体は非常に単純に行うことができる。現在の解候補のｂｉｔ列からハッシュ値を計算し、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されている場合に、現在の解候補のｂｉｔ列と、計算されたハッシュ値をアドレスとした位置に格納さているｂｉｔ列とが完全一致する場合には、現在の解候補は探索済みであると判定することができる。
【０１６０】
ただし、キャッシュテーブル３３に利用可能なメモリ量は有限なので、これまで探索した解候補のｂｉｔ列を全て保持することは事実上不可能である。ここでは、「これまでに探索した解」を「これまでに探索していない解」とある程度間違えることは許容することとする。逆に、「これまでに探索していない解」を「これまでに探索した解」を間違えることは、探索中に到達不可能な解候補ができてしまうため、こちらは許容しないとする。
【０１６１】
これら二つの要件を満たすために、キャッシュテーブル３３内のｂｉｔ列は、同じハッシュ値になる場合は上書きされ、古いｂｉｔ列は消失する、という処理を導入する。これはつまり、キャッシュテーブルに入っているｂｉｔ列は、少なくとも、これまでに探索した解候補（の一部）であることは保証できる。一方、上書きにより古いｂｉｔ列が消失することがあるので、「これまでに探索した解」を「これまでに探索していない解」と間違えることが発生する。ただし、これによって、キャッシュテーブル３３の一定のメモリサイズ内で全ての処理を行うことが可能になるという利点が加えられる。
【０１６２】
実際の処理では、例えば、解候補のｂｉｔ列を固定長のブロックに分割し、各ブロック毎にブルームフィルタを構築することで、キャッシュテーブル３３の計算コストを削減するといった工夫ができる。
【０１６３】
これは、偽陽性（出現していなくても出現したと判定する）をある程度許容して、偽陰性（出現したものを出現していないと判定する）は起こらないというブルームフィルタの性質から、少なくとも全てのブロックで「出現した」と判定されなければ、絶対に出現していないことは保証できる。よって、キャッシュテーブル３３への問い合わせの前にブルームフィルタが一つでも出現していないと判定した場合には、それ以上の処理は不要となる。
【０１６４】
また、ブロックで分割したことと、一回で変更される変数は一つであることを加味して、一回の判定では、高々一回のブルームフィルタの計算を行えばよい。さらに、キャッシュテーブル３３のハッシュ計算とブルームフィルタで計算するハッシュとを共有することで、余計な計算を削減することもできる。
【０１６５】
上述したように、最適化変数更新部２３６は、補助変数更新部２３２で更新された制約の各々に対する補助変数ξｉ、及び違反度合更新部２３４で更新された制約の各々に対する違反度合いαｉに基づいて、上記（１３）式に示す目的関数の増減が最も大きい最適化変数ｚｊを選択して更新する。そして、選択した最適化変数ｚｊて￥を更新したときの最適化変数ｚｊの各々の値の組み合わせを表すｂｉｔ列についてハッシュ値を計算し、キャッシュテーブル３３において、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されている場合に、最適化変数の各々の値の組み合わせを表すｂｉｔ列と、計算されたハッシュ値をアドレスとした位置に格納されているｂｉｔ列とが一致するか否かを判定し、一致すると判定された場合、更新部３２１〜３２Ｎのうちの処理中の更新部による処理を終了し、一致しないと判定された場合、又は、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されていない場合に、キャッシュテーブル３３において、計算されたハッシュ値をアドレスとした位置に、最適化変数の各々の値の組み合わせを表すｂｉｔ列を格納する。
【０１６６】
終了判定部２３８は、どの最適化変数ｚｊの値を変更しても目的関数の値が良くならず、かつ、制約の各々を満たすまで（実行可能解となるまで）、補助変数更新部２３２による更新、違反度合更新部２３４による更新、及び最適化変数更新部２３６による更新を繰り返させる。
【０１６７】
＜本発明の実施の形態に係る最適化問題解決装置の作用＞
【０１６８】
次に、本発明の実施の形態に係る最適化問題解決装置１００の作用について説明する。入力部１０において貪欲山登り法を行うオブジェクトを生成する指令を受け付けると、最適化問題解決装置１００は、図３に示す最適化問題解決処理ルーチンを実行する。
【０１６９】
まず、ステップＳ１００では、入力部１０において受け付けた指令により、貪欲山登り法を行うＮ個のオブジェクトを生成し、ｎ＝１とする。
【０１７０】
次に、ステップＳ１０２では、生成されたｎ番目のオブジェクトについて、貪欲法による山登り法に従って、制約を満たしつつ、予め定められた、最適化変数ｚｊ及びコスト値ｃｊの各々を含む、上記（６）式の目的関数を最適化するように、最適化変数を選択して更新することを繰り返す。
【０１７１】
ステップＳ１０４では、ステップＳ１０２におけるｎ番目の目的関数の最適値の更新の結果を受け取る。
【０１７２】
ステップＳ１０６では、ステップＳ１０２で更新された目的関数の最適値を比較して、より良い目的関数の最適値が得られたときの最適化変数の各々の値を暫定解として保持する。
【０１７３】
ステップＳ１０８では、規定回数Ｋ回分の更新処理が行われたか否かを判定し、Ｋ回分の更新処理が行われていればステップＳ１１２へ移行し、Ｋ回分の更新処理が行われていなければステップＳ１１０でｎ＝ｎ＋１とし、ステップＳ１０２に戻って処理を繰り返す。
【０１７４】
ステップＳ１１２では、ステップＳ１０６で保持した目的関数の最適値を出力部５０に出力し、処理を終了する。
【０１７５】
ステップＳ１０２は、図４に示す更新処理ルーチンによって実行される。
【０１７６】
ステップＳ２００では、最適化変数ｚｊの値をランダムに初期化し、違反度合いαｉをαｉ＝０と初期化する。
【０１７７】
ステップＳ２０２では、初期化された、又は前回更新された複数の最適化変数ｚｊ及び制約の各々に対する違反度合いαｉに基づいて、上記（７）式に従って、制約の各々に対する補助変数ξｉを更新する。
【０１７８】
ステップＳ２０４では、初期化された、又は前回更新された複数の最適化変数ｚｊに基づいて、上記（９）式に従って、制約の各々に対する違反度合いαｉを更新する。
【０１７９】
ステップＳ２０６では、ステップＳ２０２で更新された制約の各々に対する補助変数ξｉ、及びステップＳ２０４で更新された制約の各々に対する違反度合いαｉに基づいて、上記（１３）式に示す目的関数の増減が最も大きい最適化変数ｚｊを選択する。
【０１８０】
ステップＳ２０８では、ステップＳ２０６で選択した最適化変数ｚｊを更新したときの最適化変数ｚｊの各々の値の組み合わせを表すｂｉｔ列についてハッシュ値を計算し、キャッシュテーブル３３において、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されているか否かを判定する。キャッシュテーブル３３において、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されていない場合には、ステップＳ２１０へ移行する。一方、キャッシュテーブル３３において、計算されたハッシュ値をアドレスとした位置にｂｉｔ列が格納されている場合に、ステップＳ２０９において、最適化変数の各々の値の組み合わせを表すｂｉｔ列と、計算されたハッシュ値をアドレスとした位置に格納されているｂｉｔ列とが一致するか否かを判定する。一致しないと判定された場合に、ステップＳ２１０へ移行し、一致すると判定された場合は、更新処理ルーチンを終了する。
【０１８１】
ステップＳ２１０では、キャッシュテーブル３３において、ステップＳ２０８で計算したハッシュ値をアドレスとした位置に、最適化変数ｚｊの値の組み合わせを表すｂｉｔ列を保存する。なお、計算したハッシュ値をアドレスとした位置に既にｂｉｔ列が存在する場合には上書きする。
【０１８２】
ステップＳ２１２では、どの最適化変数ｚｊの値を変更しても目的関数の値が良くならず、かつ、制約の各々を満たすことを条件として、条件を満たすか否かを判定し、条件を満たさなければステップＳ２０２に戻って処理を繰り返し、条件を満たせば更新処理ルーチンを終了する。
【０１８３】
ステップＳ２１４では、ステップＳ２０８でどの最適化変数ｚｊの値を変更しても目的関数の値が良くならず、かつ、制約の各々を満たすことを条件として、条件を満たすか否かを判定し、条件を満たさなければステップＳ２０２に戻って処理を繰り返し、条件を満たせば更新処理ルーチンを終了する。
【０１８４】
以上説明したように、本発明の実施の形態に係る最適化問題解決装置によれば、更新部３２１〜３２Ｎの各部が、貪欲法による山登り法に従って、制約を満たしつつ、予め定められた、最適化変数の各々及びコスト値の各々を含む目的関数を最適化するように、最適化変数を選択して更新することを繰り返し、反復判定部３６が、予め定められた反復終了条件を満たすまで、更新部３２１〜３２Ｎによる更新を繰り返させることにより、効率よく、整数計画問題を解くことができる。
【０１８５】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【０１８６】
１０   入力部
２０   演算部
３０   オブジェクト生成部
３２１〜Ｎ    更新部
３３   キャッシュテーブル
３４   結果比較部
３６   反復判定部
５０   出力部
１００ 最適化問題解決装置
２３０ 初期化部
２３１ 重複探索排除部
２３２ 補助変数更新部
２３４ 違反度合更新部
２３６ 最適化変数更新部
２３８ 終了判定部
【図１】
0006628041.tif 000045
【図２】
0006628041.tif 000046
【図３】
0006628041.tif 000047
【図４】
0006628041.tif 000048