A novel dynamic programming heuristic for the quadratic knapsack problem

M. Eliass Fennich, Franklin Djeumou Fomeni and Leandro C. Coelho

European Journal of Operational Research, 2024, vol. 319, issue 1, 102-120

Abstract: The Quadratic Knapsack Problem (QKP) is a well-studied combinatorial optimization problem with practical applications in various fields such as finance, logistics, and telecommunications. Despite its longstanding interest, the QKP remains challenging due to its strong NP-hardness. Moreover, recent studies have introduced new instances where all existing algorithms have failed to produce good-quality results. In this paper, we aim to address these challenging QKP instances by proposing a novel approach to enhance the regular value function used in dynamic programming (DP) literature. Our proposed method considers the contribution of each item not only with respect to the items already selected, but also estimates its potential contribution with respect to items yet to be considered. Additionally, we introduce a propagation technique and a “remove-and-fill-up” local search procedure to further improve the solution quality. Through extensive computational experiments, our heuristic algorithm demonstrates superior performance compared to existing heuristics, producing optimal or near-optimal solutions for even the most demanding QKP instances. Empirical evidence, supported by an automated instance space analysis using unbiased metrics, showcases the remarkable improvements achieved, with solutions surpassing on average the solution quality of existing algorithms by up to 98%, and up to 77% reduction of the computational time.

Keywords: Combinatorial optimization; Dynamic programming; Heuristics; Binary quadratic problems; Quadratic knapsack problem (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724005149
Full text for ScienceDirect subscribers only

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:eee:ejores:v:319:y:2024:i:1:p:102-120

DOI: 10.1016/j.ejor.2024.06.034

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().