Two Knapsacks Are Better than One for Both Soft and Hard Conflict Constraints

For the classic 0–1 knapsack problem, there can be pairs of items that are in conflict. In other words, either at most one item can be inserted into the knapsack (hard conflict constraint) from the conflict pair or there may be a penalty (soft conflict constraint) if both items in a conflict pair are inserted into the knapsack. The benefit of having two or more knapsacks when the conflict constraints are hard was recently demonstrated in the literature. By using 120 knapsack problem with forfeits (KPF) (soft constraints) from the literature and 40 new KPF instances with the Gurobi software, the purpose of this paper is simply to quantify the benefit of using two or more knapsacks for the KPF while the total capacity of the knapsacks is fixed. It will be shown that for the base case 40 KPF instances, the average objective function value improves by 37% when two knapsacks are used instead of one. More importantly, it is shown that increasing either knapsack capacity (64% improvement) or the number of conflict constraints (47% improvement) or both (49.7% improvement) results in even larger improvements in the objective function value. In contrast, going from two to three knapsacks, the improvement over all 160 KPF instances is only 12% and drops dramatically beyond three knapsacks. Finally, it will be shown that based on these 160 KPF instances, the KPF solutions with four knapsacks are essentially the same as the solutions with one knapsack with no forfeit constraints. This is the first time that the multiple knapsack problem with forfeits (MKPF) is discussed in the literature.