Bounds on the Size of Branch-and-Bound Proofs for Integer Knapsacks

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