An expanding-core algorithm for the exact 0–1 Knapsack Problem

A new branch-and-bound algorithm for the exact solution of the 0–1 Knapsack Problem is presented. The algorithm is based on solving an ‘expanding core’, which initially only contains the break item, but which is expanded each time the branch-and-bound algorithm reaches the border of the core. Computational experiments show that most data instances are optimally solved without sorting or preprocessing a great majority of the items. Detailed program sketches are provided, and computational experiments are reported, indicating that the algorithm presented is not only shorter, but also faster and more stable than any other algorithm hitherto proposed.