組合せ最適化アルゴリズムの統一的枠組 : 木型計画法とその正当性

概要

論文の詳細を見る
組合せ最適化問題を解くための代表的手法として、分岐一界値法(Branc-and-Bound Method)、動的計画法、後戻り法(Backtrack Programming)などがあげられる。しかし、これらは、解法というよりは解法開発のための接近法とでも言うのが適当で、具体的な問題に応じた効果的解法を学習しておこうとすると極めて多数のアルゴリズムを習わねばならない。一方で、各接近法の原理だけを学習しても実用的な価値が乏しいという事情がある。しかも、NP完全性の検討によって、このような事態が暫定的たものとは考え難いことが強く示唆されている。この困難を打開する一方策として、原理的解法を問題に応じて具体化する技術を体系化すること、具体的には、各種接近法を包括する統一的枠組を確立し、その特定化の内容と得られる具体的アルゴリズムの効率の関係を明らかにすることが有効と考えられる。そこで本報告では、上記3つの接近法をはじめ、完全列挙法、解析解(例えば、フローショップ問題のジョンソン規則)、整数線形計画の切除平面法などをも含む"木型計画法"なる統一的枠組を提案し、その正当性一有限性と正確性(求められる解の良さ)一の分析を行った。木型計画法は選択則(列挙の順番を定める規則)、分岐則(問題をより易しい問題に分解する規則)、上界関数(列挙の各時点での最善解を判定するための道具)、廃棄則(最善解より良い解を持たない部分問題を発見しその後の列挙の対象からはずす規則)ならびに終了条件の5つの基本要素から構成される。列挙の対象が無限集合であっても良いこと列挙に重複が許されること、廃棄則の定義が包括的であることなどが、この枠組の特色と言える。正当性の分析は最も一般性の高い場合に対して行い、有限性と正確性のための十分条件を明らかにした。結果は、有限性については選択則と分岐則が、正確性については終了条件が支配的要因であることを示している。さらに、完全列挙法、分岐一界値法、動的計画法、加算的陰伏的列挙法および切除平面法を木型計画法として完式化しなおし、提案した枠組の汎用性を例示した。
社団法人日本オペレーションズ・リサーチ学会の論文
1981-03-00

著者

関口恭毅
北海道大学

組合せ最適化アルゴリズムの統一的枠組 : 木型計画法とその正当性

スポンサーリンク

概要

著者

関連論文

スポンサーリンク