Georgia Institute of Technology
Closing the Gap: A Theoretical and Practical Exploration of Branch-and-Bound Procedure for Mixed-Integer Programs
Abstract
dc:description.abstractThe 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.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Industrial and Systems Engineering
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Shah, Prachi
- Advisor dc:contributor.advisor
-
- Dey, Santanu S.
- Committee members dc:contributor.committeemember
-
- Marshall, Luke
- Sahinidis, Nikolaos
- Singh, Mohit
- Toriello, Alejandro
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/77883