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

Qing Zhou, Jin-Kao Hao, Zhong-Zhong Jiang and Qinghua Wu

Journal of the Operational Research Society, 2024, vol. 75, issue 5, 1000-1010

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.

Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2023.2228339 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:75:y:2024:i:5:p:1000-1010

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2023.2228339

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().