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

收缩背包问题（collapsing knapsack problem,CKP)是0－1背包问题的变体，其中背包的容量为所装物品数量的非增函数，针对并行计算的需求，在对CKP问题分解的基础上，给出了求解每个子问题的权分枝界限算法，提出了基于MIMD－DM的收缩背包问题的并行分枝界限算法；并在曙光1000上设计和实现了该算法，以消息传递方式来解决子算法最优解的播送问题，同时给出了子问题的求解顺序，讨论了问题求解过程中的递归深度和系统的通信开销对加速比曲线的影响。

A PARALLEL BRANCH AND BOUND ALGORITHM FOR COLLAPSING KNAPSACK PROBLEM

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.