多次元ナップサック問題の問題分割解法に関する研究
A Distributed Method for the Multidimensinal Knapsack Problem


近年、様々な研究分野において、利益の獲得及び環境負荷の低減を追求することが、これまで以上に強く求められている。 特に生産分野では、低コスト化、高効率化のために、生産に関する問題を定式化したものでもある「組合せ最適化問題」 を解く研究が盛んに行われている。しかし、組合せ最適化問題を解く上の問題点として、組合せ爆発が一般的に認知されている。 組合せ爆発により、最適解の獲得が不可能となるだけでなく、最適解の近似解さえも獲得することが非常に困難となる。 そこで、組合せ爆発を抑制し最適解の近似解を実時間で獲得することと、組合せ最適化問題全体に広く活用可能な方法等 のメタ知識を獲得することを研究目的とした。そして、2つ目の目的達成のために組合せ最適化問題の中で、より簡潔に定 式化可能な多次元ナップサック問題について研究を行った。

本研究では、組み合わせ爆発を抑制する方法として分割法を採用した。 問題分割により一度に取扱う変数を減少させることで、組み合わせ爆発の抑制が可能となる。 しかし、組み合わせ爆発の抑制と、得られる可能解の総数の減少は同義であるため、最適解やその近似解さえも発見できなくなる可能性が高い。 そこで、それらの解を復元するため、問題分割により生成された小問題間において制約条件の限界値を調整させる方法(分割解法)を実装した。 そして、分割解法を用いて60秒間で獲得した解と全探索を24時間行い獲得した解を比較する実験を行った。

実験結果より、要素数が多く制約条件数が少ない問題ほど、分割解法の解が、全探索の解を上回ることが多いことを確認した。 制約条件数が多い問題では24時間の解は下回るが、同じ60秒の計算時間で比較した場合では、 分割解法が有用であることを示す実験結果を多数確認できた。 また、実験結果の考察より、分割解法は制約条件数が少ない問題において有用であること、 分割解法の各段階への計算時間配分は問題の規模と問題分割数に柔軟に対応する必要があること、 小問題の規模が極小となる大規模な問題分割は有効ではないこと等のメタ知識が獲得された。

以上より、多次元ナップサック問題の最適解の近似解を実時間で獲得できたこと、組合せ最適化問題全体に広く活用可能な方法等のメタ知識を獲得できたことを結論つけた。


This page discribes a distributed method for the multidimensional knapsack problem suitable to obtain the approximate solution near the optimal solution within the real-time.
The method consists of four phases:
(i)partition the problem into sub-problems,
(ii)packing items in each small problems that generated by partition ,
(iii)fixing the solution obtained by leveraging some free spaces which have not packed items yet and
(iv)integrating all sub-problems.
The proposal method got solutions in 60 seconds above the solution with full search in 86400 seconds.
But,it is difficult that specific the number of partitions can generate the solution above full search one.