On exact solution approaches for concave knapsack problems

Liezl Van Eck and Stephan E. Visagie

International Journal of Operational Research, 2020, vol. 37, issue 3, 396-417

Abstract: This paper introduces five characteristics of concave knapsack problem (CKP) instances that influence computational times of algorithms. A dataset, based on these characteristics, is randomly generated and made available online for future studies and comparison of computational times. In this study the dataset is used to compare the computational performance of two integer programming formulations and four algorithms to solve CKPs. A novel algorithm (BLU) that combines the logic of dynamic programming and the Karush-Kuhn-Tucker necessary conditions for the CKP is also introduced. The computational times for the two integer programming formulations were too long and were thus excluded from the statistical analysis. Analysis of the computational times shows that algorithms are sensitive to different characteristics. Any algorithm, depending on the settings of the five characteristics, could win in terms of average computational time, but BLU outperforms the other algorithms over the widest range of settings for these characteristics.

Keywords: concave knapsack problem; CKP; branch-and-bound; dynamic programming; comparison of algorithms. (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=105445 (text/html)
Access to full text is restricted to subscribers.

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:ids:ijores:v:37:y:2020:i:3:p:396-417

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().