A 3-space dynamic programming heuristic for the cubic knapsack problem

Ibrahim Dan Dije (), Franklin Djeumou Fomeni () and Leandro C. Coelho ()
Additional contact information
Ibrahim Dan Dije: GERAD (Group for Research in Decision Analysis)
Franklin Djeumou Fomeni: GERAD (Group for Research in Decision Analysis)
Leandro C. Coelho: GERAD (Group for Research in Decision Analysis)

Journal of Combinatorial Optimization, 2025, vol. 49, issue 4, No 7, 32 pages

Abstract: Abstract The cubic knapsack problem (CKP) is a combinatorial optimization problem, which can be seen both as a generalization of the quadratic knapsack problem (QKP) and of the linear Knapsack problem (KP). This problem consists of maximizing a cubic function of binary decision variables subject to one linear knapsack constraint. It has many applications in biology, project selection, capital budgeting problem, and in logistics. The QKP is known to be strongly NP-hard, which implies that the CKP is also NP-hard in the strong sense. Unlike its linear and quadratic counterparts, the CKP has not received much of attention in the literature. Thus the few exact solution methods known for this problem can only handle problems with up to 60 decision variables. In this paper, we propose a deterministic dynamic programming-based heuristic algorithm for finding a good quality solution for the CKP. The novelty of this algorithm is that it operates in three different space variables and can produce up to three different solutions with different levels of computational effort. The algorithm has been tested on a set of 1570 test instances, which include both standard and challenging instances. The computational results show that our algorithm can find optimal solutions for nearly 98% of the standard test instances that could be solved to optimality and for 92% for the challenging instances. Finally, the computational experiments present comparisons between our algorithm, an existing heuristic algorithm for the CKP found in the literature, as well as adaptations to the CKP of some heuristic algorithms designed for the QKP. The results show that our algorithm outperforms all these methods.

Keywords: Knapsack problem; Integer programming; Dynamic programming; Cubic Knapsack problem (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01294-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:4:d:10.1007_s10878-025-01294-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01294-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().