An effective hybrid search method for the quadratic knapsack problem with conflict graphs
针对带冲突图的二次背包问题，提出一种基于模因算法的混合搜索方法，集成交叉算子、多邻域禁忌搜索和加速技术，在45个基准实例上找到3个改进的最优解并匹配其余所有已知最优解。
The quadratic knapsack problem (QKP) is a variant of the well-known knapsack problem and arises in a variety of real life applications. The quadratic knapsack problem with conflict graphs (QKPCG) further extends QKP by considering the conflicts of items. In this work, we propose an effective hybrid search method based on the framework of memetic algorithm to tackle QKPCG. The method integrates a randomized uniform-based crossover operator to generate promising offspring solutions, a multi-neighborhood tabu search to perform local optimization, and a streamline technique to speed up the evaluation of candidate solutions. The method shows a competitive performance compared to the state-of-the-art approaches in the literature. It finds 3 improved best-known solutions and matches the best-known solutions for all the remaining cases out of the 45 benchmark instances. We investigate the effects of the key ingredients of the algorithm.