PCクラスタにおける混合整数計画問題の並列処理とその性能評価

• Item type: SIG Technical Reports(1)
• 公開日: 2004-09-13
• タイトル: PCクラスタにおける混合整数計画問題の並列処理とその性能評価
• タイトル / 言語: en
• タイトル: Parallel Processing of Mixed Integer Programming Problem on PC Cluster and Its Performance Evaluation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島市立大学情報科学部
• 著者所属: NECフィールディング株式会社
• 著者所属: 広島市立大学大学院情報科学研究科
• 著者所属: 広島市立大学情報科学部
• 著者所属(英): en
• 著者所属(英): Faculty of Information Sciences, Hiroshima City Unievrsity
• 著者所属(英): en
• 著者所属(英): NEC Fielding, Ltd.
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Faculty of Information Sciences, Hiroshima City Unievrsity
• 著者名: 田村, 慶一; 岩木, 稔; 高木, 允; 北上, 始
• 著者名(英): Keiichi, Tamura; Minoru, Iwaki; Makoto, Takaki; Hajime, Kitakami
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 線形計画問題の一部の変数に対して整数制約を加えた問題を混合整数計画問題という．本論文では，分枝限定法と単体法を用いた混合整数計画問題解法の PC クラスタにおける並列化手法を提案する．混合整数計画問題の並列処理にはタスク分割によるマスタワーカモデルを使用する．並列化で課題となったのが負荷の偏りと総探索ノード数の増加である．負荷の偏りに関してはタスク奪い取りによる動的負荷分散手法を用い，総探索ノード数の増加に関しては暫定解の同期をおこない，課題を解決する．提案する並列化手法を実際に実装し，PCクラスタ上で性能評価をおこなった．性能評価により，提案する並列化手法で十分な台数効果が得られることを確認した．
• 論文抄録(英) / 内容記述タイプ: 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 load-balancing and increasing the total number of search nodes. To overcome the first problem, a task-steal-based dynamic load balancing technique 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 good speed-up.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 2004, 号 92(2004-MPS-051), p. 25-28, 発行日 2004-09-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会