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.