- This event has passed.
STOR Colloquium: Yatharth Dubey, Georgia Institute of Technology
31 Jan @ 3:30 pm - 4:30 pm
STOR Colloquium: Yatharth Dubey, Georgia Institute of Technology
31 Jan @ 3:30 pm – 4:30 pmNovel Analysis of Branch-and-Bound for Integer Programming
Mixed-integer linear programming (MILP) has become a pillar of operational decision making and optimization, with vast economic and societal impact. Multi-billion-dollar industries and critical infrastructure rely on MILP solvers to effectively make large-scale discrete decisions. Despite a half-century of active research on the subject, critical components of these solvers’ underlying algorithms remain poorly understood theoretically. This work provides novel and fundamental insights on several long-analyzed phenomena in the branch-and-bound method, the workhorse algorithm of all state-of-the-art MILP solvers. We investigate three major questions: i) does branch-and-bound work well for ”most” instances? ii) what is it about well-known variable selection rules that allows them to succeed? iii) what kinds of instances are challenging for solvers based on branch-and-bound and cutting planes? Increases in the efficiency of MILP solvers, from resulting theoretical underpinnings, has the potential for widespread positive impact.