JP2004133802A - Problem dividing method, optimization method, problem dividing device, optimization device, and computer program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a problem dividing method and a problem dividing device which effectively divide a discrete optimization problem, an optimization method and an optimization device which effectively solve the discrete optimization problem, and a computer program. <P>SOLUTION: A plurality of problems, which divides an original problem, are stored(S2), one of the stored problems is selected (S3), and it is determined whether the selected problem is difficult to be solved or not (S7). If it is difficult to solve, one active variable is selected (S9), value of the selected active variable is fixed to each of possible value, and the selected problem is divided into a plurality of problems (S10). If it is not difficult to solve, the selected problem is solved and an optimum solution is found (S11). The solution, which is most optimized among the founded optimum solutions, is the optimum solution of the original problem. <P>COPYRIGHT: (C)2004,JPO

Description

【０００６】
ここで、ａ_ｉ　，ｃ_ｉ　，ｂは正の実数であり、ｃ_ｉ　は品物の価値、ａ_ｉ　は品物の容量、ｂはナップサックの容量制限に夫々対応し、ｘ_ｉ　＝０は品物をナップサックに入れないことに対応し、ｘ_ｉ　＝１は品物をナップサックに入れることに対応しており、目的関数ｆ（Ｘ）の値は価値の合計に対応する。制約条件の基で目的関数ｆ（Ｘ）の値を最大にするＸの最適解を求めることがこの問題の目的である。分枝限定法では、任意のｘ_ｉ　の値を順に０又は１に固定することにより問題を部分問題に分割して、問題を解く。
【０００７】
図６は、分枝限定法の手順を示すフローチャートである。分枝限定法を用いて計算を行う計算機は、まず、近似解法を用いて求めた暫定解、及び該暫定解をｆ（Ｘ）に代入して得られる目的関数の暫定値を記憶し（Ｓ００１）、原問題を解くべき問題として記憶する（Ｓ００２）。計算機は、記憶している問題の中から一の問題を選択し（Ｓ００３）、選択した問題に実行可能解が存在するか否かを判定する（Ｓ００４）。例えば、制約条件の式において、任意のｘ_ｉ　の値を固定したことにより定数となった項の合計がｂより大きい場合は、明らかに、選択した問題には実行可能解は存在しない。実行可能解が存在しないと判定された場合（Ｓ００４：ＮＯ）は、明らかに、選択している問題を解く必要がないため、計算機は、処理をステップＳ００９へ進め、選択している問題を解くべき対象から除外（以下、問題の終端という）する（Ｓ００９）。実行可能解が存在すると判定された場合（Ｓ００４：ＹＥＳ）、計算機は、選択している問題の緩和問題を解くことで、Ｘの実数最適解、及び該実数最適解をｆ（Ｘ）に代入して得られる目的関数の上界値を計算する（Ｓ００５）。緩和問題とは、固定されていないｘ_ｉ　（以下、活性変数と言う）の整数条件を緩和し、ｘ_ｉ　が０≦ｘ_ｉ　≦１の範囲の実数であるとして、目的関数を最大にするＸを求める問題であり、ｃ_ｉ　／ａ_ｉ　の値が大きいｉの順に、活性変数の値を制約条件が満たされる限りできるだけ大きい値に定めることにより、実数からなるＸの最適解である実数最適解が容易に求められる。実数最適解を目的関数へ代入して得られる値は、緩和問題における目的関数の最大値であり、選択している問題における目的関数の最大値に比べて、より大きいか又は等しいため、選択している問題における目的関数の上界値となる。計算機は、次に、計算した上界値が記憶している暫定値より大きい値であるか否かを判定し（Ｓ００６）、上界値が暫定値以下の値である場合は（Ｓ００６：ＮＯ）、選択している問題には暫定値よりも良い解が存在しないため、処理をステップＳ００９へ進めて問題を終端する（Ｓ００９）。ステップＳ００４〜Ｓ００６における、解く必要がない問題を除外する操作を、限定操作（ｂｏｕｎｄｉｎｇ　ｏｐｅｒａｔｉｏｎ）と言う。
【０００８】
上界値が暫定値より大きい値である場合は（Ｓ００６：ＹＥＳ）、計算機は、実数最適解は整数解であるか否かを判定し（Ｓ００７）、実数最適解が整数解であった場合は（Ｓ００７：ＹＥＳ）、該実数最適解は、選択している問題の最適解になっており、しかも該最適解は暫定値よりも大きい目的関数の値を与えるため、選択している問題の最適解、及び該最適解を目的関数へ代入して得られる最適値を、新たな暫定解および暫定値として記憶し（Ｓ００８）、選択している問題を終端する（Ｓ００９）。
【０００９】
ステップＳ００７にて実数最適解が整数解ではない場合は（Ｓ００７：ＮＯ）、計算機は、最後に実数値を定めた活性変数の値を小さくして整数の値にする等の操作により、明らかな最適解が求まるか否かを判定し（Ｓ０１０）、明らかな最適解が求まった場合は（Ｓ０１０：ＹＥＳ）、求まった最適解を目的関数に代入して得られる目的関数の値が暫定値より大きいか否かを判定し（Ｓ０１１）、前記目的関数の値が暫定値より大きい場合は（Ｓ０１１：ＹＥＳ）、ステップＳ００８へ処理を進めて最適解および最適値を新たな暫定解および暫定値として記憶する。ステップＳ０１０にて明らかな最適解が求まらない場合（Ｓ０１０：ＮＯ）、又はステップＳ０１１にて前記目的関数の値が暫定値以下であった場合は（Ｓ０１１：ＮＯ）、計算機は、活性変数の中から一のｘ_ｉ　を選んで、選んだｘ_ｉ　の値を０又は１に固定することで、選択している問題を二つの問題に分割し（Ｓ０１２）、処理をステップＳ００２へ戻し、分割により生成した問題を解くべき問題として記憶する。ステップＳ０１２における、問題を分割する操作を、分枝操作（　ｂｒａｎｃｈｉｎｇ　ｏｐｅｒａｔｉｏｎ）と言う。
【００１０】
ステップＳ００９にて問題を終端させた後は、計算機は、他の解くべき問題を記憶しているか否かを判定し（Ｓ０１３）、他の解くべき問題を記憶している場合は（Ｓ０１３：ＹＥＳ）、ステップＳ００３へ処理を戻して新たな問題を選択し、他の解くべき問題を記憶していない場合は（Ｓ０１３：ＮＯ）、処理を終了する。処理を終了したときに記憶している暫定解が、原問題の最適解である。
【００１１】
図７は、分枝限定法の概要を示す概念図である。図中に示す白丸は問題を示し、黒丸は終端された問題を示す。原問題は、分枝操作により、ｘ_１　が０又は１に固定された二つの部分問題に分割され、更に、夫々の問題は、ｘ_２　が０又は１に固定された二つの部分問題に分割される。（ｘ_１　，ｘ_２　）＝（０，０）の部分問題は、限定操作により終端され、（ｘ_１　，ｘ_２　）＝（０，１）の部分問題が更に分割される。以上の如く、分枝限定法においては、分枝操作により問題を分割し、最適解を含まない問題を限定操作により終端することにより、無駄な計算を行わずに効率的に最適解を求めることができる。
【００１２】
ナップサック問題において、制約条件が複数である場合を多次元ナップサック問題と言い、各変数が非線形で関連づけられている場合を非線形ナップサック問題と言う。多次元非線形ナップサック問題（ｍｕｌｔｉ−ｄｉｍｅｎｓｉｏｎａｌ　ｎｏｎｌｉｎｅａｒ　ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ：ＭＮＫ問題）は、離散最適化問題の一般形であり、以下の如く表現される。
【００１３】
【数２】

【００１４】
ここで、ｘ_ｉ　はｋ_ｉ　通りの値をとりうる整数である。目的関数の最小化を最適化の条件とすることにより、ＭＮＫ問題は、値の最小化を最適化の条件とする離散最適化問題についても対応することができる。
【００１５】
ＭＮＫ問題は、単純なナップサック問題に比べて解くことは格段に困難となる。本発明者は、過去３０年間に渡ってＭＮＫ問題の解法を研究しており、１９８４年に解法の一つである代理制約法（ｓｕｒｒｏｇａｔｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｍｅｔｈｏｄ）を開発している。また、１９９０年に提案した解法であるモジュラ法を用いて単一制約の非線形ナップサック問題を解くアルゴリズムを提案している（非特許文献１を参照）。更に、本発明者は、代理制約法を改良して、より多くの変数を含むＭＮＫ問題を厳密に解くことが可能な改良代理制約法（　ｉｍｐｒｏｖｅｄ　ｓｕｒｒｏｇａｔｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｍｅｔｈｏｄ；以下、ＩＳＣ法と言う）を開発した。ＩＳＣ法を用いて離散最適化問題を解くコンピュータプログラムは、解法の性能をテストするためのテスト問題の一種について、線形の離散最適化問題を解くための商用の最高速のコンピュータプログラムに比べて平均５倍以上の早さで問題を解けることが確かめられている。この開発成果は、Ｊｏｕｒｎａｌ　ｏｆ　ｔｈｅ　ｏｐｅｒａｔｉｏｎ　ｏｆ　ｒｅｓｅａｒｃｈ　ｏｆ　Ｊａｐａｎ　に掲載予定のＮａｋａｇａｗａ　Ｙ．　：Ａｎ　ｉｍｐｒｏｖｅｄ　ｓｕｒｒｏｇａｔｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｍｅｔｈｏｄ　ｆｏｒ　ｓｅｐａｒａｂｌｅ　ｎｏｎｌｉｎｅａｒ　ｉｎｔｅｇｅｒ　ｐｒｏｇｒａｍｍｉｎｇ．に開示されている。
【００１６】
【非特許文献１】
仲川（Ｙ．　Ｎａｋａｇａｗａ）・イワサキ（Ｉ．　Ｉｗａｓａｋｉ）「モジュラ　アプローチ　フォア　ソルビング　ノンリニア　ナップサック　プロブレム（Ｍｏｄｕｌａｒ　Ａｐｐｒｏａｃｈ　ｆｏｒ　Ｓｏｌｖｉｎｇ　Ｎｏｎｌｉｎｅａｒ　Ｋｎａｐｓａｃｋ　Ｐｒｏｂｌｅｍ）」，電子情報通信学会英文論文誌（ＩＥＩＣＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｆｕｎｄａｍｅｎｔａｌｓ），１９９９年，Ｅ８２−Ａ，ｐ．１８６０−１８６４
【００１７】
【発明が解決しようとする課題】
本発明者が開発したモジュラ法又はＩＳＣ法を用いることにより、解の組み合わせの数が１０の１０００乗個の規模となるＭＮＫ問題を厳密に解くことが可能となっている。しかし、問題を解くことの困難さは、解の組み合わせの数のみに依存するものではなく、モジュラ法又はＩＳＣ法を用いて解くことが困難である問題が未だ存在する。また、従来の分枝限定法は、変数の数および該変数がとりうる値の数が多い場合には、組み合わせの爆発を引き起こし、更に、原問題を分割した後に解くことが困難である問題が残り、最終的に原問題が解けなくなる場合がある。
【００１８】
本発明は、斯かる事情に鑑みてなされたものであって、その目的とするところは、問題を分割する際に、問題を解くことの困難さを判定して、解くことが困難である問題から分割を行うことにより、解くことが容易な問題に原問題を分割する問題分割方法、問題分割装置、及びコンピュータを該問題分割装置として実現するためのコンピュータプログラムを提供することにある。
【００１９】
また、本発明の他の目的とするところは、問題を解くことが困難でないと判定した問題を適宜の解法で解くことにより、離散最適化問題を解く最適化方法、最適化装置、及びコンピュータを該最適化装置として実現するためのコンピュータプログラムを提供することにある。
【００２０】
【課題を解決するための手段】
第１発明に係る問題分割方法は、記憶部及び演算部を備えたコンピュータを用いて、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割する方法において、原問題の最適解が得られる可能性を有する、原問題又は部分問題である一の問題を記憶部に記憶し、記憶部に記憶している前記問題を解くことが困難であるか否かを演算部にて判定し、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を演算部にて選択し、選択した変数を、取り得る複数の値の夫々に固定することにより、演算部にて前記問題を複数の問題に分割して記憶部に記憶することを特徴とする。
【００２１】
第２発明に係る最適化方法は、記憶部及び演算部を備えたコンピュータを用いて、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に演算部にて分割して記憶部に記憶し、該部分問題の夫々を演算部にて解くことで前記原問題の最適解を求める最適化方法において、原問題の暫定解を記憶部に記憶し、原問題又は部分問題である解くべき一又は複数の問題を記憶部に記憶し、記憶部に記憶している一又は複数の問題から一の問題を演算部にて選択し、選択した問題について、該問題を解くことによって原問題の最適解が得られる可能性があるか否かを演算部にて判定し、原問題の最適解が得られる可能性がないと判定された場合は、前記問題を演算部にて取り扱うことを中止し、原問題の最適解が得られる可能性があると判定された場合は、前記問題を解くことが困難であるか否かを演算部にて判定し、前記問題を解くことが困難でないと判定された場合は、所定の解法により前記問題の最適解を演算部にて求め、求めた前記問題の最適解が前記暫定解に比べてより最適化されているか否かを演算部にて判定し、前記暫定解に比べてより最適化されていると判定されたときは、前記問題の最適解を新たな暫定解として記憶部に記憶し、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、演算部にて一の変数を選択し、選択した変数を、取り得る複数の値の夫々に固定することにより、演算部にて前記問題を複数の問題に分割し、分割により生成した複数の問題を新たな解くべき問題として記憶部に記憶し、記憶部に記憶している解くべき問題がなくなるまで記憶部及び演算部にて処理を繰り返し、解くべき問題がなくなったときに記憶部に記憶している暫定解を原問題の最適解として記憶部に記憶することを特徴とする。
【００２２】
第３発明に係る問題分割装置は、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割する装置において、原問題の最適解が得られる可能性を有する、原問題又は部分問題である一の問題を記憶する手段と、記憶している前記問題を解くことが困難であるか否かを判定する困難度判定手段と、前記問題を解くことが困難であると前記困難度判定手段により判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択する選択手段と、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割する手段とを備えることを特徴とする。
【００２３】
第４発明に係る問題分割装置は、前記困難度判定手段は、最適化条件が目的関数の最大化であるか又は最小化であるかに対応した、前記問題の緩和問題の実数最適解から得られる目的関数の上界値又は下界値を求める手段と、求めた上界値又は下界値が、原問題の最適解が含まれる所定範囲内に入っているか否かを判定する手段と、前記上界値又は下界値が前記所定範囲内に入っていないと判定された場合は、前記問題を解くことは困難であると判定する手段とを備えることを特徴とする。
【００２４】
第５発明に係る問題分割装置は、前記選択手段は、値が固定されていない複数の離散的な変数の夫々について、取り得る複数の値の夫々に前記変数を固定して得られる複数の問題の緩和問題の夫々を解いた実数最適解の夫々から得られる目的関数の複数の実数最適値を求める手段と、前記変数の夫々について、求めた複数の実数最適値の最小値と最大値との差を求める手段と、複数の前記変数のうち、求めた前記差の値が最小である変数を選択する手段とを備えることを特徴とする。
【００２５】
第６発明に係る最適化装置は、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解く際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割し、該部分問題の夫々を解くことで前記原問題の最適解を求める最適化装置において、原問題の暫定解を記憶する手段と、原問題又は部分問題である解くべき一又は複数の問題を記憶する手段と、記憶している一又は複数の問題から一の問題を選択する手段と、選択した問題について、該問題を解くことによって原問題の最適解が得られる可能性があるか否かを判定する手段と、原問題の最適解が得られる可能性がないと判定された場合は、前記問題を終端する手段と、原問題の最適解が得られる可能性があると判定された場合は、前記問題を解くことが困難であるか否かを判定する困難度判定手段と、前記問題を解くことが困難でないと前記困難度判定手段により判定された場合は、所定の解法により前記問題の最適解を求める手段と、求めた前記問題の最適解が前記暫定解に比べてより最適化されているか否かを判定する手段と、前記暫定解に比べてより最適化されていると判定されたときは、前記問題の最適解を新たな暫定解として記憶する手段と、前記問題を解くことが困難であると前記困難度判定手段により判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択する選択手段と、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割する手段と、分割により生成した複数の問題を新たな解くべき問題として記憶する手段と、解くべき問題がなくなるまで処理を繰り返す手段と、解くべき問題がなくなったときに記憶している暫定解を原問題の最適解とする手段とを備えることを特徴とする。
【００２６】
第７発明に係るコンピュータプログラムは、コンピュータに、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解かせる際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割させるコンピュータプログラムにおいて、コンピュータに、原問題の最適解が得られる可能性を有する、原問題又は部分問題である記憶している一の問題を解くことが困難であるか否かを判定させる困難度判定手順と、コンピュータに、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択させる選択手順と、コンピュータに、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割させる手順とを含むことを特徴とする。
【００２７】
第８発明に係るコンピュータプログラムは、前記困難度判定手順は、コンピュータに、最適化条件が目的関数の最大化であるか又は最小化であるかに対応した、前記問題の緩和問題の実数最適解から得られる目的関数の上界値又は下界値を求めさせる手順と、コンピュータに、求めた上界値又は下界値が、原問題の最適解が含まれる所定範囲内に入っているか否かを判定させる手順と、コンピュータに、前記上界値又は下界値が前記所定範囲内に入っていないと判定された場合は、前記問題を解くことは困難であると判定させる手順とを含むことを特徴とする。
【００２８】
第９発明に係るコンピュータプログラムは、前記選択手順は、コンピュータに、値が固定されていない複数の離散的な変数の夫々について、取り得る複数の値の夫々に前記変数を固定して得られる複数の問題の緩和問題の夫々を解いた実数最適解の夫々から得られる目的関数の複数の実数最適値を求めさせる手順と、コンピュータに、前記変数の夫々について、求めた複数の実数最適値の最小値と最大値との差を求めさせる手順と、コンピュータに、複数の前記変数のうち、求めた前記差の値が最小である変数を選択させる手順とを含むことを特徴とする。
【００２９】
第１０発明に係るコンピュータプログラムは、コンピュータに、一又は複数の制約条件の基で複数の離散的な変数を含む目的関数の値を最大又は最小にする前記変数の値の最適な組み合わせを求める離散最適化問題を解かせる際に、任意の変数の値を固定することにより、解くべき原問題を複数の部分問題に分割し、該部分問題の夫々を解くことで前記原問題の最適解を求めさせるコンピュータプログラムにおいて、コンピュータに、原問題又は部分問題である、記憶している一又は複数の問題から一の問題を選択させる手順と、コンピュータに、選択した問題について、該問題を解くことによって原問題の最適解が得られる可能性があるか否かを判定させる手順と、コンピュータに、原問題の最適解が得られる可能性がないと判定された場合は、前記問題を終端させる手順と、コンピュータに、原問題の最適解が得られる可能性があると判定された場合は、前記問題を解くことが困難であるか否かを判定させる困難度判定手順と、コンピュータに、前記問題を解くことが困難でないと判定された場合は、所定の解法により前記問題の最適解を求めさせる手順と、コンピュータに、求めた前記問題の最適解が記憶している暫定解に比べてより最適化されているか否かを判定させる手順と、コンピュータに、前記暫定解に比べてより最適化されていると判定されたときは、前記問題の最適解を新たな暫定解として記憶させる手順と、コンピュータに、前記問題を解くことが困難であると判定された場合は、前記問題について、値が固定されていない一又は複数の離散的な変数のうち、一の変数を選択させる選択手順と、コンピュータに、選択した変数を、取り得る複数の値の夫々に固定することにより、前記問題を複数の問題に分割させる手順と、コンピュータに、分割により生成した複数の問題を新たな解くべき問題として記憶させる手順と、コンピュータに、解くべき問題がなくなるまで処理を繰り返させる手順と、コンピュータに、解くべき問題がなくなったときに記憶している暫定解を原問題の最適解とさせる手順とを含むことを特徴とする。
【００３０】
第１、第３及び第７発明においては、離散最適化問題を分割する際に、問題を解くことの困難さを判定して、解くことが困難である問題から分割を行うことにより、解くことが容易な問題に原問題を分割する。
【００３１】
第４及び第８発明においては、分割すべき問題の緩和問題より、前記問題から得られる可能性のある解の限界を求め、原問題の最適解を含む所定範囲内に前記限界が入っていない問題を、解くことが困難である問題であると判定することにより、可能な解の中から最適解を探索すべき範囲が広いために解くことが困難である問題を分割する。
【００３２】
第５及び第９発明においては、問題を分割するために固定する活性変数を選択する際、取りうる値の夫々に活性変数のいずれかの値を固定した緩和問題から得られる目的関数の実数最適値について、値を変えたときに得られる実数最適値の最小値と最大値との差が最も小さくなる活性変数を選ぶことにより、目的関数の値の変化が小さく、値を変えて最適値を探索することが困難な活性変数を固定して、解くことが容易な問題に分割する。
【００３３】
第２、第６、及び第１０発明においては、解くことが困難な問題を分割し、困難でない問題を解くことにより、効率的に離散最適化問題を解くことができる。
【００３４】
【発明の実施の形態】
以下本発明をその実施の形態を示す図面に基づき具体的に説明する。
【００３５】
図１は、本発明の問題分割装置の構成を示すブロック図である。問題分割装置１は、本発明に係る最適化装置の機能を兼ね備えており、コンピュータを用いて構成されている。問題分割装置１は、本発明に係る演算部であり、演算を行うＣＰＵ１１と、本発明に係る記憶部であり、演算に伴って発生する一時的な情報を記憶するＲＡＭ１２と、ＣＤ−ＲＯＭドライブ等の外部記憶装置１３と、ハードディスク等の内部記憶装置１４とを備えており、ＣＤ−ＲＯＭ等の記録媒体２から本発明に係るコンピュータプログラム２０を外部記憶装置１３にて読み取り、読み取ったコンピュータプログラム２０を内部記憶装置１４に記憶し、ＲＡＭ１２にコンピュータプログラム２０をロードし、ロードしたコンピュータプログラム２０に基づいて問題分割装置１に必要な処理を実行する。問題分割装置１は、キーボード又はマウス等の入力装置１５と、液晶ディスプレイ又はＣＲＴディスプレイ等の出力装置１６とを備えており、データの入力を初めとするオペレータからの操作を受け付ける構成となっている。
【００３６】
また、問題分割装置１は、図示しない通信インタフェースを備え、該通信インタフェースに接続している図示しないサーバ装置から本発明に係るコンピュータプログラム２０をダウンロードし、ＣＰＵ１１にて処理を実行する形態であってもよい。
【００３７】
次に、離散最適化問題のテスト問題の例を参照しながら本発明の問題分割方法および最適化方法を説明する。参照するテスト問題を以下に示す。
【００３８】
【数３】

【００３９】
この問題は、５個の制約条件の基で、０〜５の６種類の整数の値を取り得る３９変数の最適な組み合わせを求める多次元ナップサック問題である。図２は、テスト問題のパラメータを示す図表である。目的関数を構成する３９個のｃ_ｉ　の値、及び制約条件の式を構成する５×３９のａ_ｊｉの値は、図２に示している通りである。
【００４０】
図３は、本発明の問題分割装置が行う本発明の問題分割方法および最適化方法の処理の手順を示すフローチャートである。問題分割装置１のＣＰＵ１１は、コンピュータプログラム２０をＲＡＭ１２へロードし、ロードしたコンピュータプログラム２０に従って、近似解法を用いて求めた原問題の暫定解、該暫定解を目的関数に代入して得られる値である暫定値、及び問題を解く困難度を判定する基準となる判定基準値を入力装置１５にてオペレータの操作により受け付けて、ＲＡＭ１２に記憶する（Ｓ１）。判定基準値は、暫定値よりもある程度大きい値に定めておく。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、原問題を解くべき問題として記憶する（Ｓ２）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、記憶している一又は複数の問題の中から一の問題を選択する（Ｓ３）。このとき、ＣＰＵ１１は、活性変数の数が少ない問題を優先（以下、深さ優先：ｄｅｐｔｈ　ｆｉｒｓｔ　と言う）して問題を選択する、又は活性変数の数が多い問題を優先（以下、幅優先：ｂｒｅａｄｔｈ　ｆｉｒｓｔ　と言う）して問題を選択する等、様々な方法で問題を選択する。深さ優先を用いた場合は、ＲＡＭ１２に記憶する活性変数の数が少なくなるため、ＲＡＭ１２の容量を節約した計算を行うことができる。幅優先を用いた場合は、最終的に解くべき問題の数が少なくなるために、計算時間を短くすることができる。
【００４１】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択した問題に実行可能解が存在するか否かを判定し（Ｓ４）、実行可能解が存在しない場合は（Ｓ４：ＮＯ）、処理をステップＳ１４へ進め、選択している問題を終端する（Ｓ１４）。実行可能解が存在する場合は（Ｓ４：ＹＥＳ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択している問題の緩和問題を解くことで、実数最適解、及び該実数最適解を目的関数に代入して得られる目的関数の上界値を計算する（Ｓ５）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、計算した上界値が、記憶している暫定値より大きい値であるか否かを判定し（Ｓ６）、上界値が暫定値以下の値である場合は（Ｓ６：ＮＯ）、選択している問題には暫定値よりも良い解が存在しないため、処理をステップＳ１４へ進めて問題を終端する（Ｓ１４）。
【００４２】
上界値が暫定値より大きい値である場合は（Ｓ６：ＹＥＳ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択している問題を解くことが困難であるか否かを判定する困難度判定処理を行う（Ｓ７）。図４は、ステップＳ７の困難度判定処理のサブルーチンを示すフローチャートである。ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、上界値が、記憶している判定基準値より大きいか否かを判定し（Ｓ７１）、上界値が判定基準値より大きい場合は（Ｓ７１：ＹＥＳ）、選択している問題は、解を探索する範囲が広いために、解くことが困難であると判定し（Ｓ７２）、処理をメインの処理へ戻す。上界値が判定基準値以下である場合は（Ｓ７１：ＮＯ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択している問題は、解くことが困難でないと判定し（Ｓ７３）、処理をメインの処理へ戻す。なお、困難度判定処理は、選択している問題の最適解を推定した値を目的関数に代入した値と上界値との値の差を用いる等、他の方法を用いて困難度の判定を行っても良い。
【００４３】
困難度判定処理にて、選択している問題を解くことが困難であると判定された場合は（Ｓ８：ＹＥＳ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択した問題が含んでいる複数の活性変数から一の活性変数を選択する選択処理を行う（Ｓ９）。図５は、ステップＳ９の選択処理のサブルーチンを示すフローチャートである。ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、複数の活性変数の中から、一の活性変数を選択し（Ｓ９１）、選択した活性変数を、取りうる各値に固定したときの、目的関数の上界値を計算し（Ｓ９２）、前記活性変数の値を変化させることにより変化する前記上界値の最大値と最小値との差の値を計算する（Ｓ９３）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、全ての活性変数について前記差の値を計算したか否かを判定し（Ｓ９４）、全てを計算していない場合は（Ｓ９４：ＮＯ）、ステップＳ９１へ処理を戻して次の活性変数を選択し、全ての活性変数について前記差の値を計算している場合は（Ｓ９４：ＹＥＳ）、前記差の値が最小となる活性変数を選択し（Ｓ９５）、処理をメインの処理へ戻す。この選択処理により、目的関数の値の変化が小さく、活性変数の値を変えて最適値を探索することが困難な問題を分割することができる。なお、計算した上界値が小さくなる活性変数を選択する等、他の方法を用いて活性変数の選択を行ってもよい。
【００４４】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択処理により選択した活性変数を、取りうる夫々の値に固定することにより、選択している問題を前記値の種類の数の問題に分割して、複数の問題を生成し（Ｓ１０）、処理をステップＳ２へ戻して、生成した複数の問題を、解くべき問題としてＲＡＭ１２に記憶する。テスト問題の場合は、選択している問題が、選択された活性変数ｘ_ｉ　の値が０〜５の６通りの整数のいずれかに固定された６個の問題に分割されて、記憶される。
【００４５】
困難度判定処理にて、選択している問題を解くことが困難ではないと判定された場合は（Ｓ８：ＮＯ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択している問題を、モジュラ法またはＩＳＣ法などの解法を用いて解いて、選択している問題の最適解を計算し（Ｓ１１）、計算した最適解を代入した目的関数の値が暫定値よりも大きいか否かを判定する（Ｓ１２）。前記目的関数の値が暫定値以下であった場合は（Ｓ１２：ＮＯ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、処理をステップＳ１４へ進めて問題を終端し（Ｓ１４）、前記目的関数の値が暫定値よりも大きい場合は（Ｓ１２：ＹＥＳ）、前記最適解、及び前記目的関数の値を、新たな暫定解および暫定値としてＲＡＭ１２に記憶し（Ｓ１３）、選択している問題を終端する（Ｓ１４）。
【００４６】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ＲＡＭ１２が他の解くべき問題を記憶しているか否かを判定し（Ｓ１５）、他の解くべき問題を記憶している場合は（Ｓ１５：ＹＥＳ）、ステップＳ３へ処理を戻して新たな問題を選択し、ＲＡＭ１２が他の解くべき問題を記憶していない場合は（Ｓ１５：ＮＯ）、ＲＡＭ１２に記憶している暫定解を、原問題の最適解として出力し（Ｓ１６）、処理を終了する。
【００４７】
以上の処理に従って、最初の暫定値を１４３３２、及び判定基準値を１４３５３として、テスト問題を解く計算を行った。ＩＳＣ法を用いて同一の問題を解いた場合は、２２０秒以上の計算時間で厳密な解が求められなかったことに比べて、本発明では、３７秒で厳密な解を得ることができた。得られた最適解は、（０００００３００００　００５３５１５０５５　００００５０３０５５　３５０００４０３０）であり、最大化された目的関数の値は、１４３３３である。
【００４８】
以上詳述した如く、本発明においては、離散最適化問題を解く際に、問題を解くことの困難度を判定し、解くことが困難である問題を、解くことがより容易である問題に分割し、解くことが困難でない問題をモジュラ法またはＩＳＣ法などの解法で解くことにより、効率的に問題を解き、従来では解くことができなかった問題を解くことが可能になり、また、従来よりも短い時間、小さいメモリ容量で離散最適化問題を解くことができる。様々な離散最適化問題を高速かつ厳密に解くことができるため、倉庫における最適な物品の管理方法、作業のスケジューリング、運送機器への運送すべき物品の割り当て、及び設備の配置など、社会活動における様々な問題に適用して、社会活動の効率化を図ることができる。
【００４９】
なお、本実施の形態においては、目的関数の最大化を最適化条件としている問題例を示したが、目的関数の最小化を最適化条件としている問題についても、前述の処理で用いた上界値の代わりに目的関数の下界値を用いて、下界値が暫定値以上である問題を終端する等、下界値を各種の判定の基準に用いることにより、同様の処理を用いて解くことができる。また、目的関数および制約条件が線形関数である問題例を示したが、非線形関数を用いた問題であっても解くことができるのは、もちろんであり、一般的な離散最適化問題に適用することができる。
【００５０】
また、本実施の形態においては、最適化装置の機能を兼ね備えた本発明の問題分割装置１は、一のＣＰＵ１１を備えた一のコンピュータを用いて構成してある形態を示したが、これに限る物ではなく、複数のＣＰＵ１１，１１，…を備えたコンピュータを用いて構成した形態であってもよく、また、夫々がＣＰＵを備えた複数のコンピュータを互いに接続させて構成した形態であってもよい。本発明は、この場合の如く複数のＣＰＵ又は複数のコンピュータを用いて構成される並列計算機についても適用可能であり、原問題を分割した複数の問題の夫々を複数のＣＰＵ又は複数のコンピュータの夫々にて独立に解くことにより、本発明を用いた並列計算を行って、より高速に離散最適化問題を解くことができる。
【００５１】
更に、本実施の形態においては、本発明の問題分割装置１は、本発明の最適化装置の機能を兼ね備えている形態を示したが、これに限るものではなく、問題分割装置１と、モジュラ法またはＩＳＣ法などを用いて問題を解く装置とを夫々別のコンピュータにて構成し、互いにデータを入出力することにより本発明の最適化装置を構成する形態としてもよい。
【００５２】
【発明の効果】
第１、第３、及び第７発明においては、離散最適化問題を分割する際に、問題を解くことの困難さを判定して、解くことが困難である問題から分割を行うことにより、解くことが容易な問題に原問題を分割することができる。
【００５３】
第４及び第８発明においては、分割すべき問題の緩和問題より、前記問題から得られる可能性のある解の限界を求め、原問題の最適解を含む所定範囲内に前記限界が入っていない問題を、解くことが困難である問題であると判定することにより、可能な解の中から最適解を探索すべき範囲が広いために解くことが困難である問題を分割することができる。
【００５４】
第５及び第９発明においては、問題を分割するために固定する活性変数を選択する際、取りうる値の夫々に活性変数のいずれかの値を固定した緩和問題から得られる目的関数の実数最適値について、値を変えたときに得られる実数最適値の最小値と最大値との差が最も小さくなる活性変数を選ぶことにより、目的関数の値の変化が小さく、活性変数の値を変えて最適値を探索することが困難な問題を分割することができる。
【００５５】
第２、第６、及び第１０発明においては、解くことが困難な問題を分割し、困難でない問題を解くことにより、効率的に離散最適化問題を解くことができる。また、一般的な離散最適化問題を高速かつ厳密に解くことができるため、倉庫における最適な物品の管理方法、作業のスケジューリング、運送機器への運送すべき物品の割り当て、及び設備の配置など、社会活動における様々な問題に適用して、社会活動の効率化を図ることができる等、本発明は優れた効果を奏する。
【図面の簡単な説明】
【図１】本発明の問題分割装置の構成を示すブロック図である。
【図２】テスト問題のパラメータを示す図表である。
【図３】本発明の問題分割装置が行う本発明の問題分割方法および最適化方法の処理の手順を示すフローチャートである。
【図４】ステップＳ７の困難度判定処理のサブルーチンを示すフローチャートである。
【図５】ステップＳ９の選択処理のサブルーチンを示すフローチャートである。
【図６】分枝限定法の手順を示すフローチャートである。
【図７】分枝限定法の概要を示す概念図である。
【符号の説明】
１　問題分割装置
１１　ＣＰＵ（演算部）
１２　ＲＡＭ（記憶部）
２　記録媒体
２０　コンピュータプログラム[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention solves a discrete optimization problem represented by a knapsack problem by dividing a problem into a plurality of subproblems, a problem dividing apparatus, and a discrete optimization problem using the problem dividing method. The present invention relates to an optimization method to be solved, an optimization device, and a computer program for realizing a computer as the problem dividing device or the optimization device.
[0002]
[Prior art]
The discrete optimization problem is a problem in which an optimal combination is determined based on predetermined constraints from combinations of discrete variables such as integers. It is necessary to solve for the route determination to shorten the length. In order to solve the discrete optimization problem exactly, it is necessary to enumerate possible combinations one by one. When the number of variables is large, the number of combinations increases explosively, and the so-called combination explosion ( combinatorial explosion).
[0003]
The knapsack problem is a typical problem of the discrete optimization problem. When there are a plurality of types of items having a defined value and capacity and a knapsack having a limited capacity, the total capacity is determined by the capacity. The problem is to find the combination that maximizes the total value from among the combinations of items that are below the limit. The knapsack problem belongs to the NP-hard problem, which is difficult to solve within an effective time using a computer, and various solutions for efficiently solving the knapsack problem have been proposed. ing.
[0004]
A branch and bound method is a typical solution for efficiently solving the knapsack problem. The branch-and-bound method is a method of solving an original problem by dividing an original problem to be solved into a plurality of partial problems and solving partial problems that can be solved in order. An example of the knapsack problem is shown below.
[0005]
(Equation 1)

[0006]
Where a _i , C _i , B are positive real numbers and c _i Is the value of the goods, a _i Is the volume of the item, b is the volume limit of the knapsack, and x _i = 0 means that the item is not put in the knapsack, and x _i = 1 corresponds to placing an item in a knapsack, and the value of the objective function f (X) corresponds to the sum of values. The purpose of this problem is to find the optimal solution of X that maximizes the value of the objective function f (X) under constraints. In the branch and bound method, any x _i Is fixed to 0 or 1 in order to divide the problem into subproblems and solve the problem.
[0007]
FIG. 6 is a flowchart showing the procedure of the branch and bound method. The computer that performs the calculation using the branch and bound method first stores the provisional solution obtained by using the approximate solution and the provisional value of the objective function obtained by substituting the provisional solution for f (X) (S001). ), And store the original problem as a problem to be solved (S002). The computer selects one of the stored questions (S003), and determines whether an executable solution exists for the selected question (S004). For example, in the constraint expression, any x _i Clearly, there is no feasible solution for the selected problem if the sum of the terms that are fixed by fixing the value of is greater than b. If it is determined that there is no feasible solution (S004: NO), it is apparently unnecessary to solve the selected problem, and the computer advances the process to step S009 to solve the selected problem. It is excluded from the power target (hereinafter referred to as the end of the problem) (S009). If it is determined that a feasible solution exists (S004: YES), the computer solves the relaxation problem of the selected problem, and substitutes the real optimal solution of X and the real optimal solution into f (X). Is calculated (S005). The mitigation problem is an unfixed x _i (Hereinafter referred to as an active variable) is relaxed, and x _i Is 0 ≦ x _i The problem is to find X that maximizes the objective function, assuming that it is a real number in the range of ≦ 1, _i / A _i By setting the value of the active variable to be as large as possible as long as the constraint condition is satisfied in the order of i in which the value of i is large, a real optimal solution which is an optimal solution of X consisting of real numbers can be easily obtained. The value obtained by substituting the real optimal solution into the objective function is the maximum value of the objective function in the relaxation problem, which is larger or equal to the maximum value of the objective function in the selected problem. The upper bound of the objective function for the problem in question. Next, the computer determines whether the calculated upper bound value is larger than the stored provisional value (S006). If the upper bound value is smaller than the provisional value (S006: NO) Since there is no better solution than the provisional value in the selected question, the process proceeds to step S009 to terminate the question (S009). The operation of excluding a problem that does not need to be solved in steps S004 to S006 is referred to as a bounding operation.
[0008]
If the upper bound value is larger than the provisional value (S006: YES), the computer determines whether the real optimal solution is an integer solution (S007), and if the real optimal solution is an integer solution. (S007: YES), the real optimal solution is the optimal solution of the selected problem, and the optimal solution gives a value of the objective function larger than the provisional value. The optimal solution and the optimal value obtained by substituting the optimal solution for the objective function are stored as new provisional solutions and provisional values (S008), and the selected problem is terminated (S009).
[0009]
If the real optimal solution is not an integer solution at step S007 (S007: NO), the computer clearly performs an operation such as reducing the value of the active variable that finally determined the real value to an integer value. It is determined whether or not the optimal solution is obtained (S010). If an obvious optimal solution is obtained (S010: YES), the value of the objective function obtained by substituting the obtained optimal solution into the objective function is larger than the provisional value. It is determined whether or not the value is larger (S011). If the value of the objective function is larger than the provisional value (S011: YES), the process proceeds to step S008, and the optimal solution and the optimal value are set as the new provisional solution and the provisional value. Remember. If a clear optimal solution cannot be obtained in step S010 (S010: NO), or if the value of the objective function is less than or equal to the provisional value in step S011 (S011: NO), the computer sets the active variable One of the x _i Choose and choose x _i Is fixed to 0 or 1, the selected problem is divided into two problems (S012), the process returns to step S002, and the problem generated by the division is stored as a problem to be solved. The operation of dividing the problem in step S012 is referred to as a branching operation.
[0010]
After terminating the problem in step S009, the computer determines whether another problem to be solved is stored (S013). If another problem to be solved is stored (S013: YES) ), The process returns to step S003 to select a new problem, and if no other problem to be solved is stored (S013: NO), the process ends. The provisional solution stored at the end of the process is the optimal solution of the original problem.
[0011]
FIG. 7 is a conceptual diagram showing an outline of the branch and bound method. The white circles in the figure indicate problems, and the black circles indicate terminated problems. The original problem is obtained by branching ₁ Is divided into two subproblems fixed at 0 or 1, and further, each problem is represented by x ₂ Is divided into two subproblems fixed at 0 or 1. (X ₁ , X ₂ ) = (0,0) is terminated by a limited operation, and (x ₁ , X ₂ ) = (0,1) is further divided. As described above, in the branch and bound method, a problem is divided by a branching operation, and a problem that does not include an optimal solution is terminated by a limiting operation, so that an optimal solution can be efficiently obtained without performing unnecessary calculations. Can be.
[0012]
In the knapsack problem, a case where there are a plurality of constraint conditions is called a multidimensional knapsack problem, and a case where each variable is nonlinearly related is called a nonlinear knapsack problem. The multi-dimensional non-linear knapsack problem (MNK problem) is a general form of a discrete optimization problem, and is expressed as follows.
[0013]
(Equation 2)

[0014]
Where x _i Is k _i It is an integer that can take any value. By setting the objective function minimization as an optimization condition, the MNK problem can also cope with a discrete optimization problem in which the value minimization is an optimization condition.
[0015]
The MNK problem is much more difficult to solve than a simple knapsack problem. The inventor has been studying a solution method of the MNK problem for the past 30 years, and has developed a surrogate constraints method, which is one of the solution methods, in 1984. Further, an algorithm for solving a single-constrained nonlinear knapsack problem using a modular method, which is a solution method proposed in 1990, has been proposed (see Non-Patent Document 1). Further, the present inventor has developed an improved surrogate constraints method (hereinafter, referred to as an ISC method) capable of strictly solving an MNK problem including more variables by improving the surrogate constraint method. did. A computer program that solves a discrete optimization problem using the ISC method has an average of one type of test problem for testing the performance of the solution compared to the fastest commercial computer program for solving a linear discrete optimization problem. It has been confirmed that the problem can be solved more than five times faster. The results of this development are described in Nakagawa Y., scheduled to be published in the Journal of the operation of research of Japan. : An improved surrogates constraints methods for for non-linear integrator programming. Is disclosed.
[0016]
[Non-patent document 1]
Nakagawa (Y. Nakagawa) · Iwasaki (I. Iwasaki) "modular approach fore Sorubingu non-linear knapsack Problem (Modular Approach for Solving Nonlinear Knapsack Problem)", Institute of Electronics, Information and Communication Engineers English Journal (IEICE Transactions on Fundamentals), 1999 years, E82 -A, p. 1860-1864
[0017]
[Problems to be solved by the invention]
By using the modular method or the ISC method developed by the present inventors, it is possible to exactly solve the MNK problem in which the number of solution combinations is 10 to the power of 1000. However, the difficulty of solving a problem does not depend only on the number of combinations of solutions, and there are still problems that are difficult to solve using the modular method or the ISC method. In addition, the conventional branch and bound method causes an explosion of combinations when the number of variables and the number of possible values of the variables are large, and furthermore, it is difficult to solve the problem after dividing the original problem. In some cases, the original problem may not be solved.
[0018]
The present invention has been made in view of such circumstances, and an object of the present invention is to determine the difficulty of solving a problem when dividing the problem and to solve the problem that is difficult to solve. Another object of the present invention is to provide a problem dividing method, a problem dividing device, and a computer program for realizing a computer as the problem dividing device by dividing an original problem into a problem that can be easily solved by dividing the original problem.
[0019]
Another object of the present invention is to solve an optimization method, an optimization device, and a computer for solving a discrete optimization problem by solving a problem determined to be not difficult to solve by an appropriate solution. Another object of the present invention is to provide a computer program for realizing the optimization device.
[0020]
[Means for Solving the Problems]
A problem dividing method according to a first aspect of the present invention maximizes or minimizes a value of an objective function including a plurality of discrete variables based on one or a plurality of constraints using a computer including a storage unit and an operation unit. When solving a discrete optimization problem that seeks an optimal combination of the values of the variables, a method of dividing an original problem to be solved into a plurality of partial problems by fixing the value of an arbitrary variable, Is stored in the storage unit, and the calculation unit determines whether it is difficult to solve the problem stored in the storage unit. However, when it is determined that it is difficult to solve the problem, for the problem, one or a plurality of discrete variables whose values are not fixed, one variable is selected by the calculation unit, Assign the selected variable to each of the possible values By constant, and to store in the memory unit by dividing the problem into a plurality of problems by the computing unit.
[0021]
An optimization method according to a second aspect of the present invention maximizes or minimizes a value of an objective function including a plurality of discrete variables under one or a plurality of constraints using a computer including a storage unit and a calculation unit. When solving a discrete optimization problem that seeks the optimal combination of the values of the variables, by fixing the value of any variable, the original problem to be solved is divided into a plurality of partial problems by the arithmetic unit and stored in the storage unit. In the optimization method for obtaining the optimal solution of the original problem by solving each of the partial problems in an arithmetic unit, the provisional solution of the original problem is stored in the storage unit, and the original or partial problem should be solved. One or more problems are stored in the storage unit, one of the one or more problems stored in the storage unit is selected by the calculation unit, and the selected problem is solved to solve the original problem. Calculate whether there is a possibility of obtaining the optimal solution When it is determined that there is no possibility that the optimal solution of the original problem can be obtained, it is determined that there is a possibility that the optimal solution of the original problem may be obtained by stopping the processing of the problem in the arithmetic unit. When it is determined, it is determined by the calculation unit whether or not it is difficult to solve the problem. When it is determined that it is not difficult to solve the problem, the optimal solution of the problem is determined by a predetermined solution. Is determined by the calculation unit, whether or not the obtained optimal solution of the problem is more optimized than the provisional solution is determined by the calculation unit, and it is determined that the optimal solution is more optimized than the provisional solution. When it is determined, the optimal solution of the problem is stored in the storage unit as a new provisional solution, and when it is determined that it is difficult to solve the problem, the value of the problem is not fixed. Or, select one variable in the calculation unit from multiple discrete variables By fixing the selected variable to each of a plurality of possible values, the calculation unit divides the problem into a plurality of problems, and the plurality of problems generated by the division are stored in the storage unit as new problems to be solved. The processing is repeated in the storage unit and the operation unit until there are no more problems to be solved stored in the storage unit. When there are no more problems to be solved, the provisional solution stored in the storage unit is optimized for the original problem Is stored in the storage unit.
[0022]
A problem dividing apparatus according to a third aspect of the present invention provides a discrete optimization for obtaining an optimal combination of values of an objective function including a plurality of discrete variables under one or a plurality of constraints to maximize or minimize the values of the variables. An original problem or partial problem that has the possibility of obtaining the optimal solution of the original problem in a device that divides the original problem to be solved into a plurality of partial problems by fixing the values of arbitrary variables when solving the problem Means for storing one problem, difficulty level determining means for determining whether it is difficult to solve the stored problem, and difficulty level determining if the problem is difficult to solve. When the determination is made by the means, for the problem, a selection means for selecting one variable among one or a plurality of discrete variables whose values are not fixed, and a plurality of possible values for the selected variable. By fixing to each Characterized in that it comprises a means for dividing the serial problem several problems.
[0023]
According to a fourth aspect of the present invention, in the problem dividing apparatus, the difficulty determination unit obtains a real number optimal solution of the problem mitigation problem corresponding to whether the optimization condition is maximization or minimization of the objective function. Means for determining an upper or lower bound value of the objective function to be obtained; means for determining whether the determined upper or lower bound value is within a predetermined range including the optimal solution of the original problem; Means for determining that it is difficult to solve the problem when it is determined that the limit value or the lower limit value does not fall within the predetermined range.
[0024]
According to a fifth aspect of the present invention, in the problem dividing apparatus, the selecting unit is configured such that, for each of a plurality of discrete variables having unfixed values, a plurality of problems obtained by fixing the variables to a plurality of possible values. Means for obtaining a plurality of real optimum values of the objective function obtained from each of the real optimum solutions for solving each of the relaxation problems, and for each of the variables, a minimum value and a maximum value of the obtained plurality of real optimum values. It is characterized by comprising: means for calculating a difference; and means for selecting a variable having a minimum value of the calculated difference from among the plurality of variables.
[0025]
An optimization device according to a sixth aspect of the present invention provides a discrete optimization that obtains an optimal combination of values of an objective function including a plurality of discrete variables under one or a plurality of constraint conditions. When solving a problem, an optimization device that divides an original problem to be solved into a plurality of partial problems by fixing the values of arbitrary variables, and solves each of the partial problems to obtain an optimal solution of the original problem Means for storing a provisional solution of the original problem, means for storing one or more problems to be solved which is the original problem or a partial problem, and means for selecting one problem from the stored one or more problems Means for determining whether there is a possibility that an optimal solution of the original problem can be obtained by solving the selected problem, and determining that there is no possibility that an optimal solution of the original problem can be obtained. If so, means to terminate the problem When it is determined that there is a possibility that an optimal solution of the original problem can be obtained, a difficulty level determination unit that determines whether it is difficult to solve the problem, and that the problem is not difficult to solve. A means for obtaining an optimal solution of the problem by a predetermined solution, and determining whether or not the obtained optimal solution of the problem is more optimized than the provisional solution, Means, means for storing the optimum solution of the problem as a new provisional solution when it is determined that the solution is more optimized than the provisional solution, and means for storing the solution if it is difficult to solve the problem. When the degree is determined by the degree determination means, for the problem, a selection means for selecting one variable from one or a plurality of discrete variables whose values are not fixed, and a plurality of possible variables for the selected variable. Fixed to each of the values Means for dividing the problem into a plurality of problems, means for storing the plurality of problems generated by the division as new problems to be solved, means for repeating the process until there are no more problems to be solved, Means for making the provisional solution stored at the time of the optimization the optimal solution of the original problem.
[0026]
A computer program according to a seventh aspect of the present invention provides a computer program which obtains an optimal combination of values of an objective function including a plurality of discrete variables under one or a plurality of constraints so as to maximize or minimize the values of the variables. When solving an optimization problem, a computer program that divides the original problem to be solved into a plurality of subproblems by fixing the values of arbitrary variables will give the computer the possibility of obtaining the optimal solution of the original problem. Having, a difficulty determination procedure for determining whether it is difficult to solve one stored problem that is an original problem or a partial problem, and a computer determining that the problem is difficult to solve. In the case of the problem, a selection procedure for selecting one variable from one or a plurality of discrete variables whose values are not fixed, and The number of, by fixing to each of a plurality of possible values, characterized in that it comprises a procedure for dividing the problem into multiple problems.
[0027]
According to an eighth aspect of the present invention, in the computer program according to the first aspect of the present invention, the difficulty determination step includes a step of causing the computer to determine whether the optimization condition is a maximization or a minimization of the objective function, the real optimal solution of the problem mitigation problem. And the computer determines whether or not the obtained upper or lower bound value is within a predetermined range that includes the optimal solution of the original problem. Causing the computer to determine that it is difficult to solve the problem when it is determined that the upper bound value or the lower bound value is not within the predetermined range. I do.
[0028]
A computer program according to a ninth invention is a computer program, wherein, for each of a plurality of discrete variables whose values are not fixed, a plurality of values obtained by fixing the variables to a plurality of possible values are provided. A procedure for obtaining a plurality of real optimal values of an objective function obtained from each of the real optimal solutions obtained by solving each of the relaxation problems of the problem, and causing the computer to calculate the minimum of the plurality of real optimal values obtained for each of the variables. The method is characterized by including a procedure for obtaining a difference between a value and a maximum value, and a procedure for causing a computer to select a variable having a minimum value of the obtained difference from the plurality of variables.
[0029]
A computer program according to a tenth aspect of the present invention is a computer program which obtains, by a computer, an optimal combination of values of an objective function including a plurality of discrete variables under one or a plurality of constraint conditions. When solving the optimization problem, by fixing the value of any variable, the original problem to be solved is divided into a plurality of partial problems, and the optimal solution of the original problem is obtained by solving each of the partial problems. A computer program that causes the computer to select one of one or more stored problems, which is an original problem or a partial problem, and causes the computer to solve the selected problem for the selected problem. The procedure for determining whether there is a possibility that the optimal solution to the problem can be obtained, and the procedure for when the computer determines that there is no possibility to obtain the optimal solution to the original problem Is a procedure for terminating the problem, and a degree of difficulty determination for causing the computer to determine whether it is difficult to solve the problem if it is determined that there is a possibility that an optimal solution to the original problem can be obtained. Procedures, when the computer determines that it is not difficult to solve the problem, a procedure for obtaining an optimal solution of the problem by a predetermined solution, and the computer stores the obtained optimal solution of the problem. A procedure for determining whether or not the solution is more optimized than the provisional solution, and when the computer determines that the solution is more optimized than the provisional solution, a new optimal solution for the problem is determined. Procedure to be stored as a provisional solution, and the computer, if it is determined that it is difficult to solve the problem, for the problem, of one or more discrete variables whose values are not fixed, A step of selecting the variables, a step of causing the computer to fix the selected variable to each of a plurality of possible values, thereby dividing the problem into a plurality of problems, and the computer The procedure to store the problem as a new problem to be solved, the procedure to make the computer repeat the process until there are no more problems to solve, and the provisional solution stored in the computer when there are no more problems to solve And a procedure for obtaining an optimal solution of
[0030]
In the first, third, and seventh aspects of the present invention, when dividing a discrete optimization problem, the difficulty of solving the problem is determined, and the problem is solved by dividing the problem that is difficult to solve. Divide the original problem into easy problems.
[0031]
In the fourth and eighth inventions, a limit of a solution that can be obtained from the problem is obtained from the relaxation problem of the problem to be divided, and the limit does not fall within a predetermined range including the optimal solution of the original problem. By determining that the problem is a problem that is difficult to solve, a problem that is difficult to solve due to a wide range in which to search for an optimal solution from among possible solutions is divided.
[0032]
In the fifth and ninth inventions, when selecting an active variable to be fixed in order to divide a problem, a real optimum of an objective function obtained from a relaxation problem in which one of active values is fixed to each of possible values For the value, by selecting an active variable that minimizes the difference between the minimum value and the maximum value of the real optimum value obtained when the value is changed, the change in the value of the objective function is small. Fix active variables that are difficult to find and divide them into problems that are easy to solve.
[0033]
In the second, sixth, and tenth aspects, a discrete optimization problem can be efficiently solved by dividing a problem that is difficult to solve and solving a problem that is not difficult.
[0034]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, the present invention will be specifically described with reference to the drawings showing the embodiments.
[0035]
FIG. 1 is a block diagram showing a configuration of a problem dividing apparatus according to the present invention. The problem dividing device 1 also has the function of the optimizing device according to the present invention, and is configured using a computer. The problem dividing apparatus 1 is an operation unit according to the present invention, which is a CPU 11 that performs an operation, a storage unit according to the present invention, a RAM 12 that stores temporary information generated by the operation, and a CD-ROM drive. Etc., and an internal storage device 14 such as a hard disk. The computer program 20 according to the present invention is read from the recording medium 2 such as a CD-ROM by the external storage device 13 and read. 20 is stored in the internal storage device 14, the computer program 20 is loaded into the RAM 12, and processing necessary for the problem dividing device 1 is executed based on the loaded computer program 20. The problem dividing apparatus 1 includes an input device 15 such as a keyboard or a mouse, and an output device 16 such as a liquid crystal display or a CRT display, and is configured to receive an operation from an operator including data input. .
[0036]
In addition, the problem dividing apparatus 1 includes a communication interface (not shown), downloads the computer program 20 according to the present invention from a server device (not shown) connected to the communication interface, and executes the processing by the CPU 11. Is also good.
[0037]
Next, the problem dividing method and the optimizing method of the present invention will be described with reference to an example of a test problem of the discrete optimization problem. The test questions to be referenced are shown below.
[0038]
[Equation 3]

[0039]
This problem is a multidimensional knapsack problem for obtaining an optimal combination of 39 variables that can take six types of integer values from 0 to 5 under five constraints. FIG. 2 is a chart showing parameters of a test question. 39 cs that make up the objective function _i And a 5 × 39 a that constitutes a constraint condition expression _ji Are as shown in FIG.
[0040]
FIG. 3 is a flowchart showing a procedure of processing of the problem dividing method and the optimizing method of the present invention performed by the problem dividing apparatus of the present invention. The CPU 11 of the problem dividing apparatus 1 loads the computer program 20 into the RAM 12 and, in accordance with the loaded computer program 20, a provisional solution of the original problem obtained by using the approximate solution, and a value obtained by substituting the provisional solution into the objective function. And a determination reference value serving as a reference for determining the degree of difficulty in solving a problem are received by the input device 15 by an operator's operation and stored in the RAM 12 (S1). The determination reference value is set to a value that is somewhat larger than the provisional value. Next, the CPU 11 stores the original problem as a problem to be solved according to the computer program 20 loaded into the RAM 12 (S2). Next, the CPU 11 selects one question from the stored one or more questions in accordance with the computer program 20 loaded into the RAM 12 (S3). At this time, the CPU 11 selects a problem by giving priority to a problem with a small number of active variables (hereinafter, referred to as depth first), or gives priority to a problem with a large number of active variables (hereinafter, breadth-first: breadth). First, the problem is selected in various ways. When the depth priority is used, the number of active variables stored in the RAM 12 is reduced, so that the calculation can be performed while saving the capacity of the RAM 12. When breadth-first is used, the number of problems to be finally solved decreases, so that the calculation time can be shortened.
[0041]
Next, the CPU 11 determines whether a feasible solution exists for the selected problem according to the computer program 20 loaded into the RAM 12 (S4). If no feasible solution exists (S4: NO), the CPU 11 proceeds to step S4. To step S14, and terminate the selected question (S14). If there is an executable solution (S4: YES), the CPU 11 solves the relaxation problem of the selected problem according to the computer program 20 loaded in the RAM 12 to obtain the real optimal solution and the objective of the real optimal solution. The upper bound of the objective function obtained by substituting into the function is calculated (S5). Next, the CPU 11 determines whether the calculated upper bound value is larger than the stored provisional value according to the computer program 20 loaded in the RAM 12 (S6), and the upper bound value is equal to or less than the provisional value. (S6: NO), there is no better solution than the provisional value in the selected question, so the process proceeds to step S14 to terminate the question (S14).
[0042]
If the upper bound value is larger than the provisional value (S6: YES), the CPU 11 determines whether it is difficult to solve the selected problem according to the computer program 20 loaded in the RAM 12. A degree determination process is performed (S7). FIG. 4 is a flowchart showing a subroutine of the difficulty level determination process in step S7. The CPU 11 determines whether or not the upper bound value is larger than the stored reference value in accordance with the computer program 20 loaded in the RAM 12 (S71). If the upper bound value is greater than the reference value (S71: YES), it is determined that the selected problem is difficult to solve because the search range for the solution is wide (S72), and the process returns to the main process. If the upper bound value is equal to or less than the determination reference value (S71: NO), the CPU 11 determines that the selected problem is not difficult to solve according to the computer program 20 loaded into the RAM 12 (S73), and To the main process. The difficulty determination process uses another method, such as using a difference between a value obtained by substituting a value obtained by estimating an optimal solution of a selected problem into an objective function and an upper bound value. May be performed.
[0043]
When it is determined in the difficulty determination process that it is difficult to solve the selected problem (S8: YES), the CPU 11 includes the selected problem according to the computer program 20 loaded in the RAM 12. A selection process for selecting one active variable from a plurality of active variables is performed (S9). FIG. 5 is a flowchart showing a subroutine of the selection process in step S9. The CPU 11 selects one active variable from a plurality of active variables according to the computer program 20 loaded into the RAM 12 (S91), and fixes the selected active variable to each possible value. An upper bound value is calculated (S92), and a value of a difference between a maximum value and a minimum value of the upper bound value which is changed by changing the value of the activation variable is calculated (S93). Next, the CPU 11 determines whether or not the difference values have been calculated for all the active variables according to the computer program 20 loaded into the RAM 12 (S94), and when not all have been calculated (S94: NO). Returning to step S91, the next active variable is selected, and if the difference value is calculated for all the active variables (S94: YES), the active variable with the minimum difference value is selected. (S95), and returns the processing to the main processing. By this selection processing, it is possible to divide the problem in which the change in the value of the objective function is small and it is difficult to search for the optimum value by changing the value of the active variable. The active variable may be selected using another method, such as selecting an active variable for which the calculated upper bound value becomes smaller.
[0044]
Next, the CPU 11 fixes the active variables selected by the selection process to the respective possible values in accordance with the computer program 20 loaded in the RAM 12, thereby reducing the selected problem to the problem of the number of types of the values. The program is divided to generate a plurality of problems (S10), the process returns to step S2, and the generated plurality of problems are stored in the RAM 12 as problems to be solved. In the case of a test question, the selected question is the selected active variable x _i Is divided into six questions in which the value of is fixed to any of six integers from 0 to 5, and stored.
[0045]
If it is determined in the difficulty determination process that it is not difficult to solve the selected problem (S8: NO), the CPU 11 determines the selected problem according to the computer program 20 loaded in the RAM 12. It solves using a solution method such as the modular method or the ISC method, calculates the optimal solution of the selected problem (S11), and determines whether the value of the objective function to which the calculated optimal solution is substituted is larger than the provisional value. A determination is made (S12). If the value of the objective function is equal to or less than the provisional value (S12: NO), the CPU 11 advances the process to step S14 according to the computer program 20 loaded in the RAM 12, and terminates the problem (S14). Is larger than the provisional value (S12: YES), the optimal solution and the value of the objective function are stored in the RAM 12 as a new provisional solution and a provisional value (S13), and the selected problem is determined. Terminate (S14).
[0046]
Next, the CPU 11 determines whether or not the RAM 12 stores another problem to be solved according to the computer program 20 loaded into the RAM 12 (S15). If the RAM 12 stores another problem to be solved (S15). : YES), the process returns to step S3, a new problem is selected, and if the RAM 12 does not store another problem to be solved (S15: NO), the provisional solution stored in the RAM 12 is replaced with the original problem. (S16), and the process ends.
[0047]
According to the above processing, the calculation for solving the test problem was performed with the initial provisional value being 14332 and the determination reference value being 14353. When the same problem was solved using the ISC method, an exact solution was obtained in 37 seconds according to the present invention, as compared with a case where an exact solution was not obtained in a calculation time of 220 seconds or more. . The obtained optimal solution is (000030000000 00531505500000503055 350004030), and the value of the maximized objective function is 14333.
[0048]
As described in detail above, in the present invention, when solving a discrete optimization problem, the degree of difficulty in solving the problem is determined, and the problem that is difficult to solve is divided into problems that are easier to solve. By solving a problem that is not difficult to solve using a modular method or an ISC method, it is possible to solve a problem efficiently and solve a problem that could not be solved conventionally. In addition, the discrete optimization problem can be solved in a short time and with a small memory capacity. Because it is possible to solve various discrete optimization problems at high speed and rigorously, it can be used in social activities such as optimal management method of goods in warehouse, scheduling of work, allocation of goods to be transported to transport equipment, and arrangement of equipment. Applying to various problems can improve the efficiency of social activities.
[0049]
In the present embodiment, an example of a problem in which maximization of an objective function is used as an optimization condition has been described. By using the lower bound of the objective function instead of the value and terminating the problem where the lower bound is greater than or equal to the provisional value, the lower bound can be used as a criterion for various determinations, and can be solved using similar processing. . In addition, the example in which the objective function and the constraint condition are linear functions has been described. However, it is needless to say that a problem using a nonlinear function can be solved, and the present invention is applied to a general discrete optimization problem. be able to.
[0050]
In the present embodiment, the problem dividing apparatus 1 having the function of the optimizing apparatus according to the present invention is configured using one computer having one CPU 11. The present invention is not limited to this, and may be configured using a computer having a plurality of CPUs 11, 11,..., Or configured by connecting a plurality of computers each having a CPU to each other. Is also good. The present invention is also applicable to a parallel computer constituted by using a plurality of CPUs or a plurality of computers as in this case, and each of the plurality of problems obtained by dividing the original problem is divided into a plurality of CPUs or a plurality of computers, respectively. , It is possible to solve the discrete optimization problem more quickly by performing parallel calculation using the present invention.
[0051]
Furthermore, in the present embodiment, the problem dividing device 1 of the present invention has been described as having the form of having the function of the optimizing device of the present invention. However, the present invention is not limited to this. An apparatus for solving a problem using the ISC method or the ISC method may be configured by separate computers, and the optimization apparatus of the present invention may be configured by mutually inputting and outputting data.
[0052]
【The invention's effect】
In the first, third, and seventh aspects of the present invention, when dividing a discrete optimization problem, the difficulty of solving the problem is determined, and the problem is solved by dividing the problem that is difficult to solve. It is easy to divide the original problem into problems.
[0053]
In the fourth and eighth inventions, a limit of a solution that can be obtained from the problem is obtained from the relaxation problem of the problem to be divided, and the limit does not fall within a predetermined range including the optimal solution of the original problem. By determining that a problem is a problem that is difficult to solve, it is possible to divide a problem that is difficult to solve due to a wide range in which to search for an optimal solution from among possible solutions.
[0054]
In the fifth and ninth inventions, when selecting an active variable to be fixed in order to divide a problem, a real optimal value of an objective function obtained from a relaxation problem in which one of the active variables is fixed to each of possible values. For the value, by selecting the active variable that minimizes the difference between the minimum value and the maximum value of the real optimal value obtained when the value is changed, the change in the value of the objective function is small, and the value of the active variable is changed. Problems that are difficult to find the optimal value can be divided.
[0055]
In the second, sixth, and tenth aspects, a discrete optimization problem can be efficiently solved by dividing a problem that is difficult to solve and solving a problem that is not difficult. In addition, since it is possible to solve general discrete optimization problems at high speed and strictly, optimal management method of goods in warehouse, scheduling of work, allocation of goods to be transported to transport equipment, arrangement of equipment, etc. The present invention has excellent effects, for example, it can be applied to various problems in social activities to improve the efficiency of social activities.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a problem dividing apparatus according to the present invention.
FIG. 2 is a table showing parameters of a test question.
FIG. 3 is a flowchart showing a procedure of a problem dividing method and an optimizing method of the present invention performed by the problem dividing apparatus of the present invention.
FIG. 4 is a flowchart showing a subroutine of a difficulty level determination process in step S7.
FIG. 5 is a flowchart showing a subroutine of a selection process in step S9.
FIG. 6 is a flowchart illustrating a procedure of a branch and bound method.
FIG. 7 is a conceptual diagram showing an outline of a branch and bound method.
[Explanation of symbols]
1 Problem dividing device
11 CPU (arithmetic unit)
12 RAM (storage unit)
2 Recording media
20 Computer programs

Claims (10)

Using a computer equipped with a storage unit and a calculation unit, find an optimal combination of the values of the variables that maximize or minimize the value of the objective function including a plurality of discrete variables under one or a plurality of constraints. When solving a discrete optimization problem, by fixing the value of any variable, the original problem to be solved is divided into multiple subproblems,
One problem that is an original problem or a partial problem that has a possibility of obtaining an optimal solution of the original problem is stored in the storage unit,
The arithmetic unit determines whether it is difficult to solve the problem stored in the storage unit,
When it is determined that it is difficult to solve the problem, for the problem, among the one or more discrete variables whose values are not fixed, one of the variables is selected by the calculation unit,
A problem dividing method, wherein the selected variable is fixed to each of a plurality of possible values, so that the operation unit divides the problem into a plurality of problems and stores the divided problems in a storage unit. Using a computer equipped with a storage unit and a calculation unit, find an optimal combination of the values of the variables that maximize or minimize the value of the objective function including a plurality of discrete variables under one or a plurality of constraints. When solving a discrete optimization problem, the original problem to be solved is divided into a plurality of partial problems by an arithmetic unit and stored in a storage unit by fixing values of arbitrary variables, and each of the partial problems is calculated. In the optimization method for finding the optimal solution of the original problem by solving in the section,
The provisional solution of the original problem is stored in the storage unit,
One or more problems to be solved, which are original problems or partial problems, are stored in the storage unit,
One of a plurality of questions stored in the storage unit is selected by the calculation unit from the one or more problems,
For the selected problem, the operation unit determines whether there is a possibility that an optimal solution of the original problem can be obtained by solving the problem,
If it is determined that there is no possibility that the optimal solution of the original problem can be obtained, stop handling the problem in the arithmetic unit,
When it is determined that there is a possibility that an optimal solution of the original problem can be obtained, the operation unit determines whether it is difficult to solve the problem,
If it is determined that it is not difficult to solve the problem, an optimal solution of the problem is obtained by a calculation unit by a predetermined solution,
Determined by the computing unit whether the obtained optimal solution of the problem is more optimized than the provisional solution,
When it is determined that it is more optimized than the provisional solution, the optimal solution of the problem is stored in the storage unit as a new provisional solution,
When it is determined that it is difficult to solve the problem, for the problem, among the one or more discrete variables whose values are not fixed, one variable is selected in the calculation unit,
By fixing the selected variable to each of a plurality of possible values, the operation unit divides the problem into a plurality of problems,
A plurality of problems generated by the division are stored in the storage unit as a new problem to be solved, and the processing is repeated in the storage unit and the calculation unit until there are no more problems to be solved stored in the storage unit.
An optimization method characterized by storing a temporary solution stored in a storage unit as an optimal solution of an original problem in a storage unit when there are no more problems to be solved. When solving a discrete optimization problem that seeks the optimal combination of the values of the variables that maximize or minimize the value of the objective function including a plurality of discrete variables under one or more constraints, In a device that divides the original problem to be solved into multiple subproblems by fixing the value,
Means for storing a problem that is an original problem or a partial problem, which has a possibility of obtaining an optimal solution of the original problem;
Difficulty determining means for determining whether it is difficult to solve the stored problem,
When it is determined by the difficulty determination unit that it is difficult to solve the problem, a selection is made to select one variable from one or a plurality of discrete variables whose values are not fixed for the problem. Means,
Means for dividing the problem into a plurality of problems by fixing the selected variable to each of a plurality of possible values. The difficulty level determination means includes:
Means for determining the upper or lower bound of the objective function obtained from the real optimal solution of the relaxation problem of the problem, corresponding to whether the optimization condition is maximization or minimization of the objective function,
Means for determining whether the obtained upper bound value or lower bound value is within a predetermined range including the optimal solution of the original problem,
The apparatus according to claim 3, further comprising: a unit that determines that it is difficult to solve the problem when it is determined that the upper bound value or the lower bound value does not fall within the predetermined range. Problem splitter. The selecting means,
For each of a plurality of discrete variables whose values are not fixed, the values are obtained from real real optimal solutions that solve each of the relaxation problems of a plurality of problems obtained by fixing the variables to a plurality of possible values. Means for determining a plurality of real optimum values of the objective function to be obtained;
For each of the variables, means for calculating the difference between the minimum value and the maximum value of the plurality of real number optimum values obtained,
5. The problem dividing apparatus according to claim 3, further comprising: a unit that selects, from among the plurality of variables, a variable in which the obtained value of the difference is the smallest. When solving a discrete optimization problem that seeks the optimal combination of the values of the variables that maximize or minimize the value of the objective function including a plurality of discrete variables under one or more constraints, By fixing the value, the original problem to be solved is divided into a plurality of subproblems, and in the optimization apparatus for finding the optimal solution of the original problem by solving each of the partial problems,
Means for storing provisional solutions to the original problem;
Means for storing one or more problems to be solved, which are the original or partial problems;
Means for selecting one of the stored one or more questions;
Means for determining whether or not there is a possibility that an optimal solution to the original problem can be obtained by solving the selected problem,
Means for terminating the problem if it is determined that there is no possibility of obtaining an optimal solution of the original problem;
When it is determined that there is a possibility that an optimal solution of the original problem can be obtained, a difficulty determination unit that determines whether it is difficult to solve the problem,
A means for obtaining an optimal solution of the problem by a predetermined solution, when it is determined by the difficulty determination means that it is not difficult to solve the problem,
Means for determining whether the obtained optimal solution of the problem is more optimized than the provisional solution,
Means for storing the optimal solution of the problem as a new provisional solution when it is determined that the solution is more optimized than the provisional solution,
When it is determined by the difficulty determination unit that it is difficult to solve the problem, a selection is made to select one variable from one or a plurality of discrete variables whose values are not fixed for the problem. Means,
Means for dividing the problem into a plurality of problems by fixing the selected variable to each of a plurality of possible values;
Means for storing a plurality of problems generated by the division as new problems to be solved;
Means to repeat the process until there are no more problems to solve;
Means for making a provisional solution stored when there are no more problems to be solved as an optimal solution of the original problem. When causing the computer to solve a discrete optimization problem that seeks an optimal combination of the values of the variables that maximize or minimize the value of the objective function including a plurality of discrete variables under one or more constraints, In a computer program that divides the original problem to be solved into a plurality of subproblems by fixing the values of arbitrary variables,
A difficulty determination procedure for causing the computer to determine whether it is difficult to solve one stored problem that is an original problem or a partial problem, which has a possibility of obtaining an optimal solution of the original problem,
When the computer determines that it is difficult to solve the problem, for the problem, one or more discrete variables whose values are not fixed, a selection procedure for selecting one variable,
Causing the computer to fix the selected variable to each of a plurality of possible values, thereby dividing the problem into a plurality of problems. The difficulty level determination procedure includes:
A procedure for causing a computer to obtain an upper bound or a lower bound of an objective function obtained from a real optimal solution of the relaxation problem of the problem corresponding to whether the optimization condition is maximization or minimization of the objective function. When,
A procedure for causing the computer to determine whether the obtained upper or lower bound value is within a predetermined range including the optimal solution of the original problem, and
8. A procedure for causing a computer to determine that it is difficult to solve the problem when it is determined that the upper bound value or the lower bound value is not within the predetermined range. Computer program described in 1. The selection procedure includes:
For each of a plurality of discrete variables whose values are not fixed, the computer calculates a real optimal solution that solves each of the relaxation problems of the plurality of problems obtained by fixing the variables to each of a plurality of possible values. A procedure for calculating a plurality of real optimal values of the objective function obtained from each of them,
A procedure for causing the computer to determine a difference between a minimum value and a maximum value of the plurality of real numbers obtained, for each of the variables,
The computer program according to claim 7, further comprising: causing a computer to select a variable having a minimum value of the obtained difference from a plurality of the variables. When causing the computer to solve a discrete optimization problem that seeks an optimal combination of the values of the variables that maximize or minimize the value of the objective function including a plurality of discrete variables under one or more constraints, By fixing the value of an arbitrary variable, the original problem to be solved is divided into a plurality of subproblems, and a computer program for obtaining an optimal solution of the original problem by solving each of the partial problems,
Causing the computer to select one of the memorized one or more problems, which is the original problem or the partial problem,
A procedure for causing a computer to determine whether or not there is a possibility that an optimal solution of an original problem can be obtained by solving the selected problem,
If the computer determines that there is no possibility of obtaining the optimal solution of the original problem, a procedure for terminating the problem,
Computer, if it is determined that there is a possibility that the optimal solution of the original problem can be obtained, a difficulty determination procedure for determining whether it is difficult to solve the problem,
If the computer determines that solving the problem is not difficult, a procedure for obtaining an optimal solution to the problem by a predetermined solution,
A procedure for causing the computer to determine whether or not the obtained optimal solution of the problem is more optimized than the provisional solution stored,
A step of, when it is determined that the computer is more optimized than the provisional solution, storing the optimal solution of the problem as a new provisional solution,
When the computer determines that it is difficult to solve the problem, for the problem, one or more discrete variables whose values are not fixed, a selection procedure for selecting one variable,
A step of causing the computer to divide the problem into a plurality of problems by fixing the selected variable to each of a plurality of possible values;
A step of causing the computer to store the plurality of problems generated by the division as a new problem to be solved,
Steps to make the computer repeat the process until there are no more problems to solve;
Causing the computer to make the provisional solution stored when there are no more problems to be solved the optimal solution of the original problem.

Images