Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143194 | Operations Research Letters | 2008 | 7 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Bala Krishnamoorthy,