PCクラスタにおける混合整数計画問題の並列処理とその性能評価 Parallel Processing of Mixed Integer Programming Problem on PC Cluster and Its Performance Evaluation

この論文にアクセスする

この論文をさがす

著者

抄録

線形計画問題の一部の変数に対して整数制約を加えた問題を混合整数計画問題という.本論文では,分枝限定法と単体法を用いた混合整数計画問題解法の PC クラスタにおける並列化手法を提案する.混合整数計画問題の並列処理にはタスク分割によるマスタワーカモデルを使用する.並列化で課題となったのが負荷の偏りと総探索ノード数の増加である.負荷の偏りに関してはタスク奪い取りによる動的負荷分散手法を用い,総探索ノード数の増加に関しては暫定解の同期をおこない,課題を解決する.提案する並列化手法を実際に実装し,PCクラスタ上で性能評価をおこなった.性能評価により,提案する並列化手法で十分な台数効果が得られることを確認した.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.

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.

収録刊行物

  • 情報処理学会研究報告数理モデル化と問題解決(MPS)

    情報処理学会研究報告数理モデル化と問題解決(MPS) 2004(92(2004-MPS-051)), 25-28, 2004-09-13

    一般社団法人情報処理学会

参考文献:  4件中 1-4件 を表示

各種コード

  • NII論文ID(NAID)
    110002914266
  • NII書誌ID(NCID)
    AN10505667
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    09196072
  • NDL 記事登録ID
    7120557
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-1121
  • データ提供元
    CJP書誌  NDL  NII-ELS  IPSJ 
ページトップへ