| 講演名 | 1995/4/28 分枝限定法の並列化と並列計算機での実行 宮本 隆宏, 岩崎 一彦, 萩原 兼一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 分枝限定法はNP困難な組み合わせ最適化問題を解く有効な手段として知られている.ナップサック問題を題材として,分枝限定法の並列アルゴリズムを提案する.部分問題の分割や問題送信順序を工夫した.MIMD型の並列計算機iPSC/860(8PE)及びKSR1(32PE)上にそのアルゴリズムを適用して実行した.iPSC/860(8PE)上のプログラムで平均倍率(100問題)は7.25倍となった.KSR1上のプログラムの平均倍率(100問題)は2PEで2.04倍,32PEで15.48倍となった.その結果並列化アルゴリズムの有効性が確かめられた. |
| 抄録(英) | Branch-and-bound algorithm is known to be an effective method to slove NP-hard combinational optimization problems such as knapsack problems. We propose parallel branch-and-bound algorithms for knapsack problems and work out some ideas. Those algorithms are applied to MIMD-type parallel computers (iPSC/860, KSR1). The average ratios of 100 example problems are 7.25 on iPSC/860(8PEs), 2.04 on KSR1(2PEs), and 15.48 on KSR1(32PEs) respectively. Proposed argorithms are shown to be effective. |
| キーワード(和) | ナップサック問題 / 分枝限定法 / iPSC/860 / KSR1 |
| キーワード(英) | knapsack problems / branch-and-bound / iPSC/860 / KSR1 |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | CPSY |
|---|---|
| 開催期間 | 1995/4/28(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Computer Systems (CPSY) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 分枝限定法の並列化と並列計算機での実行 |
| サブタイトル（和） | |
| タイトル（英） | Parallel Branch-and-Bound Algorithms and Their Application to Parallel Computers |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ナップサック問題 / knapsack problems |
| キーワード(2)（和/英） | 分枝限定法 / branch-and-bound |
| キーワード(3)（和/英） | iPSC/860 / iPSC/860 |
| キーワード(4)（和/英） | KSR1 / KSR1 |
| 第 1 著者 氏名（和/英） | 宮本 隆宏 / Takahiro Miyamoto |
| 第 1 著者 所属（和/英） | 千葉大学工学部情報工学科 Chiba University, Faculty of Engineering |
| 第 2 著者 氏名（和/英） | 岩崎 一彦 / Kazuhiko Iwasaki |
| 第 2 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Osaka University, Faculty of Scientific Engineering |
| 第 3 著者 氏名（和/英） | 萩原 兼一 / Ken'ichi Hagihara |
| 第 3 著者 所属（和/英） | 大阪大学基礎工学部情報工学科 Osaka University, Faculty of Scientific Engineering |
| 発表年月日 | 1995/4/28 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 21 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |