In many practical occurrences of knapsack problems additional requirements are im- posed on the structure of the optimal solution. A quite frequent and natural restric- tion concerns the number of items included in an optimal solution. Whenever the selection of items causes the explicit handling of goods or induces transaction costs not represented in the data of the knapsack instance, solutions with a small number of larger items will be preferred to a solution with a large number of smaller items.
The easiest way of representing this goal is the formulation of a cardinality constraint, i.e. an upper bound k on the number of packed items.
The resulting cardinality constrained knapsack problem or k-item knapsack problem is the following linear integer program:
where
- U. Pferschy, D. Pisinger, Knapsack Problems, 2004, DOI