On Solving the Knapsack Problem with Conflicts

Abstract

A variant of the well-known Knapsack Problem is studied in this paper. In the classic problem, a set of items is given, with each item characterized by a weight and a profit. A knapsack of a given capacity is provided, and the problem consists of selecting a subset of items such that the total weight does not exceed the capacity of the knapsack, while the total profit is maximized. In the variation considered in the present work, pairs of items are conflicting, and cannot be selected at the same time. The resulting problem, which can be used to model several real applications, is considerably harder to approach than the classic one. In this paper, we consider a mixed-integer linear program representing the problem and we solve it with a state-of-the-art black-box software. A vast experimental procedure on the instances available from the literature, and adopted in the last decade by the community, indicates that the approach we propose achieves results comparable with, and in many cases better than, those of state-of-the-art methods, notwithstanding that the latter are typically based on more complex and problem-specific ideas and algorithms than the idea we propose.