A New Algorithm for the 0-1 Knapsack Problem

We present a new algorithm for the optimal solution of the 0-1 Knapsack problem, which is particularly effective for large-size problems. The algorithm is based on determination of an appropriate small subset of items and the solution of the corresponding “core problem”: from this we derive a heuristic solution for the original problem which, with high probability, can be proved to be optimal. The algorithm incorporates a new method of computation of upper bounds and efficient implementations of reduction procedures. The corresponding Fortran code is available. We report computational experiments on small-size and large-size random problems, comparing the proposed code with all those available in the literature.

• 저널Management Science · 34(5) · 633–644
• 토픽Optimization and Packing Problems · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.34.5.633
• 저자Silvano Martello, Paolo Toth