WEKO3
-
RootNode
アイテム
PCクラスタにおける混合整数計画問題の並列処理とその性能評価
https://ipsj.ixsq.nii.ac.jp/records/17187
https://ipsj.ixsq.nii.ac.jp/records/171876d8bdf7c-aca6-4f19-824a-bb8ee9fe0fbc
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TOM4617007.pdf (864.1 kB)
|
Copyright (c) 2005 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2005-12-15 | |||||||
| タイトル | ||||||||
| タイトル | PCクラスタにおける混合整数計画問題の並列処理とその性能評価 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Parallel Processing of Mixed Integer Programming Problem on PC Cluster and Its Performance Evaluation | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | オリジナル論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 広島市立大学情報科学部 | ||||||||
| 著者所属 | ||||||||
| 広島市立大学情報科学部 現在，NEC フィールディング株式会社 | ||||||||
| 著者所属 | ||||||||
| 広島市立大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 広島市立大学情報科学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Information Sciences Hiroshima City University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Information Sciences Hiroshima City University,Presently with NEC Fielding, Ltd. | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences Hiroshima City University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Information Sciences Hiroshima City University | ||||||||
| 著者名 |
田村, 慶一
岩木, 稔
高木, 允
北上, 始
× 田村, 慶一 岩木, 稔 高木, 允 北上, 始
|
|||||||
| 著者名(英) |
Keiichi, Tamura
Minoru, Iwaki
Makoto, Takaki
Hajime, Kitakami
× Keiichi, Tamura Minoru, Iwaki Makoto, Takaki Hajime, Kitakami
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 線形計画問題の一部の変数に対して整数制約を加えた問題を混合整数計画問題という．本論文では，分枝限定法と単体法を用いた混合整数計画問題解法のPC クラスタにおける並列化手法を提案する．並列化には典型的なマスタワーカモデルを使用する．課題となったのが負荷の偏りと総探索ノード数の増加である．負荷の偏りに関してはタスク奪い取りによる動的負荷分散手法であるマスタ・タスク・ステイル法を用い，総探索ノード数の増加に関しては暫定解同期を行い，課題を解決する．提案する並列化手法を実際に実装し，PC クラスタ上で数値実験を行った．数値実験により，提案する並列化手法で2 つの課題を解決できていることを確認できた． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | A problem in which some variables of a linear programming problem can take only integer values and some variables can take fractional values is called a mixed-integer programming problem. The mixed-integer programming problem is solved using both the simplex method branch-and-bound algorithm. This paper proposes a parallelism of the mixed-integer programming problem on a PC cluster. The parallelism of the mixed-integer programming problem uses a task-divided-based master-worker model. There are two problems; inefficient loadbalancing and increasing the total number of search nodes. To overcome the first problem, a task-steal-based dynamic load balancing technique Master-Task-Steal method is used for the dynamic load balancing of master-worker model. To solve the second problem, we propose synchronous techniques of incumbent. We implemented parallel mixed-integer programming problem on an actual PC clusters. The experimental results show that the two problems are not occured. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464803 | |||||||
| 書誌情報 |
情報処理学会論文誌数理モデル化と応用（TOM） 巻 46, 号 SIG17(TOM13), p. 56-69, 発行日 2005-12-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7780 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
