An Algorithm for Large Zero-One Knapsack Problems

We describe an algorithm for the 0-1 knapsack problem (KP), which relies mainly on three new ideas. The first one is to focus on what we call the core of the problem, namely, a knapsack problem equivalent to KP, defined on a particular subset of the variables. The size of this core is usually a small fraction of the full problem size, and does not seem to increase with the latter. While the core cannot be identified without solving KP, a satisfactory approximation can be found by solving the associated linear program (LKP). The second new ingredient is a binary search-type procedure for solving LKP which, unlike earlier methods, does not require any ordering of the variables. The computational effort involved in this procedure is linear in the number of variables. Finally, the third new feature is a simple heuristic which under certain conditions finds an optimal solution with a probability that increases with the size of KP. Computational experience with an algorithm based on the above ideas, on several hundred randomly generated test problems with 1,000–10,000 variables and with coefficients ranging from between 10 and 100 to between 10 and 10,000, indicates that for such problems the computational effort grows linearly with the number of variables and less than linearly with the range of coefficients. Average time per problem was less than a second, and the maximum time for any single problem was 3 seconds. Value-independent 0-1 knapsack problems (also randomly generated), were solved with a specialized version of the code in less than one-third of the time required for general 0-1 knapsack problems. To conclude, we identify a class of hard knapsack problems.