Skip to main content

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

Location: Zoom room 63658381373; Seminar room 3721, for watching the zoom presentation on zoom together

Language: English

Participating: Santanu Dey, Georgia Tech

Export to calendar

Page responsible:Per Enqvist
Belongs to: Stockholm Mathematics Centre
Last changed: Apr 23, 2023