IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v326y2025i1p1-12.html

The quadratic knapsack problem

Author

Listed:
  • Galli, Laura
  • Martello, Silvano
  • Toth, Paolo

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.

Suggested Citation

  • Galli, Laura & Martello, Silvano & Toth, Paolo, 2025. "The quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 326(1), pages 1-12.
    • Handle: RePEc:eee:ejores:v:326:y:2025:i:1:p:1-12
    DOI: 10.1016/j.ejor.2024.12.032
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724009743
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.12.032?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Fampa, M. & Lubke, D. & Wang, F. & Wolkowicz, H., 2020. "Parametric convex quadratic relaxation of the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 281(1), pages 36-49.
    2. Z. Wu & G. Li & J. Quan, 2011. "Global optimality conditions and optimization methods for quadratic integer programming problems," Journal of Global Optimization, Springer, vol. 51(3), pages 549-568, November.
    3. Billionnet, Alain & Faye, Alain & Soutif, Eric, 1999. "A new upper bound for the 0-1 quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 112(3), pages 664-672, February.
    4. Galli, Laura & Martello, Silvano & Rey, Carlos & Toth, Paolo, 2021. "Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 291(3), pages 871-882.
    5. FERREIRA, C. E. & MARTIN, A. & de SOUZA, C. C. & WEISMANTEL, R., 1996. "Formulations and valid inequalities for the node capacitated graph partitioning problem," LIDAM Reprints CORE 1236, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Fred Glover & Gary Kochenberger & Yu Du, 2019. "Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models," 4OR, Springer, vol. 17(4), pages 335-371, December.
    7. X. Zheng & X. Sun & D. Li & Y. Xu, 2012. "On reduction of duality gap in quadratic knapsack problems," Journal of Global Optimization, Springer, vol. 54(2), pages 325-339, October.
    8. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    9. Alberto Caprara & David Pisinger & Paolo Toth, 1999. "Exact Solution of the Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 125-137, May.
    10. WOLSEY, Laurence A., 1975. "Faces for a linear inequality in 0-1 variables," LIDAM Reprints CORE 218, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Martina Fischetti & David Pisinger, 2019. "Mathematical Optimization and Algorithms for Offshore Wind Farm Design: An Overview," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 61(4), pages 469-485, August.
    12. Fred Glover & Eugene Woolsey, 1973. "Further Reduction of Zero-One Polynomial Programming Problems to Zero-One linear Programming Problems," Operations Research, INFORMS, vol. 21(1), pages 156-161, February.
    13. Ulrich Pferschy & Joachim Schauer, 2016. "Approximation of the Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 308-318, May.
    14. W. David Pisinger & Anders Bo Rasmussen & Rune Sandvik, 2007. "Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 280-290, May.
    15. Franklin Djeumou Fomeni & Adam N. Letchford, 2014. "A Dynamic Programming Heuristic for the Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 173-182, February.
    16. Fred Glover & Eugene Woolsey, 1974. "Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program," Operations Research, INFORMS, vol. 22(1), pages 180-182, February.
    17. Byron Tasseff & Tameem Albash & Zachary Morrell & Marc Vuffray & Andrey Y. Lokhov & Sidhant Misra & Carleton Coffrin, 2024. "On the emerging potential of quantum annealing hardware for combinatorial optimization," Journal of Heuristics, Springer, vol. 30(5), pages 325-358, December.
    18. Warren P. Adams & Hanif D. Sherali, 1986. "A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems," Management Science, INFORMS, vol. 32(10), pages 1274-1290, October.
    19. Z. Y. Wu & Y. J. Yang & F. S. Bai & M. Mammadov, 2011. "Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems," Journal of Optimization Theory and Applications, Springer, vol. 151(2), pages 241-259, November.
    20. Jesus Cunha & Luidi Simonetti & Abilio Lucena, 2016. "Lagrangian heuristics for the Quadratic Knapsack Problem," Computational Optimization and Applications, Springer, vol. 63(1), pages 97-120, January.
    21. Alain Billionnet & Éric Soutif, 2004. "Using a Mixed Integer Programming Tool for Solving the 0–1 Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 188-197, May.
    22. Schauer, Joachim, 2016. "Asymptotic behavior of the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 255(2), pages 357-363.
    23. Fennich, M. Eliass & Fomeni, Franklin Djeumou & Coelho, Leandro C., 2024. "A novel dynamic programming heuristic for the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 319(1), pages 102-120.
    24. C. Helmberg & F. Rendl & R. Weismantel, 2000. "A Semidefinite Programming Approach to the Quadratic Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 4(2), pages 197-215, June.
    25. D. J. Laughhunn, 1970. "Quadratic Binary Programming with Application to Capital-Budgeting Problems," Operations Research, INFORMS, vol. 18(3), pages 454-461, June.
    26. Billionnet, Alain & Soutif, Eric, 2004. "An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 157(3), pages 565-575, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hochbaum, D.S. & Baumann, P. & Goldschmidt, O. & Zhang, Y., 2025. "A fast and effective breakpoints heuristic algorithm for the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 323(2), pages 425-440.
    2. Britta Schulze & Michael Stiglmayr & Luís Paquete & Carlos M. Fonseca & David Willems & Stefan Ruzika, 2020. "On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(1), pages 107-132, August.
    3. Fennich, M. Eliass & Fomeni, Franklin Djeumou & Coelho, Leandro C., 2024. "A novel dynamic programming heuristic for the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 319(1), pages 102-120.
    4. Ibrahim Dan Dije & Franklin Djeumou Fomeni & Leandro C. Coelho, 2025. "A 3-space dynamic programming heuristic for the cubic knapsack problem," Journal of Combinatorial Optimization, Springer, vol. 49(4), pages 1-32, May.
    5. Gabriel Lopez Zenarosa & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2021. "On exact solution approaches for bilevel quadratic 0–1 knapsack problem," Annals of Operations Research, Springer, vol. 298(1), pages 555-572, March.
    6. Fabio Furini & Emiliano Traversi, 2019. "Theoretical and computational study of several linearisation techniques for binary quadratic problems," Annals of Operations Research, Springer, vol. 279(1), pages 387-411, August.
    7. David Bergman, 2019. "An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating," INFORMS Journal on Computing, INFORMS, vol. 31(3), pages 477-492, July.
    8. Sven Mallach, 2021. "Inductive linearization for binary quadratic programs with linear constraints," 4OR, Springer, vol. 19(4), pages 549-570, December.
    9. Schauer, Joachim, 2016. "Asymptotic behavior of the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 255(2), pages 357-363.
    10. Jesus Cunha & Luidi Simonetti & Abilio Lucena, 2016. "Lagrangian heuristics for the Quadratic Knapsack Problem," Computational Optimization and Applications, Springer, vol. 63(1), pages 97-120, January.
    11. W. David Pisinger & Anders Bo Rasmussen & Rune Sandvik, 2007. "Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 280-290, May.
    12. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    13. Warren Adams & Hanif Sherali, 2005. "A Hierarchy of Relaxations Leading to the Convex Hull Representation for General Discrete Optimization Problems," Annals of Operations Research, Springer, vol. 140(1), pages 21-47, November.
    14. Z. Y. Wu & Y. J. Yang & F. S. Bai & M. Mammadov, 2011. "Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems," Journal of Optimization Theory and Applications, Springer, vol. 151(2), pages 241-259, November.
    15. Richard J. Forrester & Warren P. Adams & Paul T. Hadavas, 2010. "Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(1), pages 1-12, February.
    16. Nihal Berktaş & Hande Yaman, 2021. "A Branch-and-Bound Algorithm for Team Formation on Social Networks," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1162-1176, July.
    17. Xiaojin Zheng & Xiaoling Sun & Duan Li & Yong Xia, 2010. "Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming," Mathematics of Operations Research, INFORMS, vol. 35(4), pages 864-880, November.
    18. Sven Mallach, 2024. "Inductive linearization for binary quadratic programs with linear constraints: a computational study," 4OR, Springer, vol. 22(1), pages 47-87, March.
    19. Borzou Rostami & Fausto Errico & Andrea Lodi, 2023. "A Convex Reformulation and an Outer Approximation for a Large Class of Binary Quadratic Programs," Operations Research, INFORMS, vol. 71(2), pages 471-486, March.
    20. C. Helmberg & F. Rendl & R. Weismantel, 2000. "A Semidefinite Programming Approach to the Quadratic Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 4(2), pages 197-215, June.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:326:y:2025:i:1:p:1-12. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.