UPPER-BOUNDS AND ALGORITHMS FOR HARD 0-1-KNAPSACK-PROBLEMS

It is well-known that many instances of the 0-1 knapsack problem can b e effectively solved to optimality also for very large values of n (th e number of binary variables), while other instances cannot be solved for n equal to only a few hundreds. We propose upper bounds obtained f rom the mathematical model of the problem by adding valid inequalities on the cardinality of an optimal solution, and relaxing it in a Lagra ngian 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 experim ents prove that several classes of hard instances are effectively solv ed even for large values of n.