A partitioning scheme for solving the exact K-item 0-1 knapsack problem

Abstract

Our investigation on the impact of partitioning the search space of the classical 0- 1 Knapsack Problem through the inclusion of equality constraints on the knapsack's cardinality, has given rise to the study we undertook on solving the Exact k-item 0- 1 Knapsack Problem (EKP) and proving optimality. This problem also arises in the solution of real-life cutting stock problems by column generation in which the number of pieces cut from each stock is limited by the number of knives available. In this paper we explore a partitioning scheme on the Exact k-item 0- 1 Knapsack Problem. We introduce equality constraints on the number of items outside the break solution, which must be selected for inclusion into the knapsack. This can be seen as constraint disaggregation. As a result of this, we do a forest search, i.e. instead of searching one tree, more trees (in general) are searched. We present results of numerical experiments.