Upper bounds and algorithms for hard 0-1 knapsack problems
成果类型：
Article
署名作者：
Martello, S; Toth, P
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.5.768
发表日期：
1997
页码：
768-778
关键词：
摘要：
It is well-known that many instances of the 0-1 knapsack problem can be effectively solved to optimality also for very large values of n (the number of binary variables), while other instances cannot be solved for n equal to only a few hundreds. We propose upper bounds obtained from the mathematical model of the problem by adding valid inequalities on the cardinality of an optimal solution, and relaxing it in a Lagrangian fashion. We then introduce a specialized iterative technique for determining the optimal Lagrangian multipliers in polynomial time. A branch-and-bound algorithm is finally developed. Computational experiments prove that several classes of hard instances are effectively solved even for large values of n.