9/15/22 | 4:15pm | E51-145

Santanu Dey

Professor
Georgia Tech

Abstract: 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 rule?

This is joint work with Yatharth Dubey, Marco Molinaro, and Prachi Shah.

Bio: Santanu S. Dey is A. Russell Chandler III Professor and associate chair of graduate studies in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. His research interests are in the area of non-convex optimization, and in particular mixed integer linear and nonlinear programming. He serves on the editorial board of several journals including Computational Optimization and Applications, Mathematics of Operations Research, Mathematical Programming A, and SIAM Journal on Optimization. His honors include the INFORMS Nicholson student paper competition, IBM Faculty Award, Class of 1969 Teaching Fellow at Georgia Tech, NSF CAREER award, INFORMS ENRE best paper award for energy, and the INFORMS optimization society Balas Prize.