A minimal algorithm for the 0–1 knapsack problem

Several types of large-sized 0–1 Knapsack Problems (KP) may be easily solved, but in such cases most of the computational effort is used for sorting and reduction. In order to avoid this problem it has been proposed to solve the so-called core of the problem: a Knapsack Problem defined on a small subset of the variables. The exact core cannot, however, be identified before KP is solved to optimality, thus, previous algorithms had to rely on approximate core sizes. In this paper we present an algorithm for KP where the enumerated core size is minimal, and the computational effort for sorting and reduction also is limited according to a hierarchy. The algorithm is based on a dynamic programming approach, where the core size is extended by need, and the sorting and reduction is performed in a similar ‘lazy’ way. Computational experiments are presented for several commonly occurring types of data instances. Experience from these tests indicates that the presented approach outperforms any known algorithm for KP, having very stable solution times.