Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Branch-and-Bound and Dynamic Programming Approaches for the Knapsack Problem

  • Research
  • Published:
Operations Research Forum Aims and scope Submit manuscript

Abstract

The knapsack problem is one of the most popular NP-hard problems in combinatorial optimization. For 0-1 Knapsack Problem, there are two common approaches which guarantee the optimality of the solutions: Branch-and-Bound (BnB) and Dynamic Programming (DP) algorithms. Both algorithms suffer from a large amount of redundant calculations. To handle this problem, we proposed modifications of these algorithms. For DP, we suggest some new pre-processing and search rules which help us to avoid unneeded calculations. For BnB, we develop a combination of common BnB method with DP with list approach. Computational experiments on artificially generated data and common benchmarks show the effectiveness of the proposed algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Data Availability

The large scale instances of 0/1 knapsack problem are described in “Pisinger, D., Where are the hard knapsack problems? Computers & Operations Research, 2005. 32(9): p. 2271-2284”, and the data can be found here: http://artemisa.unicauca.edu.co/~johnyortega/instances_01_KP/.

References

  1. Merkle R, Hellman M (1978) Hiding information and signatures in trapdoor knapsacks. IEEE Trans Inf Theory 24(5):525–530

    Article  Google Scholar 

  2. Bellman R (1954) The theory of dynamic programming. Bull Am Math Soc 60(6):503–515

    Article  Google Scholar 

  3. Nemhauser GL, Ullmann Z (1969) Discrete dynamic programming and capital allocation. Manage Sci 15(9):494–505

    Article  Google Scholar 

  4. Bas E (2011) A capital budgeting problem for preventing workplace mobbing by using analytic hierarchy process and fuzzy 0–1 bidimensional knapsack model. Expert Syst Appl 38(10):12415–12422

    Article  Google Scholar 

  5. Kellerer H, Pferschy U, Pisinger D (2004) Multidimensional knapsack problems. Springer, Berlin, Heidelberg

    Book  Google Scholar 

  6. Taillandier F, Fernandez C, Ndiaye A (2017) Real estate property maintenance optimization based on multiobjective multidimensional knapsack problem. Comput‐Aided Civ Infrastruct Eng 32(3):227–251

  7. Pisinger D (2002) Heuristics for the container loading problem. Eur J Oper Res 141(2):382–392

    Article  Google Scholar 

  8. Chang PT, Lee JH (2012) A fuzzy DEA and knapsack formulation integrated model for project selection. Comput Oper Res 39(1):112–125

    Article  Google Scholar 

  9. Pfeiffer J, Rothlauf F (2007) Analysis of greedy heuristics and weight-coded eas for multidimensional knapsack problems and multi-unit combinatorial auctions. In Proceedings of the 9th annual conference on Genetic and evolutionary computation, pp 1529–1529.https://doi.org/10.1145/1276958.1277258

  10. Kolesar PJ (1967) A branch and bound algorithm for the knapsack problem. Manag Sci 13(9):723–735

    Article  Google Scholar 

  11. Martello S, Toth P (1977) An upper bound for the zero-one knapsack. Eur J Oper Res 1:169–175

    Article  Google Scholar 

  12. Nauss RM (1976) An efficient algorithm for the 0–1 knapsack problem. Manag Sci 23(1):27–31

    Article  Google Scholar 

  13. Lalami ME, El-Baz D (2012) GPU implementation of the branch and bound method for knapsack problems. In 2012 IEEE 26th international parallel and distributed processing symposium workshops & PhD Forum, pp 1769–1777. https://doi.org/10.1109/IPDPSW.2012.219

  14. Ghassemi-Tari F, Hendizadeh H, Hogg GL (2018) Exact solution algorithms for multi-dimensional multiple-choice knapsack problems. Curr J Appl Sci Technol 1–21. https://doi.org/10.9734/CJAST/2018/40420

  15. Martello S, Pisinger D, Toth P (1999) Dynamic programming and strong bounds for the 0–1 knapsack problem. Manag Sci 45(3):414–424

    Article  Google Scholar 

  16. Pushpa SK, Mrunal TV, Suhas C (2016) A study of performance analysis on Knapsack problem. Int J Comput Appl

  17. Manaseer S, Almogdady H (2017) New hybrid approach to solve the 0/1, bounded knapsack problem. Int J Fut Revol Comput Sci Commun Eng 3:2454

  18. Zhou Y, Chen X, Zhou G (2016) An improved monkey algorithm for a 0–1 knapsack problem. Appl Soft Comput 38:817–830

    Article  Google Scholar 

  19. Rezoug A, Bader-El-Den M, Boughaci D (2018) Guided genetic algorithm for the multidimensional knapsack problem. Memetic Comp 10(1):29–42

    Article  Google Scholar 

  20. Martello S, Pisinger D, Toth P (2000) New trends in exact algorithms for the 0–1 knapsack problem. Eur J Oper Res 123(2):325–332

    Article  Google Scholar 

  21. Ross GT, Soland RM (1975) A branch and bound algorithm for the generalized assignment problem. Math Program 8(1):91–103

    Article  Google Scholar 

  22. Hristakeva M, Shrestha D (2005, April) Different approaches to solve the 0/1 knapsack problem. In: The Midwest Instruction and Computing Symposium

  23. Dantzig GB (1957) Discrete-variable extremum problems. Oper Res 5(2):266–288

    Article  Google Scholar 

  24. Pisinger D (2018) Instances of 0/1 knapsack problem. [Online]. Retrieved from September 30, 2024, from http://artemisa.unicauca.edu.co/~johnyortega/instances

  25. Kellerer H, Pferschy U, Pisinger D (2004) Multidimensional knapsack problems. Springer Berlin Heidelberg, pp 235–283

Download references

Acknowledgements

The article was prepared within the framework of the Basic Research Program at the National Research UniversityHigher School of Economics (HSE University).

Author information

Authors and Affiliations

  1. National Research University Higher School of Economics (HSE University), Nizhny Novgorod, Russia

    Evgenii Burashnikov

Authors
  1. Evgenii Burashnikov
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

I, Burashnikov E., conducted all aspects of the research, including writing the main manuscript text and preparing all figures. I reviewed and approved the final manuscript.

Corresponding author

Correspondence to Evgenii Burashnikov.

Ethics declarations

Competing Interests

The authors declare no competing interests.

Additional information

Topical Collection on Networks and Decision Making.

Appendix

Appendix

7

Table 7 The results of the algorithms for common benchmarks (the best results in terms of the algorithm’s running time are highlighted in bold)
Full size table

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Burashnikov, E. Branch-and-Bound and Dynamic Programming Approaches for the Knapsack Problem. Oper. Res. Forum 5, 98 (2024). https://doi.org/10.1007/s43069-024-00372-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s43069-024-00372-2

Keywords

Search

Navigation