トランスピュータネットワークにおける0－1ナップサック問題の分枝限定解法

• Item type: SIG Technical Reports(1)
• 公開日: 1991-07-17
• タイトル: トランスピュータネットワークにおける0－1ナップサック問題の分枝限定解法
• タイトル / 言語: en
• タイトル: Parallel Branch -and- Bound Algorithms for solving 0 - 1 Knapsack Problems on a Transputer Network
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学工学部
• 著者所属: 広島大学工学部
• 著者所属: 広島大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者名: 梶田, 哲史; 渡辺, 敏正; 翁長, 健治
• 著者名(英): Satoshi, Kajita; Toshimasa, Watanabe; Kenji, Onaga
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿の目的は，0?1ナップサック問題に対する疎結合並列計算機環境下での並列分枝限走解法において，節点探索法の違いや変数選択法の違いが計算時間，加速率等にいかなる影響を与えるかを調べることである．即ち，0?1ナップサック最大化問題をメッシュ型結合のトランスピュータネットワーク上で並列計算する場合の総計算時間及び加速率が，（） 分枝節点の探索ルール，（） 分枝変数の選択ルール，等によってどのような影響を受けるがを詳細に調べることを目的としている．本稿では，分枝節点探索ルールとしては従来からの （） 上界値最大節点を選択する Best upper?bound選択，（） 深さ最大節点を選択する Depth?first選択，を用いる．分枝変数選択ルールとしては，（） 子節点の上界値極大の変数選択，（） LP最適解を利用したピポット変数選択，(） 単価最大の未固定変数選択，なる既存の3つのルールに加えて，[13]で提案されている（）より大きな下界値を生成する変数選択，なる選択ルールを採用し，これらの探索/分枝ルールの組合せの下での実験結果に基づき解析を行う．また，探索節点選択ルールによっては得意，不得意なデータパターンが存在すると考えられるので，問題のパターンと探索ルールの関係についても解析をする．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The subject of the paper is to analyze how node-search and variable-selection strategies affect computation time and speedup of parallel branch-and-bound algorithms for solving 0-1 knapsack problems on a mesh-connected transputer network. There are two kinds of choice in a branch-and-bound algorithm: node(subproblem)-serching; variable selection. We adopt the following two rules of node-searching: (1) Best upper-bound rule; (2) Depth first rule. As variable-selection rules, there are three rules existing; (i) variables giving a maximal upper bound, (ii) pivoting-variables in LP relaxation, (iii) maximum unit-cost variables. In addition we consider the following rule which is proposed in our previous paper: (iv) variables producing a better lower bound. Experimental analyses with respect to these rules of node-searching / variable-selection are given.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 情報処理学会研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 1991, 号 61(1991-HPC-037), p. 67-74, 発行日 1991-07-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会