The quadratic knapsack problem is a relevant NP-hard combinatorial optimization problem, inspired, since the Seventies, by a number of real-world applications. After its formal definition in 1980, it was subject to intensive research, especially in the last two decades. No recent review on this problem appeared in the literature after a well-known survey, published in 2007 but updated to 2003. The purpose of this work is to provide a thorough overview of classical and recent results on the quadratic knapsack problem. We examine mathematical models, linearizations and reformulations. We review upper bounds, exact algorithms, heuristic and metaheuristic approaches, and provide a comparison of their computational performance.
Galli, L., Martello, S., Toth, P. (2025). The quadratic knapsack problem. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, On line first, 1-12 [10.1016/j.ejor.2024.12.032].
The quadratic knapsack problem
Galli L.;Martello S.
;Toth P.
2025
Abstract
The quadratic knapsack problem is a relevant NP-hard combinatorial optimization problem, inspired, since the Seventies, by a number of real-world applications. After its formal definition in 1980, it was subject to intensive research, especially in the last two decades. No recent review on this problem appeared in the literature after a well-known survey, published in 2007 but updated to 2003. The purpose of this work is to provide a thorough overview of classical and recent results on the quadratic knapsack problem. We examine mathematical models, linearizations and reformulations. We review upper bounds, exact algorithms, heuristic and metaheuristic approaches, and provide a comparison of their computational performance.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
