Title: Closing the Gap: A Theoretical and Practical Exploration of Branch-and-Bound for MIPs

Date: April 9th, 2025

Time: 12 PM – 2:00 PM

Location: Groseclose 303

Meeting Link: https://gatech.zoom.us/j/99775221586

Prachi Shah

Operations Research PhD Student

H. Milton Stewart School of Industrial and Systems Engineering

Georgia Institute of Technology

Committee:

Dr. Santanu Dey (Advisor), H. Milton Stewart School of Industrial and Systems Engineering

Dr. Nick Sahinidis, H. Milton Stewart School of Industrial and Systems Engineering

Dr. Mohit Singh, H. Milton Stewart School of Industrial and Systems Engineering

Dr. Alejandro Toriello, H. Milton Stewart School of Industrial and Systems Engineering

Dr. Luke Marshall, Microsoft Research

Abstract:

The branch-and-bound scheme, invented by Land and Doig, is the method of choice for solving mixed integer linear programs (MILP) by all modern state-of-the-art MILP solvers. While the branch-and-bound algorithm has been studied for a long time, a theoretical understanding of its performance guarantees is lacking. Furthermore, in practice, its efficiency relies on the performance of several heuristics whose interactions are not well understood. This thesis is motivated by the goal to improve both theoretical as well as practical understanding of branch-and-bound for MILPs. Given that node selection rules are well-understood, this thesis focuses primarily on branching rules.

In Chapter 2, we consider the lot-sizing problem for which there exists a polynomial time dynamic programming algorithm and prove an (worst case) exponential lower bound on the size of branch-and-bound trees even when branching is considered on general disjunctions. In Chapter 3, we consider the question of whether adding cuts will always lead to smaller trees for a given fixed branching rule. We formally call such a property of a branching rule monotonicity. We prove that most of the standard branching rules used in practice are non-monotonic. We also empirically attempt to estimate the prevalence of non-monotonicity in practice while using full strong-branching and discover that non-monotonicity is surprisingly prevalent. In Chapter 4, we introduce the notion of an ''optimal branch-and-bound tree", that is, the smallest branch-and-bound tree that solves a given instance. We present a dynamic programming algorithm for generating the optimal trees and use it to evaluate the efficiency of strong-branching on (small) instances from a range of classical problems. In Chapter 5,  attempted to better understand the properties and limitations of FSB. We have identified two key factors that significantly impact tree sizes and leveraged them to design new FSB scores.