Bounds on the size of branch-and-bound proofs for integer knapsacks

Bounds on the size of branch-and-bound proofs for integer knapsacks

0.00 Avg rating0 Votes
Article ID: iaor2009670
Country: Netherlands
Volume: 36
Issue: 1
Start Page Number: 19
End Page Number: 25
Publication Date: Jan 2008
Journal: Operations Research Letters
Authors:
Keywords: programming: branch and bound
Abstract:

Using a direct counting argument, we derive lower and upper bounds for the number of nodes enumerated by linear programming-based branch-and-bound (B&B) method to prove the integer infeasibility of a knapsack. We prove by example that the size of the B&B tree could be exponential in the worst case.

Reviews

Required fields are marked *. Your email address will not be published.