Back to Search
Start Over
A new exact algorithm for concave knapsack problems with integer variables.
- Source :
-
International Journal of Computer Mathematics . Jan2019, Vol. 96 Issue 1, p126-134. 9p. - Publication Year :
- 2019
-
Abstract
- Concave knapsack problems with integer variables have many applications in real life, and they are NP-hard. In this paper, an exact and efficient algorithm is presented for concave knapsack problems. The algorithm combines the contour cut with a special cut to improve the lower bound and reduce the duality gap gradually in the iterative process. The lower bound of the problem is obtained by solving a linear underestimation problem. A special cut is performed by exploiting the structures of the objective function and the feasible region of the primal problem. The optimal solution can be found in a finite number of iterations, and numerical experiments are also reported for two different types of concave objective functions. The computational results show the algorithm is efficient. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00207160
- Volume :
- 96
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- International Journal of Computer Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 132835999
- Full Text :
- https://doi.org/10.1080/00207160.2017.1418505