A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
研究了带冲突图的背包问题，提出一种新的分支定界算法，在短时间内求得最优解，实验表明在图密度10%及以上时优于现有方法和通用求解器。
We study the knapsack problem with conflict graph (KPCG), an extension of the 0-1 knapsack problem, in which a conflict graph describing incompatibilities between items is given. The goal of the KPCG is to select the maximum profit set of compatible items while satisfying the knapsack capacity constraint. We present a new branch-and-bound approach to derive optimal solutions to the KPCG in short computing times. Extensive computational experiments are reported showing that, for instances with graph density of 10% and larger, the proposed method outperforms a state-of-the-art approach and mixed-integer programming formulations tackled through a general purpose solver. The online supplement is available at https://doi.org/10.1287/ijoc.2016.0742 .