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

• Item type: SIG Technical Reports(1)
• 公開日: 2003-09-19
• タイトル: 最小重み点被覆問題に対する並列分枝限定法の性能評価
• タイトル / 言語: en
• タイトル: Performance Evaluation of Parallel Branch -and- Bound Algorithms for the Weighted Vetex Cover Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学大学院工学研究科
• 著者所属: 広島大学大学院工学研究科
• 著者所属: 広島大学大学院工学研究科
• 著者所属: 広島大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者名: 下田, 善隆; 高藤, 大介; 田岡, 智志; 渡邉, 敏正
• 著者名(英): Yoshitaka, Shimoda; Daisuke, Takafuji; Satoshi, Taoka; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 分枝限定法は，さまざまな組合わせ最適化問題を解くための最も一般的な解法である，が問題サイズの増加にともない計算時間が指数関数的に増加する．そのため，計算時間短縮を意図した並列化が考えられる．分枝限定法においては，分枝の早い段階においてり最適解に近い暫定解が得られれば，枝刈りが早く起こる可能性が高くなり計算回数を減らすこと，すなわち，解法の高速化につながる．そこで，上界値計算に高性能な既存近似解法を用いることによって計算回数が減少され，計算時間の短縮が期待できる．また，分枝限定法には，問題中のどの変数を固定するか（分枝変数選択）の選択がある．本稿では，最小重み点被覆問題に対するPCクラスタ上での並列分枝限定法について，上界値計算における近似解法の効果，分枝変数選択の効果を計算機実験により検証する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2003, 号 92(2003-AL-091), p. 51-58, 発行日 2003-09-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会