Epstein Institute - ISE 651 Seminar

Department of Industrial & Systems Engineering, USC

Date: Tuesday, February 7, 2023

Time: 6:30 – 7:50 pm EST; 3:30 – 4:50 pm PST

Location: USC’s Andrus Gerontology Center (Room 206)

Speaker: Santanu Dey

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 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.

Bio: Santanu 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. Dr. Dey's research interests are in non-convex optimization, and in particular mixed integer linear and nonlinear programming. He currently serves on the editorial board of Computational Optimization and Applications, and is an associate editor for Mathematical Programming A, Mathematics of Operations Research and SIAM Journal on Optimization. He has previously served as an associate editor for INFORMS Journal on Computing and an area editor for Mathematical Programming C. He has won the 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 INFORMS Balas prize. He has been a Diversity Fellow at Georgia Tech, and has held the Fouts Family Junior Professorship and the A. Russell Chandler III Professorship at Georgia Tech.