全整数区間線型計画法の解法

概要

論文の詳細を見る
整数計画問題に対する切除平面法は、小規模問題に対しても計算の不安定性があるため現在一般に用いられていない。ここでは区間制約をもつ全整数線形計画問題を対象として、切除平面法(小数法)の安定化の試みがなされている。区間制約とする理由は0-1変数問題のように実用問題では区間制約の場合が多いので記憶容量の節約になること、また区間計画法や区間縮小法を用いて計算効率を高められるためである。区間線形計画法では列タブローを用いるが、目的関数ƒ=Σc^0_jx_jは係数が零のとき退化する。退化対策として、目的関数の初期係数に無限小乱数を加えたものƒ=Σ(c^0_j+εξ^0_j)x_jを用いる摂動法の考えを導入した。この考えは、初期計算表でc^0_jと乱数ξ^0_jを別々の行におき消去計算を独立に行い、途中の計算表ではc_jが零のときのみξ_jを考慮する辞書的方法と等価となる。ξ_jは実際上非零とみなされ、従って2次元ベクトル(c_j、ξ_j)^tについてのみ辞書的考慮すればよく、従来の多次元ベクトルを用いる方法に比し簡単なものとなっている。以上の方法にGomoryの小数カット法を組合せても切除平面法の改良にならない。一般にカットは発生を重ねるにつれ効果が弱まる。特に連続解が整数解に近づくにつれ、この傾向は加速度的となる。そこで最適化問題を満足化問題に変換して解の探索を行った。満足化問題では連続実行可能解が整数解に一致するまでカットの発生を続けることは必しも必要ではなく、連続解を丸めその実行可能性を調べることで計算量を減らすことができる。すなわち、第1ステップとして元の問題の連続緩和問題を解き、連続解に対する目的値ƒ^+を得る。これは整数実行可能解の上限ƒ^0=[ƒ^+]を与える。次に第2ステップとして、目的関数を制約式Σc^0_jx_j=ƒ^0とし、元の制約式に加えた部分問題の整数実行可能性を調べる。そのために、一つの変数x_hを人工目的関数とし、修正した最適化手法を用いている。この部分問題が実行不可能ならΣc^0_jx_j=ƒ^0-1と代えて整数解の探索を続けるのである。提案された方法の性能を調べるため、よく知られた29のテスト問題(規模1×10〜140×21)を用いた。従来の方法とピボット計算の回数で比較している。これらの中には従来の方法では収束しなかったものも含まれているが、この方法ではすべて収束し、29例のうち25例はパソコンで解いている。提案された方法は小規模問題に対し安定性があるように見えるが、大きい問題への応用は今後の課題である。
社団法人日本オペレーションズ・リサーチ学会の論文

全整数区間線型計画法の解法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク