Portal de Periódicos da CAPES

Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems

1997; Institute for Operations Research and the Management Sciences; Volume: 45; Issue: 5 Linguagem: Inglês

10.1287/opre.45.5.768

1526-5463

Silvano Martello, Paolo Toth,

Optimization and Search Problems

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.