Title: On exact solution approaches for concave knapsack problems

Authors: Liezl Van Eck; Stephan E. Visagie

Addresses: Department of Logistics, Stellenbosch University, South Africa ' Department of Logistics, Stellenbosch University, South Africa

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.

DOI: 10.1504/IJOR.2020.105445

International Journal of Operational Research, 2020 Vol.37 No.3, pp.396 - 417

Received: 27 Aug 2016
Accepted: 03 Apr 2017
Published online: 02 Mar 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article