收缩背包问题的并行分枝界限算法  

A PARALLEL BRANCH AND BOUND ALGORITHM FOR COLLAPSING KNAPSACK PROBLEM

作　　者：陈国良[1] 吴明[1] 顾钧[2] 

机构地区：[1]中国科学技术大学计算机科学与技术系,合肥230027 [2]香港科技大学

出　　处：《计算机研究与发展》2001年第6期741-745,共5页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展规化项目基金资助!(G19980 3 0 40 3 )

摘　　要：收缩背包问题 (collapsing knapsack problem,CKP)是 0 - 1背包问题的变体 ,其中背包的容量为所装物品数量的非增函数 ,针对并行计算的需要 ,在对 CKP问题分解的基础上 ,给出了求解每个子问题的分枝界限算法 ;提出了基于 MIMD- DM的收缩背包问题的并行分枝界限算法 ;并在曙光 10 0 0上设计和实现了该算法 ,以消息传递方式来解决子算法最优解的播送问题 ,同时给出了子问题的求解顺序 。The collapsing knapsack problem (CKP) is the transformation of the standard 0-1 knapsack problem. The capacity of its knapsack is the non-increasing function of the number of items loaded in it. For the need of parallel computation, an effective branch and bound algorithm is put forward to solve each sub CKP problem based on the partition of CKP. And then the parallel branch and bound algorithm of CKP is presented, which is based on MIMD-DM model. The design and implementation of this algorithm on Dawning-1000, a parallel machine, is also given. The optimal solution of each sub CKP problem is sent by message passing among different nodes. Meanwhile, the solving sequence of sub CKP problems is shown and the recursion depth in the process of solving problems and the system communication spending and their effect on the speed-up line are also discussed.

关 键 词：收缩背包问题 并行分枝界限算法 计算机 NP问题 

分 类 号：O22[理学—运筹学与控制论] TP301.6[理学—数学]