最小重み点被覆問題に対する並列分枝限定法の性能評価

スポンサーリンク

概要

論文の詳細を見る
分枝限定法は,さまざまな組合わせ最適化問題を解くための最も一般的な解法である,が問題サイズの増加にともない計算時間が指数関数的に増加する.そのため,計算時間短縮を意図した並列化が考えられる.分枝限定法においては,分枝の早い段階においてより最適解に近い暫定解が得られれば,枝刈りが早く起こる可能性が高くなり計算回数を減らすこと,すなわち,解法の高速化につながる.そこで,上界値計算に高性能な既存近似解法を用いることによって計算回数が減少され,計算時間の短縮が期待できる.また,分枝限定法には,問題中のどの変数を固定するか(分枝変数選択)の選択がある.本稿では,最小重み点被覆問題に対するPCクラスタ上での並列分枝限定法について,上界値計算における近似解法の効果,分枝変数選択の効果を計算機実験により検証する.
一般社団法人情報処理学会の論文
2003-09-19

著者

関連論文

もっと見る

スポンサーリンク