.png){kind=icon}
.png){kind=icon}
Return
A new lower bound for the linear knapsack problem with general integer variables
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2006.02.018.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
It is well known that the linear knapsack problem with general integer variables (LKP) is NP-hard. In this paper we first introduce a special case of this problem and develop an O(n) algorithm to solve it. We then show how this algorithm can be used efficiently to obtain a lower bound for a general instance of LKP and prove that it is at least as good as the linear programming lower bound. We also present the results of a computational study that show that for certain classes of problems the proposed bound on average is tighter than other bounds proposed in the literature. (c) 2006 Elsevier B.V. All rights reserved.
Keywords:
discrete optimization
integer programming
Knapsack problem
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
No organization information available