(57)【要約】【課題】効果的に離散最適化問題を分割する問題分割方法、問題分割装置、離散最適化問題を効率的に解く最適化方法、最適化装置、及びコンピュータプログラムを提供する。【解決手段】原問題を分割した複数の問題を記憶し（Ｓ２）、記憶している複数の問題の中から一の問題を選択し（Ｓ３）、選択した問題を解くことが困難であるか否かを判定する（Ｓ７）。解くことが困難である場合は、一の活性変数を選択し（Ｓ９）、選択した活性変数の値を取りうる値の夫々に固定して、選択している問題を複数の問題に分割する（Ｓ１０）。解くことが困難でない場合は、選択している問題を解いて該問題の最適解を求める（Ｓ１１）。求めた最適解のうち最も最適化されている解が原問題の最適解である。【選択図】　　　　図３
2004133802.tif 000002
【特許請求の範囲】
【請求項１】
記憶部及び演算部を備えたコンピュータを用いて、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割する方法において、
原問題の最適解が得られる可能性を有する、原問題又は部分問題である一の問題を記憶部に記憶し、
記憶部に記憶している前記問題を解くことが困難であるか否かを演算部にて判定し、
前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を演算部にて選択し、
選択した変数を、取り得る複数の値の夫々に固定することにより、演算部にて前記問題を複数の問題に分割して記憶部に記憶する
ことを特徴とする問題分割方法。
【請求項２】
記憶部及び演算部を備えたコンピュータを用いて、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に演算部にて分割して記憶部に記憶し、該部分問題の夫々を演算部にて解くことで前記原問題の最適解を求める最適化方法において、
原問題の暫定解を記憶部に記憶し、
原問題又は部分問題である解くべき一又は複数の問題を記憶部に記憶し、
記憶部に記憶している一又は複数の問題から一の問題を演算部にて選択し、
選択した問題について、該問題を解くことによって原問題の最適解が得られる可能性があるか否かを演算部にて判定し、
原問題の最適解が得られる可能性がないと判定された場合は、前記問題を演算部にて取り扱うことを中止し、
原問題の最適解が得られる可能性があると判定された場合は、前記問題を解くことが困難であるか否かを演算部にて判定し、
前記問題を解くことが困難でないと判定された場合は、所定の解法により前記問題の最適解を演算部にて求め、
求めた前記問題の最適解が前記暫定解に比べてより最適化されているか否かを演算部にて判定し、
前記暫定解に比べてより最適化されていると判定されたときは、前記問題の最適解を新たな暫定解として記憶部に記憶し、
前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、演算部にて一の変数を選択し、
選択した変数を、取り得る複数の値の夫々に固定することにより、演算部にて前記問題を複数の問題に分割し、
分割により生成した複数の問題を新たな解くべき問題として記憶部に記憶し、記憶部に記憶している解くべき問題がなくなるまで記憶部及び演算部にて処理を繰り返し、
解くべき問題がなくなったときに記憶部に記憶している暫定解を原問題の最適解として記憶部に記憶する
ことを特徴とする最適化方法。
【請求項３】
一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割する装置において、
原問題の最適解が得られる可能性を有する、原問題又は部分問題である一の問題を記憶する手段と、
記憶している前記問題を解くことが困難であるか否かを判定する困難度判定手段と、
前記問題を解くことが困難であると前記困難度判定手段により判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択する選択手段と、
選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割する手段と
を備えることを特徴とする問題分割装置。
【請求項４】
前記困難度判定手段は、
最適化条件が目的関数の最大化であるか又は最小化であるかに対応した、前記問題の緩和問題の実数最適解から得られる目的関数の上界値又は下界値を求める手段と、
求めた上界値又は下界値が、原問題の最適解が含まれる所定範囲内に入っているか否かを判定する手段と、
前記上界値又は下界値が前記所定範囲内に入っていないと判定された場合は、前記問題を解くことは困難であると判定する手段と
を備えることを特徴とする請求項３に記載の問題分割装置。
【請求項５】
前記選択手段は、
値が固定されていない複数の離散的な変数の夫々について、取り得る複数の値の夫々に前記変数を固定して得られる複数の問題の緩和問題の夫々を解いた実数最適解の夫々から得られる目的関数の複数の実数最適値を求める手段と、
前記変数の夫々について、求めた複数の実数最適値の最小値と最大値との差を求める手段と、
複数の前記変数のうち、求めた前記差の値が最小である変数を選択する手段と
を備えることを特徴とする請求項３又は４に記載の問題分割装置。
【請求項６】
一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割し、該部分問題の夫々を解くことで前記原問題の最適解を求める最適化装置において、
原問題の暫定解を記憶する手段と、
原問題又は部分問題である解くべき一又は複数の問題を記憶する手段と、
記憶している一又は複数の問題から一の問題を選択する手段と、
選択した問題について、該問題を解くことによって原問題の最適解が得られる可能性があるか否かを判定する手段と、
原問題の最適解が得られる可能性がないと判定された場合は、前記問題を終端する手段と、
原問題の最適解が得られる可能性があると判定された場合は、前記問題を解くことが困難であるか否かを判定する困難度判定手段と、
前記問題を解くことが困難でないと前記困難度判定手段により判定された場合は、所定の解法により前記問題の最適解を求める手段と、
求めた前記問題の最適解が前記暫定解に比べてより最適化されているか否かを判定する手段と、
前記暫定解に比べてより最適化されていると判定されたときは、前記問題の最適解を新たな暫定解として記憶する手段と、
前記問題を解くことが困難であると前記困難度判定手段により判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択する選択手段と、
選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割する手段と、
分割により生成した複数の問題を新たな解くべき問題として記憶する手段と、
解くべき問題がなくなるまで処理を繰り返す手段と、
解くべき問題がなくなったときに記憶している暫定解を原問題の最適解とする手段と
を備えることを特徴とする最適化装置。
【請求項７】
コンピュータに、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解かせる際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割させるコンピュータプログラムにおいて、
コンピュータに、原問題の最適解が得られる可能性を有する、原問題又は部分問題である記憶している一の問題を解くことが困難であるか否かを判定させる困難度判定手順と、
コンピュータに、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択させる選択手順と、
コンピュータに、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割させる手順と
を含むことを特徴とするコンピュータプログラム。
【請求項８】
前記困難度判定手順は、
コンピュータに、最適化条件が目的関数の最大化であるか又は最小化であるかに対応した、前記問題の緩和問題の実数最適解から得られる目的関数の上界値又は下界値を求めさせる手順と、
コンピュータに、求めた上界値又は下界値が、原問題の最適解が含まれる所定範囲内に入っているか否かを判定させる手順と、
コンピュータに、前記上界値又は下界値が前記所定範囲内に入っていないと判定された場合は、前記問題を解くことは困難であると判定させる手順と
を含むことを特徴とする請求項７に記載のコンピュータプログラム。
【請求項９】
前記選択手順は、
コンピュータに、値が固定されていない複数の離散的な変数の夫々について、取り得る複数の値の夫々に前記変数を固定して得られる複数の問題の緩和問題の夫々を解いた実数最適解の夫々から得られる目的関数の複数の実数最適値を求めさせる手順と、
コンピュータに、前記変数の夫々について、求めた複数の実数最適値の最小値と最大値との差を求めさせる手順と、
コンピュータに、複数の前記変数のうち、求めた前記差の値が最小である変数を選択させる手順と
を含むことを特徴とする請求項７又は８に記載のコンピュータプログラム。
【請求項１０】
コンピュータに、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解かせる際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割し、該部分問題の夫々を解くことで前記原問題の最適解を求めさせるコンピュータプログラムにおいて、
コンピュータに、原問題又は部分問題である、記憶している一又は複数の問題から一の問題を選択させる手順と、
コンピュータに、選択した問題について、該問題を解くことによって原問題の最適解が得られる可能性があるか否かを判定させる手順と、
コンピュータに、原問題の最適解が得られる可能性がないと判定された場合は、前記問題を終端させる手順と、
コンピュータに、原問題の最適解が得られる可能性があると判定された場合は、前記問題を解くことが困難であるか否かを判定させる困難度判定手順と、
コンピュータに、前記問題を解くことが困難でないと判定された場合は、所定の解法により前記問題の最適解を求めさせる手順と、
コンピュータに、求めた前記問題の最適解が記憶している暫定解に比べてより最適化されているか否かを判定させる手順と、
コンピュータに、前記暫定解に比べてより最適化されていると判定されたときは、前記問題の最適解を新たな暫定解として記憶させる手順と、
コンピュータに、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択させる選択手順と、
コンピュータに、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割させる手順と、
コンピュータに、分割により生成した複数の問題を新たな解くべき問題として記憶させる手順と、
コンピュータに、解くべき問題がなくなるまで処理を繰り返させる手順と、
コンピュータに、解くべき問題がなくなったときに記憶している暫定解を原問題の最適解とさせる手順と
を含むことを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ナップサック問題を代表とする離散最適化問題を解くために、一の問題を複数の部分問題に分割する問題分割方法、問題分割装置、前記問題分割方法を用いて離散最適化問題を解く最適化方法、最適化装置、及びコンピュータを前記問題分割装置または前記最適化装置として実現するためのコンピュータプログラムに関する。
【０００２】
【従来の技術】
離散最適化問題とは、整数などの離散的な変数の組み合わせの中から、所定の制約条件の基で最適な組み合わせを求める問題であり、工場の作業時間を短くする作業のスケジューリング又は回路の経路長を短くする経路決定などに関して解くことが必要となる。離散最適化問題を厳密に解くためには、可能な組み合わせを逐一列挙していく必要があり、変数の数が多い場合には、組み合わせの数が爆発的に増大して、いわゆる組み合わせの爆発（　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｅｘｐｌｏｓｉｏｎ）を引き起こす。
【０００３】
ナップサック問題（Ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ）は、離散最適化問題の代表的な問題であり、価値および容量が定められた複数種類の品物と容量制限が定められたナップサックとがあるときに、容量の合計が容量制限以下となる品物の組み合わせの中から価値の合計が最大となる組み合わせを求める問題である。ナップサック問題は、計算機を用いて実効的な時間内で解くことが困難であるＮＰ困難（　ＮＰ−ｈａｒｄ）な問題に属し、ナップサック問題を効率的に解こうとする様々な解法が従来より提案されている。
【０００４】
ナップサック問題を効率的に解く代表的な解法として分枝限定法（ｂｒａｎｃｈ　ａｎｄ　ｂｏｕｎｄ　ｍｅｔｈｏｄ　）がある。分枝限定法は、解くべき原問題を複数の部分問題に分割し、解くことが可能な部分問題を順に解くことで原問題を解く解法である。ナップサック問題の例を以下に示す。
【０００５】
【数１】
2004133802.tif 000003
【０００６】
ここで、ａｉ　，ｃｉ　，ｂは正の実数であり、ｃｉ　は品物の価値、ａｉ　は品物の容量、ｂはナップサックの容量制限に夫々対応し、ｘｉ　＝０は品物をナップサックに入れないことに対応し、ｘｉ　＝１は品物をナップサックに入れることに対応しており、目的関数ｆ（Ｘ）の値は価値の合計に対応する。制約条件の基で目的関数ｆ（Ｘ）の値を最大にするＸの最適解を求めることがこの問題の目的である。分枝限定法では、任意のｘｉ　の値を順に０又は１に固定することにより問題を部分問題に分割して、問題を解く。
【０００７】
図６は、分枝限定法の手順を示すフローチャートである。分枝限定法を用いて計算を行う計算機は、まず、近似解法を用いて求めた暫定解、及び該暫定解をｆ（Ｘ）に代入して得られる目的関数の暫定値を記憶し（Ｓ００１）、原問題を解くべき問題として記憶する（Ｓ００２）。計算機は、記憶している問題の中から一の問題を選択し（Ｓ００３）、選択した問題に実行可能解が存在するか否かを判定する（Ｓ００４）。例えば、制約条件の式において、任意のｘｉ　の値を固定したことにより定数となった項の合計がｂより大きい場合は、明らかに、選択した問題には実行可能解は存在しない。実行可能解が存在しないと判定された場合（Ｓ００４：ＮＯ）は、明らかに、選択している問題を解く必要がないため、計算機は、処理をステップＳ００９へ進め、選択している問題を解くべき対象から除外（以下、問題の終端という）する（Ｓ００９）。実行可能解が存在すると判定された場合（Ｓ００４：ＹＥＳ）、計算機は、選択している問題の緩和問題を解くことで、Ｘの実数最適解、及び該実数最適解をｆ（Ｘ）に代入して得られる目的関数の上界値を計算する（Ｓ００５）。緩和問題とは、固定されていないｘｉ　（以下、活性変数と言う）の整数条件を緩和し、ｘｉ　が０≦ｘｉ　≦１の範囲の実数であるとして、目的関数を最大にするＸを求める問題であり、ｃｉ　／ａｉ　の値が大きいｉの順に、活性変数の値を制約条件が満たされる限りできるだけ大きい値に定めることにより、実数からなるＸの最適解である実数最適解が容易に求められる。実数最適解を目的関数へ代入して得られる値は、緩和問題における目的関数の最大値であり、選択している問題における目的関数の最大値に比べて、より大きいか又は等しいため、選択している問題における目的関数の上界値となる。計算機は、次に、計算した上界値が記憶している暫定値より大きい値であるか否かを判定し（Ｓ００６）、上界値が暫定値以下の値である場合は（Ｓ００６：ＮＯ）、選択している問題には暫定値よりも良い解が存在しないため、処理をステップＳ００９へ進めて問題を終端する（Ｓ００９）。ステップＳ００４〜Ｓ００６における、解く必要がない問題を除外する操作を、限定操作（ｂｏｕｎｄｉｎｇ　ｏｐｅｒａｔｉｏｎ）と言う。
【０００８】
上界値が暫定値より大きい値である場合は（Ｓ００６：ＹＥＳ）、計算機は、実数最適解は整数解であるか否かを判定し（Ｓ００７）、実数最適解が整数解であった場合は（Ｓ００７：ＹＥＳ）、該実数最適解は、選択している問題の最適解になっており、しかも該最適解は暫定値よりも大きい目的関数の値を与えるため、選択している問題の最適解、及び該最適解を目的関数へ代入して得られる最適値を、新たな暫定解および暫定値として記憶し（Ｓ００８）、選択している問題を終端する（Ｓ００９）。
【０００９】
ステップＳ００７にて実数最適解が整数解ではない場合は（Ｓ００７：ＮＯ）、計算機は、最後に実数値を定めた活性変数の値を小さくして整数の値にする等の操作により、明らかな最適解が求まるか否かを判定し（Ｓ０１０）、明らかな最適解が求まった場合は（Ｓ０１０：ＹＥＳ）、求まった最適解を目的関数に代入して得られる目的関数の値が暫定値より大きいか否かを判定し（Ｓ０１１）、前記目的関数の値が暫定値より大きい場合は（Ｓ０１１：ＹＥＳ）、ステップＳ００８へ処理を進めて最適解および最適値を新たな暫定解および暫定値として記憶する。ステップＳ０１０にて明らかな最適解が求まらない場合（Ｓ０１０：ＮＯ）、又はステップＳ０１１にて前記目的関数の値が暫定値以下であった場合は（Ｓ０１１：ＮＯ）、計算機は、活性変数の中から一のｘｉ　を選んで、選んだｘｉ　の値を０又は１に固定することで、選択している問題を二つの問題に分割し（Ｓ０１２）、処理をステップＳ００２へ戻し、分割により生成した問題を解くべき問題として記憶する。ステップＳ０１２における、問題を分割する操作を、分枝操作（　ｂｒａｎｃｈｉｎｇ　ｏｐｅｒａｔｉｏｎ）と言う。
【００１０】
ステップＳ００９にて問題を終端させた後は、計算機は、他の解くべき問題を記憶しているか否かを判定し（Ｓ０１３）、他の解くべき問題を記憶している場合は（Ｓ０１３：ＹＥＳ）、ステップＳ００３へ処理を戻して新たな問題を選択し、他の解くべき問題を記憶していない場合は（Ｓ０１３：ＮＯ）、処理を終了する。処理を終了したときに記憶している暫定解が、原問題の最適解である。
【００１１】
図７は、分枝限定法の概要を示す概念図である。図中に示す白丸は問題を示し、黒丸は終端された問題を示す。原問題は、分枝操作により、ｘ１　が０又は１に固定された二つの部分問題に分割され、更に、夫々の問題は、ｘ２　が０又は１に固定された二つの部分問題に分割される。（ｘ１　，ｘ２　）＝（０，０）の部分問題は、限定操作により終端され、（ｘ１　，ｘ２　）＝（０，１）の部分問題が更に分割される。以上の如く、分枝限定法においては、分枝操作により問題を分割し、最適解を含まない問題を限定操作により終端することにより、無駄な計算を行わずに効率的に最適解を求めることができる。
【００１２】
ナップサック問題において、制約条件が複数である場合を多次元ナップサック問題と言い、各変数が非線形で関連づけられている場合を非線形ナップサック問題と言う。多次元非線形ナップサック問題（ｍｕｌｔｉ−ｄｉｍｅｎｓｉｏｎａｌ　ｎｏｎｌｉｎｅａｒ　ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ：ＭＮＫ問題）は、離散最適化問題の一般形であり、以下の如く表現される。
【００１３】
【数２】
2004133802.tif 000004
【００１４】
ここで、ｘｉ　はｋｉ　通りの値をとりうる整数である。目的関数の最小化を最適化の条件とすることにより、ＭＮＫ問題は、値の最小化を最適化の条件とする離散最適化問題についても対応することができる。
【００１５】
ＭＮＫ問題は、単純なナップサック問題に比べて解くことは格段に困難となる。本発明者は、過去３０年間に渡ってＭＮＫ問題の解法を研究しており、１９８４年に解法の一つである代理制約法（ｓｕｒｒｏｇａｔｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｍｅｔｈｏｄ）を開発している。また、１９９０年に提案した解法であるモジュラ法を用いて単一制約の非線形ナップサック問題を解くアルゴリズムを提案している（非特許文献１を参照）。更に、本発明者は、代理制約法を改良して、より多くの変数を含むＭＮＫ問題を厳密に解くことが可能な改良代理制約法（　ｉｍｐｒｏｖｅｄ　ｓｕｒｒｏｇａｔｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｍｅｔｈｏｄ；以下、ＩＳＣ法と言う）を開発した。ＩＳＣ法を用いて離散最適化問題を解くコンピュータプログラムは、解法の性能をテストするためのテスト問題の一種について、線形の離散最適化問題を解くための商用の最高速のコンピュータプログラムに比べて平均５倍以上の早さで問題を解けることが確かめられている。この開発成果は、Ｊｏｕｒｎａｌ　ｏｆ　ｔｈｅ　ｏｐｅｒａｔｉｏｎ　ｏｆ　ｒｅｓｅａｒｃｈ　ｏｆ　Ｊａｐａｎ　に掲載予定のＮａｋａｇａｗａ　Ｙ．　：Ａｎ　ｉｍｐｒｏｖｅｄ　ｓｕｒｒｏｇａｔｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｍｅｔｈｏｄ　ｆｏｒ　ｓｅｐａｒａｂｌｅ　ｎｏｎｌｉｎｅａｒ　ｉｎｔｅｇｅｒ　ｐｒｏｇｒａｍｍｉｎｇ．に開示されている。
【００１６】
【非特許文献１】
仲川（Ｙ．　Ｎａｋａｇａｗａ）・イワサキ（Ｉ．　Ｉｗａｓａｋｉ）「モジュラ　アプローチ　フォア　ソルビング　ノンリニア　ナップサック　プロブレム（Ｍｏｄｕｌａｒ　Ａｐｐｒｏａｃｈ　ｆｏｒ　Ｓｏｌｖｉｎｇ　Ｎｏｎｌｉｎｅａｒ　Ｋｎａｐｓａｃｋ　Ｐｒｏｂｌｅｍ）」，電子情報通信学会英文論文誌（ＩＥＩＣＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｆｕｎｄａｍｅｎｔａｌｓ），１９９９年，Ｅ８２−Ａ，ｐ．１８６０−１８６４
【００１７】
【発明が解決しようとする課題】
本発明者が開発したモジュラ法又はＩＳＣ法を用いることにより、解の組み合わせの数が１０の１０００乗個の規模となるＭＮＫ問題を厳密に解くことが可能となっている。しかし、問題を解くことの困難さは、解の組み合わせの数のみに依存するものではなく、モジュラ法又はＩＳＣ法を用いて解くことが困難である問題が未だ存在する。また、従来の分枝限定法は、変数の数および該変数がとりうる値の数が多い場合には、組み合わせの爆発を引き起こし、更に、原問題を分割した後に解くことが困難である問題が残り、最終的に原問題が解けなくなる場合がある。
【００１８】
本発明は、斯かる事情に鑑みてなされたものであって、その目的とするところは、問題を分割する際に、問題を解くことの困難さを判定して、解くことが困難である問題から分割を行うことにより、解くことが容易な問題に原問題を分割する問題分割方法、問題分割装置、及びコンピュータを該問題分割装置として実現するためのコンピュータプログラムを提供することにある。
【００１９】
また、本発明の他の目的とするところは、問題を解くことが困難でないと判定した問題を適宜の解法で解くことにより、離散最適化問題を解く最適化方法、最適化装置、及びコンピュータを該最適化装置として実現するためのコンピュータプログラムを提供することにある。
【００２０】
【課題を解決するための手段】
第１発明に係る問題分割方法は、記憶部及び演算部を備えたコンピュータを用いて、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割する方法において、原問題の最適解が得られる可能性を有する、原問題又は部分問題である一の問題を記憶部に記憶し、記憶部に記憶している前記問題を解くことが困難であるか否かを演算部にて判定し、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を演算部にて選択し、選択した変数を、取り得る複数の値の夫々に固定することにより、演算部にて前記問題を複数の問題に分割して記憶部に記憶することを特徴とする。
【００２１】
第２発明に係る最適化方法は、記憶部及び演算部を備えたコンピュータを用いて、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に演算部にて分割して記憶部に記憶し、該部分問題の夫々を演算部にて解くことで前記原問題の最適解を求める最適化方法において、原問題の暫定解を記憶部に記憶し、原問題又は部分問題である解くべき一又は複数の問題を記憶部に記憶し、記憶部に記憶している一又は複数の問題から一の問題を演算部にて選択し、選択した問題について、該問題を解くことによって原問題の最適解が得られる可能性があるか否かを演算部にて判定し、原問題の最適解が得られる可能性がないと判定された場合は、前記問題を演算部にて取り扱うことを中止し、原問題の最適解が得られる可能性があると判定された場合は、前記問題を解くことが困難であるか否かを演算部にて判定し、前記問題を解くことが困難でないと判定された場合は、所定の解法により前記問題の最適解を演算部にて求め、求めた前記問題の最適解が前記暫定解に比べてより最適化されているか否かを演算部にて判定し、前記暫定解に比べてより最適化されていると判定されたときは、前記問題の最適解を新たな暫定解として記憶部に記憶し、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、演算部にて一の変数を選択し、選択した変数を、取り得る複数の値の夫々に固定することにより、演算部にて前記問題を複数の問題に分割し、分割により生成した複数の問題を新たな解くべき問題として記憶部に記憶し、記憶部に記憶している解くべき問題がなくなるまで記憶部及び演算部にて処理を繰り返し、解くべき問題がなくなったときに記憶部に記憶している暫定解を原問題の最適解として記憶部に記憶することを特徴とする。
【００２２】
第３発明に係る問題分割装置は、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割する装置において、原問題の最適解が得られる可能性を有する、原問題又は部分問題である一の問題を記憶する手段と、記憶している前記問題を解くことが困難であるか否かを判定する困難度判定手段と、前記問題を解くことが困難であると前記困難度判定手段により判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択する選択手段と、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割する手段とを備えることを特徴とする。
【００２３】
第４発明に係る問題分割装置は、前記困難度判定手段は、最適化条件が目的関数の最大化であるか又は最小化であるかに対応した、前記問題の緩和問題の実数最適解から得られる目的関数の上界値又は下界値を求める手段と、求めた上界値又は下界値が、原問題の最適解が含まれる所定範囲内に入っているか否かを判定する手段と、前記上界値又は下界値が前記所定範囲内に入っていないと判定された場合は、前記問題を解くことは困難であると判定する手段とを備えることを特徴とする。
【００２４】
第５発明に係る問題分割装置は、前記選択手段は、値が固定されていない複数の離散的な変数の夫々について、取り得る複数の値の夫々に前記変数を固定して得られる複数の問題の緩和問題の夫々を解いた実数最適解の夫々から得られる目的関数の複数の実数最適値を求める手段と、前記変数の夫々について、求めた複数の実数最適値の最小値と最大値との差を求める手段と、複数の前記変数のうち、求めた前記差の値が最小である変数を選択する手段とを備えることを特徴とする。
【００２５】
第６発明に係る最適化装置は、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割し、該部分問題の夫々を解くことで前記原問題の最適解を求める最適化装置において、原問題の暫定解を記憶する手段と、原問題又は部分問題である解くべき一又は複数の問題を記憶する手段と、記憶している一又は複数の問題から一の問題を選択する手段と、選択した問題について、該問題を解くことによって原問題の最適解が得られる可能性があるか否かを判定する手段と、原問題の最適解が得られる可能性がないと判定された場合は、前記問題を終端する手段と、原問題の最適解が得られる可能性があると判定された場合は、前記問題を解くことが困難であるか否かを判定する困難度判定手段と、前記問題を解くことが困難でないと前記困難度判定手段により判定された場合は、所定の解法により前記問題の最適解を求める手段と、求めた前記問題の最適解が前記暫定解に比べてより最適化されているか否かを判定する手段と、前記暫定解に比べてより最適化されていると判定されたときは、前記問題の最適解を新たな暫定解として記憶する手段と、前記問題を解くことが困難であると前記困難度判定手段により判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択する選択手段と、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割する手段と、分割により生成した複数の問題を新たな解くべき問題として記憶する手段と、解くべき問題がなくなるまで処理を繰り返す手段と、解くべき問題がなくなったときに記憶している暫定解を原問題の最適解とする手段とを備えることを特徴とする。
【００２６】
第７発明に係るコンピュータプログラムは、コンピュータに、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解かせる際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割させるコンピュータプログラムにおいて、コンピュータに、原問題の最適解が得られる可能性を有する、原問題又は部分問題である記憶している一の問題を解くことが困難であるか否かを判定させる困難度判定手順と、コンピュータに、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択させる選択手順と、コンピュータに、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割させる手順とを含むことを特徴とする。
【００２７】
第８発明に係るコンピュータプログラムは、前記困難度判定手順は、コンピュータに、最適化条件が目的関数の最大化であるか又は最小化であるかに対応した、前記問題の緩和問題の実数最適解から得られる目的関数の上界値又は下界値を求めさせる手順と、コンピュータに、求めた上界値又は下界値が、原問題の最適解が含まれる所定範囲内に入っているか否かを判定させる手順と、コンピュータに、前記上界値又は下界値が前記所定範囲内に入っていないと判定された場合は、前記問題を解くことは困難であると判定させる手順とを含むことを特徴とする。
【００２８】
第９発明に係るコンピュータプログラムは、前記選択手順は、コンピュータに、値が固定されていない複数の離散的な変数の夫々について、取り得る複数の値の夫々に前記変数を固定して得られる複数の問題の緩和問題の夫々を解いた実数最適解の夫々から得られる目的関数の複数の実数最適値を求めさせる手順と、コンピュータに、前記変数の夫々について、求めた複数の実数最適値の最小値と最大値との差を求めさせる手順と、コンピュータに、複数の前記変数のうち、求めた前記差の値が最小である変数を選択させる手順とを含むことを特徴とする。
【００２９】
第１０発明に係るコンピュータプログラムは、コンピュータに、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解かせる際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割し、該部分問題の夫々を解くことで前記原問題の最適解を求めさせるコンピュータプログラムにおいて、コンピュータに、原問題又は部分問題である、記憶している一又は複数の問題から一の問題を選択させる手順と、コンピュータに、選択した問題について、該問題を解くことによって原問題の最適解が得られる可能性があるか否かを判定させる手順と、コンピュータに、原問題の最適解が得られる可能性がないと判定された場合は、前記問題を終端させる手順と、コンピュータに、原問題の最適解が得られる可能性があると判定された場合は、前記問題を解くことが困難であるか否かを判定させる困難度判定手順と、コンピュータに、前記問題を解くことが困難でないと判定された場合は、所定の解法により前記問題の最適解を求めさせる手順と、コンピュータに、求めた前記問題の最適解が記憶している暫定解に比べてより最適化されているか否かを判定させる手順と、コンピュータに、前記暫定解に比べてより最適化されていると判定されたときは、前記問題の最適解を新たな暫定解として記憶させる手順と、コンピュータに、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択させる選択手順と、コンピュータに、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割させる手順と、コンピュータに、分割により生成した複数の問題を新たな解くべき問題として記憶させる手順と、コンピュータに、解くべき問題がなくなるまで処理を繰り返させる手順と、コンピュータに、解くべき問題がなくなったときに記憶している暫定解を原問題の最適解とさせる手順とを含むことを特徴とする。
【００３０】
第１、第３及び第７発明においては、離散最適化問題を分割する際に、問題を解くことの困難さを判定して、解くことが困難である問題から分割を行うことにより、解くことが容易な問題に原問題を分割する。
【００３１】
第４及び第８発明においては、分割すべき問題の緩和問題より、前記問題から得られる可能性のある解の限界を求め、原問題の最適解を含む所定範囲内に前記限界が入っていない問題を、解くことが困難である問題であると判定することにより、可能な解の中から最適解を探索すべき範囲が広いために解くことが困難である問題を分割する。
【００３２】
第５及び第９発明においては、問題を分割するために固定する活性変数を選択する際、取りうる値の夫々に活性変数のいずれかの値を固定した緩和問題から得られる目的関数の実数最適値について、値を変えたときに得られる実数最適値の最小値と最大値との差が最も小さくなる活性変数を選ぶことにより、目的関数の値の変化が小さく、値を変えて最適値を探索することが困難な活性変数を固定して、解くことが容易な問題に分割する。
【００３３】
第２、第６、及び第１０発明においては、解くことが困難な問題を分割し、困難でない問題を解くことにより、効率的に離散最適化問題を解くことができる。
【００３４】
【発明の実施の形態】
以下本発明をその実施の形態を示す図面に基づき具体的に説明する。
【００３５】
図１は、本発明の問題分割装置の構成を示すブロック図である。問題分割装置１は、本発明に係る最適化装置の機能を兼ね備えており、コンピュータを用いて構成されている。問題分割装置１は、本発明に係る演算部であり、演算を行うＣＰＵ１１と、本発明に係る記憶部であり、演算に伴って発生する一時的な情報を記憶するＲＡＭ１２と、ＣＤ−ＲＯＭドライブ等の外部記憶装置１３と、ハードディスク等の内部記憶装置１４とを備えており、ＣＤ−ＲＯＭ等の記録媒体２から本発明に係るコンピュータプログラム２０を外部記憶装置１３にて読み取り、読み取ったコンピュータプログラム２０を内部記憶装置１４に記憶し、ＲＡＭ１２にコンピュータプログラム２０をロードし、ロードしたコンピュータプログラム２０に基づいて問題分割装置１に必要な処理を実行する。問題分割装置１は、キーボード又はマウス等の入力装置１５と、液晶ディスプレイ又はＣＲＴディスプレイ等の出力装置１６とを備えており、データの入力を初めとするオペレータからの操作を受け付ける構成となっている。
【００３６】
また、問題分割装置１は、図示しない通信インタフェースを備え、該通信インタフェースに接続している図示しないサーバ装置から本発明に係るコンピュータプログラム２０をダウンロードし、ＣＰＵ１１にて処理を実行する形態であってもよい。
【００３７】
次に、離散最適化問題のテスト問題の例を参照しながら本発明の問題分割方法および最適化方法を説明する。参照するテスト問題を以下に示す。
【００３８】
【数３】
2004133802.tif 000005
【００３９】
この問題は、５個の制約条件の基で、０〜５の６種類の整数の値を取り得る３９変数の最適な組み合わせを求める多次元ナップサック問題である。図２は、テスト問題のパラメータを示す図表である。目的関数を構成する３９個のｃｉ　の値、及び制約条件の式を構成する５×３９のａｊｉの値は、図２に示している通りである。
【００４０】
図３は、本発明の問題分割装置が行う本発明の問題分割方法および最適化方法の処理の手順を示すフローチャートである。問題分割装置１のＣＰＵ１１は、コンピュータプログラム２０をＲＡＭ１２へロードし、ロードしたコンピュータプログラム２０に従って、近似解法を用いて求めた原問題の暫定解、該暫定解を目的関数に代入して得られる値である暫定値、及び問題を解く困難度を判定する基準となる判定基準値を入力装置１５にてオペレータの操作により受け付けて、ＲＡＭ１２に記憶する（Ｓ１）。判定基準値は、暫定値よりもある程度大きい値に定めておく。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、原問題を解くべき問題として記憶する（Ｓ２）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、記憶している一又は複数の問題の中から一の問題を選択する（Ｓ３）。このとき、ＣＰＵ１１は、活性変数の数が少ない問題を優先（以下、深さ優先：ｄｅｐｔｈ　ｆｉｒｓｔ　と言う）して問題を選択する、又は活性変数の数が多い問題を優先（以下、幅優先：ｂｒｅａｄｔｈ　ｆｉｒｓｔ　と言う）して問題を選択する等、様々な方法で問題を選択する。深さ優先を用いた場合は、ＲＡＭ１２に記憶する活性変数の数が少なくなるため、ＲＡＭ１２の容量を節約した計算を行うことができる。幅優先を用いた場合は、最終的に解くべき問題の数が少なくなるために、計算時間を短くすることができる。
【００４１】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択した問題に実行可能解が存在するか否かを判定し（Ｓ４）、実行可能解が存在しない場合は（Ｓ４：ＮＯ）、処理をステップＳ１４へ進め、選択している問題を終端する（Ｓ１４）。実行可能解が存在する場合は（Ｓ４：ＹＥＳ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択している問題の緩和問題を解くことで、実数最適解、及び該実数最適解を目的関数に代入して得られる目的関数の上界値を計算する（Ｓ５）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、計算した上界値が、記憶している暫定値より大きい値であるか否かを判定し（Ｓ６）、上界値が暫定値以下の値である場合は（Ｓ６：ＮＯ）、選択している問題には暫定値よりも良い解が存在しないため、処理をステップＳ１４へ進めて問題を終端する（Ｓ１４）。
【００４２】
上界値が暫定値より大きい値である場合は（Ｓ６：ＹＥＳ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択している問題を解くことが困難であるか否かを判定する困難度判定処理を行う（Ｓ７）。図４は、ステップＳ７の困難度判定処理のサブルーチンを示すフローチャートである。ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、上界値が、記憶している判定基準値より大きいか否かを判定し（Ｓ７１）、上界値が判定基準値より大きい場合は（Ｓ７１：ＹＥＳ）、選択している問題は、解を探索する範囲が広いために、解くことが困難であると判定し（Ｓ７２）、処理をメインの処理へ戻す。上界値が判定基準値以下である場合は（Ｓ７１：ＮＯ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択している問題は、解くことが困難でないと判定し（Ｓ７３）、処理をメインの処理へ戻す。なお、困難度判定処理は、選択している問題の最適解を推定した値を目的関数に代入した値と上界値との値の差を用いる等、他の方法を用いて困難度の判定を行っても良い。
【００４３】
困難度判定処理にて、選択している問題を解くことが困難であると判定された場合は（Ｓ８：ＹＥＳ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択した問題が含んでいる複数の活性変数から一の活性変数を選択する選択処理を行う（Ｓ９）。図５は、ステップＳ９の選択処理のサブルーチンを示すフローチャートである。ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、複数の活性変数の中から、一の活性変数を選択し（Ｓ９１）、選択した活性変数を、取りうる各値に固定したときの、目的関数の上界値を計算し（Ｓ９２）、前記活性変数の値を変化させることにより変化する前記上界値の最大値と最小値との差の値を計算する（Ｓ９３）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、全ての活性変数について前記差の値を計算したか否かを判定し（Ｓ９４）、全てを計算していない場合は（Ｓ９４：ＮＯ）、ステップＳ９１へ処理を戻して次の活性変数を選択し、全ての活性変数について前記差の値を計算している場合は（Ｓ９４：ＹＥＳ）、前記差の値が最小となる活性変数を選択し（Ｓ９５）、処理をメインの処理へ戻す。この選択処理により、目的関数の値の変化が小さく、活性変数の値を変えて最適値を探索することが困難な問題を分割することができる。なお、計算した上界値が小さくなる活性変数を選択する等、他の方法を用いて活性変数の選択を行ってもよい。
【００４４】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択処理により選択した活性変数を、取りうる夫々の値に固定することにより、選択している問題を前記値の種類の数の問題に分割して、複数の問題を生成し（Ｓ１０）、処理をステップＳ２へ戻して、生成した複数の問題を、解くべき問題としてＲＡＭ１２に記憶する。テスト問題の場合は、選択している問題が、選択された活性変数ｘｉ　の値が０〜５の６通りの整数のいずれかに固定された６個の問題に分割されて、記憶される。
【００４５】
困難度判定処理にて、選択している問題を解くことが困難ではないと判定された場合は（Ｓ８：ＮＯ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択している問題を、モジュラ法またはＩＳＣ法などの解法を用いて解いて、選択している問題の最適解を計算し（Ｓ１１）、計算した最適解を代入した目的関数の値が暫定値よりも大きいか否かを判定する（Ｓ１２）。前記目的関数の値が暫定値以下であった場合は（Ｓ１２：ＮＯ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、処理をステップＳ１４へ進めて問題を終端し（Ｓ１４）、前記目的関数の値が暫定値よりも大きい場合は（Ｓ１２：ＹＥＳ）、前記最適解、及び前記目的関数の値を、新たな暫定解および暫定値としてＲＡＭ１２に記憶し（Ｓ１３）、選択している問題を終端する（Ｓ１４）。
【００４６】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ＲＡＭ１２が他の解くべき問題を記憶しているか否かを判定し（Ｓ１５）、他の解くべき問題を記憶している場合は（Ｓ１５：ＹＥＳ）、ステップＳ３へ処理を戻して新たな問題を選択し、ＲＡＭ１２が他の解くべき問題を記憶していない場合は（Ｓ１５：ＮＯ）、ＲＡＭ１２に記憶している暫定解を、原問題の最適解として出力し（Ｓ１６）、処理を終了する。
【００４７】
以上の処理に従って、最初の暫定値を１４３３２、及び判定基準値を１４３５３として、テスト問題を解く計算を行った。ＩＳＣ法を用いて同一の問題を解いた場合は、２２０秒以上の計算時間で厳密な解が求められなかったことに比べて、本発明では、３７秒で厳密な解を得ることができた。得られた最適解は、（０００００３００００　００５３５１５０５５　００００５０３０５５　３５０００４０３０）であり、最大化された目的関数の値は、１４３３３である。
【００４８】
以上詳述した如く、本発明においては、離散最適化問題を解く際に、問題を解くことの困難度を判定し、解くことが困難である問題を、解くことがより容易である問題に分割し、解くことが困難でない問題をモジュラ法またはＩＳＣ法などの解法で解くことにより、効率的に問題を解き、従来では解くことができなかった問題を解くことが可能になり、また、従来よりも短い時間、小さいメモリ容量で離散最適化問題を解くことができる。様々な離散最適化問題を高速かつ厳密に解くことができるため、倉庫における最適な物品の管理方法、作業のスケジューリング、運送機器への運送すべき物品の割り当て、及び設備の配置など、社会活動における様々な問題に適用して、社会活動の効率化を図ることができる。
【００４９】
なお、本実施の形態においては、目的関数の最大化を最適化条件としている問題例を示したが、目的関数の最小化を最適化条件としている問題についても、前述の処理で用いた上界値の代わりに目的関数の下界値を用いて、下界値が暫定値以上である問題を終端する等、下界値を各種の判定の基準に用いることにより、同様の処理を用いて解くことができる。また、目的関数および制約条件が線形関数である問題例を示したが、非線形関数を用いた問題であっても解くことができるのは、もちろんであり、一般的な離散最適化問題に適用することができる。
【００５０】
また、本実施の形態においては、最適化装置の機能を兼ね備えた本発明の問題分割装置１は、一のＣＰＵ１１を備えた一のコンピュータを用いて構成してある形態を示したが、これに限る物ではなく、複数のＣＰＵ１１，１１，…を備えたコンピュータを用いて構成した形態であってもよく、また、夫々がＣＰＵを備えた複数のコンピュータを互いに接続させて構成した形態であってもよい。本発明は、この場合の如く複数のＣＰＵ又は複数のコンピュータを用いて構成される並列計算機についても適用可能であり、原問題を分割した複数の問題の夫々を複数のＣＰＵ又は複数のコンピュータの夫々にて独立に解くことにより、本発明を用いた並列計算を行って、より高速に離散最適化問題を解くことができる。
【００５１】
更に、本実施の形態においては、本発明の問題分割装置１は、本発明の最適化装置の機能を兼ね備えている形態を示したが、これに限るものではなく、問題分割装置１と、モジュラ法またはＩＳＣ法などを用いて問題を解く装置とを夫々別のコンピュータにて構成し、互いにデータを入出力することにより本発明の最適化装置を構成する形態としてもよい。
【００５２】
【発明の効果】
第１、第３、及び第７発明においては、離散最適化問題を分割する際に、問題を解くことの困難さを判定して、解くことが困難である問題から分割を行うことにより、解くことが容易な問題に原問題を分割することができる。
【００５３】
第４及び第８発明においては、分割すべき問題の緩和問題より、前記問題から得られる可能性のある解の限界を求め、原問題の最適解を含む所定範囲内に前記限界が入っていない問題を、解くことが困難である問題であると判定することにより、可能な解の中から最適解を探索すべき範囲が広いために解くことが困難である問題を分割することができる。
【００５４】
第５及び第９発明においては、問題を分割するために固定する活性変数を選択する際、取りうる値の夫々に活性変数のいずれかの値を固定した緩和問題から得られる目的関数の実数最適値について、値を変えたときに得られる実数最適値の最小値と最大値との差が最も小さくなる活性変数を選ぶことにより、目的関数の値の変化が小さく、活性変数の値を変えて最適値を探索することが困難な問題を分割することができる。
【００５５】
第２、第６、及び第１０発明においては、解くことが困難な問題を分割し、困難でない問題を解くことにより、効率的に離散最適化問題を解くことができる。また、一般的な離散最適化問題を高速かつ厳密に解くことができるため、倉庫における最適な物品の管理方法、作業のスケジューリング、運送機器への運送すべき物品の割り当て、及び設備の配置など、社会活動における様々な問題に適用して、社会活動の効率化を図ることができる等、本発明は優れた効果を奏する。
【図面の簡単な説明】
【図１】本発明の問題分割装置の構成を示すブロック図である。
【図２】テスト問題のパラメータを示す図表である。
【図３】本発明の問題分割装置が行う本発明の問題分割方法および最適化方法の処理の手順を示すフローチャートである。
【図４】ステップＳ７の困難度判定処理のサブルーチンを示すフローチャートである。
【図５】ステップＳ９の選択処理のサブルーチンを示すフローチャートである。
【図６】分枝限定法の手順を示すフローチャートである。
【図７】分枝限定法の概要を示す概念図である。
【符号の説明】
１　問題分割装置
１１　ＣＰＵ（演算部）
１２　ＲＡＭ（記憶部）
２　記録媒体
２０　コンピュータプログラム
【図１】
2004133802.tif 000006
【図２】
2004133802.tif 000007
【図３】
2004133802.tif 000008
【図４】
2004133802.tif 000009
【図５】
2004133802.tif 000010
【図６】
2004133802.tif 000011
【図７】
2004133802.tif 000012