Till innehåll på sidan

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.

Tid: Fr 2021-11-05 kl 14.00 - 15.00

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

Språk: English

Föreläsare: Santanu Dey, Georgia Tech

Innehållsansvarig:Per Enqvist
Tillhör: Stockholms Matematikcentrum
Senast ändrad: 2021-11-02