Article ID Journal Published Year Pages File Type
1143194 Operations Research Letters 2008 7 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,