| 講演名 | 2005-01-28 グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能評価 下田 善隆, 田岡 智志, 高藤 大介, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 分枝限定解法は, さまざまな組合わせ最適化問題を解くための最も一般的な解法であるが, 問題サイズの増加にともない計算時間が指数関数的に増加する.そのため, 計算時間短縮を意図した並列化が考えられている.分枝限定解法においては, 分枝の早い段階においてより最適解に近い暫定解が得られれば, 枝刈りが早く起こる可能性が高くなり計算回数を減らすこと, すなわち, 解法の高速化につながる.分枝限定解法には, 分枝木のどの節点(部分問題)で分枝を行うかの選択(分枝節点選択), 問題中のどの変数を固定するか(分枝変数選択)があり, これが解法の速度に影響している.また, 並列化の際には通信時間の増加防止等も考慮する必要があるため, どのような節点をどれだけ転送するか(転送節点選択)も重要となってくる.本研究では, グラフ彩色問題に対するPCクラスタ上での並列分枝限定解法に関して, 転送節点選択手法を提案し, その効果を計算機実験により検証する. |
| 抄録(英) | A branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported that the computation time of a parallel BB heavily depends upon node-variable selection strategies. And, in case of a parallel BB, it is also necessary to prevent increase in communication time. So, it is important to pay attention to how many and what kind of nodes are to be transferred (called sending-node selection strategy). In this paper, we propose some sending-node selection strategies and experimentally evaluate how these strategies affect computation time of a parallel BB on a PC cluster network. |
| キーワード(和) | 並列分枝限定解法 / 組合わせ最適化問題 / 最適解 |
| キーワード(英) | Parallel branch-and-bound algorithms / Combinatorial optimization problems / MPI / Optimum solutions |
| 資料番号 | COMP2004-68 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/1/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能評価 |
| サブタイトル（和） | |
| タイトル（英） | Performance Evaluation of PC Cluster-based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 並列分枝限定解法 / Parallel branch-and-bound algorithms |
| キーワード(2)（和/英） | 組合わせ最適化問題 / Combinatorial optimization problems |
| キーワード(3)（和/英） | 最適解 / MPI |
| 第 1 著者 氏名（和/英） | 下田 善隆 / Yoshitaka SHIMODA |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 高藤 大介 / Daisuke TAKAFUJI |
| 第 3 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 第 4 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 4 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2005-01-28 |
| 資料番号 | COMP2004-68 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 642 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |