2024-03-29T04:53:45Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000319082023-04-27T10:00:04Z01164:02592:02627:02629
最小重み点被覆問題に対する並列分枝限定法の性能評価Performance Evaluation of Parallel Branch -and- Bound Algorithms for the Weighted Vetex Cover Problemjpnhttp://id.nii.ac.jp/1001/00031908/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31908&item_no=1&attribute_id=1&file_no=1Copyright (c) 2003 by the Information Processing Society of Japan広島大学大学院工学研究科広島大学大学院工学研究科広島大学大学院工学研究科広島大学大学院工学研究科下田, 善隆高藤, 大介田岡, 智志渡邉, 敏正分枝限定法は,さまざまな組合わせ最適化問題を解くための最も一般的な解法である,が問題サイズの増加にともない計算時間が指数関数的に増加する.そのため,計算時間短縮を意図した並列化が考えられる.分枝限定法においては,分枝の早い段階においてり最適解に近い暫定解が得られれば,枝刈りが早く起こる可能性が高くなり計算回数を減らすこと,すなわち,解法の高速化につながる.そこで,上界値計算に高性能な既存近似解法を用いることによって計算回数が減少され,計算時間の短縮が期待できる.また,分枝限定法には,問題中のどの変数を固定するか(分枝変数選択)の選択がある.本稿では,最小重み点被覆問題に対するPCクラスタ上での並列分枝限定法について,上界値計算における近似解法の効果,分枝変数選択の効果を計算機実験により検証する.Even though a branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems, the computation time is likely to be exponential as the size of input increases. Parallelization is one way of improvement. We can expect that using a better upper bound makes bounding operations appear at early stages of computating, possibly resulting in short computation time. Here we consider using an approximation algorithm in computing an upper bound. In this paper, we experimentally evaluate how using an upper bound given by an existing approximation algorithm and variable selection strategies affect the computation time of a parallel BB for solving the minimun cost vertex cover problem on a PC cluster.AN1009593X情報処理学会研究報告アルゴリズム(AL)200392(2003-AL-091)51582003-09-192009-06-30