A 3-space dynamic programming heuristic for the cubic knapsack problem
Author
Abstract
Suggested Citation
DOI: 10.1007/s10878-025-01294-3
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- Hammami, Farouk & Rekik, Monia & Coelho, Leandro C., 2019. "Exact and heuristic solution approaches for the bid construction problem in transportation procurement auctions with a heterogeneous fleet," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 150-177.
- D. E. Peterson & D. J. Laughhunn, 1971. "Capital Expenditure Programming and Some Alternative Approaches to Risk," Management Science, INFORMS, vol. 17(5), pages 320-336, January.
- 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.
- 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.
- 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.
- H. Martin Weingartner, 1966. "Capital Budgeting of Interrelated Projects: Survey and Synthesis," Management Science, INFORMS, vol. 12(7), pages 485-516, March.
- Bruce Faaland, 1974. "An Integer Programming Algorithm for Portfolio Selection," Management Science, INFORMS, vol. 20(10), pages 1376-1384, June.
- Peter Cramton & Yoav Shoham & Richard Steinberg (ed.), 2010. "Combinatorial Auctions," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262514133, December.
- Schauer, Joachim, 2016. "Asymptotic behavior of the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 255(2), pages 357-363.
- 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.
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.- 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.
- 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.
- 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.
- 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.
- Gupta, Renu & Bandopadhyaya, Lakshmisree & Puri, M. C., 1996. "Ranking in quadratic integer programming problems," European Journal of Operational Research, Elsevier, vol. 95(1), pages 231-236, November.
- 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.
- Daniele Pretolani, 2014. "Apportionments with minimum Gini index of disproportionality: a Quadratic Knapsack approach," Annals of Operations Research, Springer, vol. 215(1), pages 257-267, April.
- 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.
- Ulrich Pferschy & Joachim Schauer, 2016. "Approximation of the Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 308-318, May.
- 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.
- Richard J. Forrester & Lucas A. Waddell, 2022. "Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 498-517, August.
- Rafael Martinelli & Claudio Contardo, 2015. "Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 658-676, November.
- D. Quadri & E. Soutif & P. Tolla, 2009. "Exact solution method to solve large scale integer quadratic multidimensional knapsack problems," Journal of Combinatorial Optimization, Springer, vol. 17(2), pages 157-167, February.
- 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.
- Hammami, Farouk & Rekik, Monia & Coelho, Leandro C., 2021. "Exact and hybrid heuristic methods to solve the combinatorial bid construction problem with stochastic prices in truckload transportation services procurement auctions," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 204-229.
- Tobin, Roger L., 1999. "A fast interactive solution method for large capital expenditure selection problems," European Journal of Operational Research, Elsevier, vol. 116(1), pages 1-15, July.
- Renaud Chicoisne, 2023. "Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes," Computational Optimization and Applications, Springer, vol. 84(3), pages 789-831, April.
- Chen, Liang & Chen, Sheng-Jie & Chen, Wei-Kun & Dai, Yu-Hong & Quan, Tao & Chen, Juan, 2023. "Efficient presolving methods for solving maximal covering and partial set covering location problems," European Journal of Operational Research, Elsevier, vol. 311(1), pages 73-87.
- 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.
- Caprara, Alberto, 2008. "Constrained 0-1 quadratic programming: Basic approaches and extensions," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1494-1503, June.
More about this item
Keywords
Knapsack problem; Integer programming; Dynamic programming; Cubic Knapsack problem;All these keywords.
Statistics
Access and download statisticsCorrections
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:spr:jcomop:v:49:y:2025:i:4:d:10.1007_s10878-025-01294-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.