LAUSR

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.