An effective hybrid search method for the quadratic knapsack problem with conflict graphs

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.

Keywords:

• Quadratic knapsack problem
• conflict graphs
• heuristics
• memetic framework
• tabu search

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

1 https://github.com/neteasefans/QKPCG.git

2 The source codes of the HSM algorithm will be publicly available at the GitHub page.

Additional information

Funding

This work was partially supported by the National Natural Science Foundation of China (Grant Nos. 72201053, 71971052), China Postdoctoral Science Foundation (Grant No. 2021M700716) and the Fundamental Research Funds for the Central Universities (Grant No. 2023GFZD01).