Cardinality constrained 0-1 Knapsack problems

Abstract

The Knapsack Problem is one of the most important problems in Discrete optimization. Although it is the simplest integer program, it has numerous practical applications and often appears as a subproblem in solving more complicated problems. Inspired by recent research results we take a closer look at a new emerging problem , the cardinality constrained 0- 1 knapsack problem. If one knows the cardinality (i.e. the number of items packed into the knapsack) of an optimal solution one can solve the equivalent problem where the cardinality constraint is an equality constraint. We propose an exact algorithm based on Lagrangian relaxation for this problem. We introduce a specialized iterative, but finite, technique for determining the optimal Lagrange multipliers and report on the results of numerical experiments with our algorithm.