Computer Sciences Dept.

Parallel Solution of Extremely Large Knapsack Problems

Michael C Ferris

We shall describe a parallel algorithm for solving the knapsack feasibility problem, also known as the subset sum problem. The use of a random branching technique is described and its implementation on a parallel processor is discussed. Computational results show this to be an effective method for solving large problems. Using this approach we have solved problems with as many as 2 million variables in an average of 800 seconds on the Sequent Symmetry parallel processor. Furthermore, a coarse parallelization overcomes some of the problems that are present when serial algorithms are used to solve the knapsack problem.

Download this report (PDF)

Return to tech report index

Computer Science | UW Home