A core approach to the 0–1 equality knapsack problem

Abstract

For the 0–1 knapsack problem with equality constraint a partitioning procedure is introduced which focuses on the core of the problem. The purpose of the procedure is to reduce the required preliminary sorting for large problem instances. Computational results are presented for an improved heuristic as well as for a complete (exact) algorithm showing the success of the core approach. Test problems of size up to 15–000 objects are solved within 400–ms on a standard personal computer, that is, within the time that is needed for sorting the profit-weight ratios. The core algorithm reduces the solution times by a factor of up to four for large problem instances.

Keywords:

• knapsack problem
• integer programming
• heuristics