Thesis Title: Novel Analysis of the Branch-and-Bound Method for Integer Programming

Advisor:

Dr. Santanu S. Dey, School of Industrial and Systems Engineering, Georgia Institute of Technology

Thesis Committee:

Dr. Amitabh Basu, Department of Applied Mathematics and Statistics, Johns Hopkins University

Dr. Marco Molinaro, Computer Science Department, Pontifical Catholic University of Rio de Janeiro

Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology

Dr. Alejandro Toriello, School of Industrial and Systems Engineering, Georgia Institute of Technology

Date and Time: Wednesday, June 15th, 2022, 10:00 AM (ET)

Location: Meeting link below

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

Meeting ID: 910 0687 5097

Abstract:

Mixed-integer linear programming (MILP) has become a pillar of operational decision making and optimization, with large-scale economic and societal impact. MILP solvers drive multi-billion dollar industries and the operation of critical infrastructure, and this ability to use MILPs to effectively make large-scale discrete decisions relies on the ability to solve MILPs efficiently. Despite a half-century of active research on the subject, critical components of these solvers' underlying algorithms remain poorly understood theoretically. This thesis provides novel and fundamental explanations for, and practical insights on, several long-analyzed phenomena in the branch-and-bound method, the workhorse algorithm of all state-of-the-art MILP solvers. 

These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some integer constrained variable to one of its possible values. Even though modern MILP solvers are able to solve very large-scale instances efficiently, relatively little attention has been given to understanding why the underlying branch-and-bound algorithm performs so well. In Chapter 2, our goal is to theoretically analyze the performance of the standard variable branching based branch-and-bound algorithm. In order to avoid the exponential worst-case lower bounds, we follow the common idea of considering random instances. More precisely, we consider random integer programs where the entries of the coefficient matrix and the objective function are randomly sampled. Our main result is that with good probability branch-and-bound with variable branching explores only a polynomial number of nodes to solve these instances, for a fixed number of constraints. To the best of our knowledge this is the first known such result for a standard version of branch-and-bound. 

To understand the difficulties of branch-and-bound, in Chapter 3 we study an algorithm that can be viewed as an abstraction of modern MILP solvers: general branch-and-bound. That is, instances that are challenging for general branch-and-bound are likely to also be challenging for MILP solvers. A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general (i.e., split) disjunctions to create child nodes. We construct a packing instance, a set covering instance, and a Traveling Salesman Problem instance, such that any general branch-and-bound tree that solves these instances must be of exponential size. We also verify that an exponential lower bound on the size of general branch-and-bound trees persists even when we add Gaussian noise to the coefficients of the cross-polytope, thus showing that a polynomial-size ``smoothed analysis'' upper bound is not possible.

Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In Chapter 4, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On the positive side for strong branching, we identify vertex cover as a class of instances where this rule provably works well. In particular, for vertex cover we present an upper bound on the size of the branch-and-bound tree using strong-branching as a function of the additive integrality gap, show how the Nemhauser-Trotter property of persistency which can be used as a pre-solve technique for vertex cover is being recursively and consistently used through-out the strong-branching based branch-and-bound tree, and finally provide an example of a vertex cover instance where not using strong-branching leads to a tree that has at least exponentially more nodes than the branch-and-bound tree based on strong-branching. On the negative side for strong-branching, we identify another class of instances where strong-branching based branch-and-bound tree has exponentially larger tree in comparison to another branch-and-bound tree for solving these instances. On the computational side, we conduct experiments on various types of instances like the lot-sizing problem and its variants, packing IPs, covering IPs,  chance constrained IPs, vertex cover, etc., to understand how much larger is the size of the strong-branching based branch-and-bound tree in comparison to the optimal branch-and-bound tree. The main take-away from these experiments is that for all these instances, the size of the strong-branching based branch-and-bound tree is within a factor of two of the size of the optimal branch-and-bound tree.

Finally, in Chapter 5 we discuss possible extensions of the work covered in this thesis.