Location: Gilman 132
When: April 27th at 1:30 p.m.
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 limited 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.
Zoom link: https://wse.zoom.us/j/95738965246