On exact solution approaches for concave knapsack problems Online publication date: Mon, 02-Mar-2020
by Liezl Van Eck; Stephan E. Visagie
International Journal of Operational Research (IJOR), Vol. 37, No. 3, 2020
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Operational Research (IJOR):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook