A Minimal Algorithm for the 0-1 Knapsack Problem

TLDR

Large‑size 0‑1 knapsack problems are solvable, but most computational effort is spent on sorting and reduction, and the exact core cannot be identified before optimality, forcing previous methods to use approximate core sizes. The authors aim to avoid this overhead by solving the knapsack problem on a minimal core consisting of a small subset of variables. They present a dynamic‑programming algorithm that lazily extends the core as needed and performs sorting and reduction only when required, with experiments on common data instances. Experiments show the method outperforms all known algorithms for the 0‑1 knapsack problem and yields highly stable solution times.

Abstract

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 indicate that the presented approach outperforms any known algorithm for KP, having very stable solution times.