A new exact algorithm for concave knapsack problems with integer variables

作者：Wang, Fenlan^*

来源：International Journal of Computer Mathematics, 2019, 96(1): 126-134.

DOI：10.1080/00207160.2017.1418505

• Linear underestimation
• special cut
• contour cut
• branch and bound
• concave knapsack problem

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.

• 出版日期2019-1-2
• 单位南京航空航天大学