Bi-objective knapsack problem with conflicts

Abstract In this work we propose a bi-objective variant of the well-known 0/1 Knapsack Problem, that finds application in cases in which some item pairs may be seen as mutually conflicting. Previous variants considered in this scenario proposed to either avoid all conflicts, or to deal with them by considering the payment of appropriate penalty costs. We propose a different approach where the maximization of the profit and the minimization of the accepted conflicts are considered two different objective functions. We aim at identifying all Pareto-optimal solutions, so that a decision maker may choose a posteriori the optimal trade-off. We propose an exact resolution method based on the -constraint approach. Computational results on a wide set of instances show that our approach can be used in practice to identify and analyze their Pareto front.