A novel dynamic programming heuristic for the quadratic knapsack problem

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.