A Theoretical and Computational Analysis of Full Strong-Branching

Understand

Full 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 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 throughout 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.