.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
discrete optimization
integer programming
Knapsack problem
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
暂无机构信息
引用论文
.png){kind=icon}
没有更多内容
没有更多内容