What is the best method to achieve a tight upper bound for knapsack problem?
I guess you know one of the simplest method : the objects are sorted by the decresasing ratio of cost/volume. the first objects that fill the bag are choosen. The variable associated with the last object put in the bag may be not integer.
This method is probably not the best upper bound, but one of the fastest and the simplest to compute.
Dear Bertrand, the linear relaxation of the knapsack problem model is the method has been mentioned. However, i want to know the better method.
It depends on the context of the problem. A possibly good alternative might be the lagrangian relaxation using a cutting plane algorithm.
I suggest to read this introduction of Alberto Caprara in 4OR journal:
Knapsack problems: A book review (4OR journal, 2004, Volume 2, Issue 4, pp 317-320)
and "Knapsack Problems" by Hans Kellerer, Ulrich Pferschy, David Pisinger (Springer)
- Badges
- Science topic