Santanu Dey, Title: Theoretical and computational analysis of sizes of branch-and-bound trees
Abstract: The branch-and-bound algorithm was invented for solving integer programs (IP) in 1960. Since then, there is almost no 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 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.
Time: Fri 2021-11-05 14.00 - 15.00
Lecturer: Santanu Dey, Georgia Tech