We study the Knapsack Problem with Conflict Graph (KPCG), a generalization of the Knapsack Problem in which a conflict graph specifies pairs of items (vertices of the graph) which cannot be simultaneously selected in a solution. The KPCG asks for determining a maximum-profit subset of items of total weight no larger than the knapsack capacity which do not violate any of the item conflicts. In this work, we propose a novel combinatorial branch-and-bound algorithm for the KPCG based on an $n$-ary branching scheme. Our algorithm effectively combines different procedures for pruning the branch-and-bound nodes based on different relaxations of the KPCG. Key to the algorithm is its high pruning potential and the low computational effort that it requires to process each branch-and-bound node. An extensive set of experiments carried out on the benchmark instances typically used in the literature shows that, for edge densities ranging from 0.1 to 0.9, our algorithm is faster by up to two orders of magnitude than the state-of-the-art method and by up to several orders of magnitude than a state-of-the-art mixed-integer linear programming solver.
Article
View A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflict Graph