  


A Theoretical and Computational Analysis of Full StrongBranching
Santanu S. Dey (santanu.deyisye.gatech.edu) Abstract: Full strongbranching (henceforth referred to as strongbranching) is a wellknown variable selection rule that is known experimentally to produce significantly smaller branchandbound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strongbranching rule both from a theoretical and a computational perspective. On the positive side for strongbranching 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 branchandbound tree using strongbranching as a function of the additive integrality gap, show how the NemhauserTrotter property of persistency which can be used as a presolve technique for vertex cover is being recursively and consistently used throughout the strongbranching based branchandbound tree, and finally provide an example of a vertex cover instance where not using strongbranching leads to a tree that has at least exponentially more nodes than the branchandbound tree based on strongbranching. On the negative side for strongbranching, we identify another class of instances where strongbranching based branchandbound tree has exponentially larger tree in comparison to another branchandbound tree for solving these instances. On the computational side, we first present a dynamic programming algorithm to find an optimal branchandbound 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 lotsizing 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 strongbranching based branchandbound tree in comparison to the optimal branchandbound tree. The main takeaway from these experiments is that for all these instances, the size of the strongbranching based branchandbound tree is within a factor of two of the size of the optimal branchandbound tree. Keywords: branchandbound, integer programming, variable selection, strong branching Category 1: Integer Programming Category 2: Combinatorial Optimization (Branch and Cut Algorithms ) Citation: Download: [PDF] Entry Submitted: 10/20/2021 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  