Parallel and VLSI Implementation of the Knapsack Problem

Sanjay Rajopadhye

joint work with R. Andonov and V. Poirriez, Université de Valenciennes

The unbounded knapsack problem (UKP) is a classic NP hard, combinatorial optimization problem with a wide range of applications. It may be formulated as follows: we are given a knapsack of capacity c, into which we may put n types of objects. Each object of type i has a profit , p[i], and a weight w[i], (where w[i], p[i], n and c are all positive integers, and we have an unbounded number of copies of each object type). We seek to determine, for each i, the number x[i], of i -th type objects to be chosen so as to maximize the total profit without exceeding the capacity.

Since 1993 we have explored a number of aspects related to the efficient implementation of the dynamic programming (DP) algorithm for the UKP on dedicated VLSI architectures, general purpose parallel machines, and also on sequential machines (using algorithmic advances). The parallel software solution is described in Irisa techreport PI-740 and led to our recent work on tiling optimizations (see for example Irisa techreport PI-999). My ongoing work involves implementing our most efficient algorithm on FPGA based coprocessors. The three main results/papers on the UKP are summarized below: