Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems

Silvano Martello and Paolo Toth
Additional contact information
Silvano Martello: University of Bologna, Italy
Paolo Toth: University of Bologna, Italy

Operations Research, 1997, vol. 45, issue 5, 768-778

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 (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.5.768 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:5:p:768-778

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().