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.
International Journal of Operational Research, 2020 Vol.37 No.3, pp.396 - 417
Received: 27 Aug 2016
Accepted: 03 Apr 2017
Published online: 21 Feb 2020 *