Optimization Online


A Theoretical and Computational Analysis of Full Strong-Branching

Santanu S. Dey (santanu.dey***at***isye.gatech.edu)
Yatharth Dubey (yatharthdubey7***at***gatech.edu)
Marco Molinaro (molinaro***at***inf.puc-rio.br)
Prachi Shah (prachi.shah***at***gatech.edu)

Abstract: 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 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 $\text{poly}(\text{data}(\I)) \cdot 3^{O(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.

Keywords: branch-and-bound, integer programming, variable selection, strong branching

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 10/20/2021
Entry Accepted: 10/20/2021
Entry Last Modified: 11/09/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society