The Knapsack Problem with Conflicts: The Advantage of More than One Knapsack

The Knapsack Problem with Conflicts (KPC) is an extension of the classic Knapsack Problem (KP) that requires pairs of items that are in conflict cannot both be inserted into the knapsack. The KPC deals with one knapsack. Although we do not claim that this paper involves a new theory, this short paper will demonstrate for the first time in the operations research (OR) literature that there can be a significant advantage to using two knapsacks, but the advantage to using more than two knapsacks decreases rapidly. This is supported by an extensive empirical analysis solving 11,640 instances based on problems from the OR literature. The methodology of considering the advantage of using more than one knapsack when pairs of items can conflict has not been reported previously in the literature. Based on the authors’ personal experience, this information can be very useful to OR practitioners.