The branch-and-bound algorithm was invented for solving integer programs (IP) in 1960. Since then, there is very little theoretical analysis of the branch-and-bound algorithm, even though the algorithm is the workhorse of all modern IP solvers. We try and answer some of the following basic questions regarding the branch-and-bound algorithm in this talk: (i) While it is known that the size of simple branch-and-bound trees can be exponential in size in the worst case, can we prove smaller size of branch-and-bound tree under a random model for the instances? (ii) Most lower bounds on size of branch-and-bound tree are for simple disjunctions. Can we prove similar lower bounds for general disjunctions? (iii) Can we analyze the performance of well-known branching rules like the full strong branching?
This is joint work with Yatharth Dubey, Marco Molinaro, and Prachi Shah.