A theoretical and computational analysis of full strong-branching

Full strong-branching (henceforth referred to as strong-branching) is a well-known variable
selection rule that is known experimentally to produce signi cantly smaller branch-and-bound
trees in comparison to all other known variable selection rules. In this paper, 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 first present a dynamic
programming algorithm to find an optimal branch-and-bound tree for any mixed integer linear
program (MILP) with n binary variables whose running time is poly(data(I))*3^n. Then we
conduct experiments on various types of instances like the lot-sizing problem and its variants,
packing integer programs (IP), 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.