Abstract
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.
Acknowledgments
We are grateful to the reviewers for their valuable comments and suggestions, which helped us to improve the paper.
Disclosure statement
No potential conflict of interest was reported by the authors.
Notes
2 The source codes of the HSM algorithm will be publicly available at the GitHub page.