Back to search

Georgia Institute of Technology

Closing the Gap: A Theoretical and Practical Exploration of Branch-and-Bound Procedure for Mixed-Integer Programs

Abstract

dc:description.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.

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

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/77883

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shah, Prachi. Closing the Gap: A Theoretical and Practical Exploration of Branch-and-Bound Procedure for Mixed-Integer Programs. Doctoral thesis, Georgia Institute of Technology, 2025. https://hdl.handle.net/1853/77883