Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
Operations Research · 1997 · Volume 45 · Issue 5
Abstract
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 .
Keywords
programming, integer, algorithms, branch-and-bound, 0-1 knapsack problem, programming, integer, algorithms, relaxation/subgradient, valid inequalities, Lagrangian relaxations
Enable JavaScript for citation tools and additional paper interactions.