多重選択ナップザック問題

概要

論文の詳細を見る
多重選択ナップザック問題は、通常の(連続形)ナップザック問題に多重選択条件を付したもので、つぎのように書かれる。P:目標関数[numerical formula]拘束条件[numerical formula]各iに対し、x_<ij>(j=1、2、…、m_i)のたかだか1個が正の値をとる。(4)ただし・n・m_iは正整数、a_<ij>、c_<ij>、bは正の実数である。この問題は、いわゆるNP完全族に属す難しいものであることが分かっており、一般的に多項式オーダーの計算量で最適解を得るアルゴリズムは存在しないと考えられている。本論文では、簡単な計算で得られる近似解法を提案するとともに、分枝限定法にもとづく厳密解法についても述べ、両者の理論的性質を調べ、その計算実験を行なった。その結果、本問題はNP完全族の中では比較的容易なものであることが分かった。両解法の基本は、Pの多重選択条件(4)を[numerical formula]に緩和して得られる線形計画問題P^^が簡単に解けるという事実にある。P^^の最適解x^^=(x^^_<11>x^^_<12>、…、xx^^_<nm_n>)は、そのままPの最適解でもあるか、あるいはただ1つのi=i^^に対し、連続するx<ij>^^^ー1、x<ij>^^^が正の値をとり他のiは(4)をみたすという性質をもっている。近似察法の第1怯x^^の変数x<ij>^^^_ー1、x<ij>^^^の一方を0に固定し、他方を条件(2)(3)の許す範囲の最大値に定めて得られる解の良い方をとるものである。係数を一様乱数から生成した問題では、n=1000、m_i=2程度の大規模な問題でも、FACOM230/60の1秒以下で、z^<(R)>/z^0≧0。9990をみたす良い近似解が得られている。ただし、z^<(R)>は近似解の値、z^0はPの最適値である。さらに、この近似解法の改良も検討され、より優れた計算結果を得ている。つぎに、厳密解を求める分枝限定法のアルゴリズムをつぎのように構成した。分解操作:各部分問題P_tに対しその線形計画問題P^^_tを解き、x<ij>^^^ー1、x<ij>^^^>0ならば、それぞれを0に固定して2個の部分問題を生成する。限定操作:P^^_tの値z^^_tの近似解の値z^<(R)>_tをそれぞれ上・下界値として限定操作を実行する。このアルゴリズムはきわめて効率良く動作し、前記の一様乱数から生成した問題では、n=500、m_i=2程度の問題でもFACOM M190を用いてO。1〜O。2秒で最適解が得られている。nに対する計算時間の増加も0(nlogn)程度である。しかし、意地悪く構成した難しい問題では、計算量がnの指数オーダで増加することも確かめられている。
社団法人日本オペレーションズ・リサーチ学会の論文

多重選択ナップザック問題

スポンサーリンク

概要

著者

関連論文

スポンサーリンク