# A Theoretical and Computational Analysis of Full Strong-Branching

arXiv: https://arxiv.org/abs/2110.10754 · HTML: https://mlsanity.com/paper/2110.10754/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2021.

## Built on by (most cited first, 13 of 13)

- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [A Survey of Optimization-based Task and Motion Planning: From Classical To Learning Approaches](https://mlsanity.com/paper/2404.02817/) (2024)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [CAMBranch: Contrastive Learning with Augmented MILPs for Branching](https://mlsanity.com/paper/2402.03647/) (2024)
- [MPAX: Mathematical Programming in JAX](https://mlsanity.com/paper/2412.09734/) (2024)
- [LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs](https://mlsanity.com/paper/2605.10401/) (2026)
- [STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization](https://mlsanity.com/paper/2506.11057/) (2025)
- [Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization](https://mlsanity.com/paper/2511.09219/) (2025)
- [Learning to Condition: A Neural Heuristic for Scalable MPE Inference](https://mlsanity.com/paper/2509.25217/) (2025)
- [Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality](https://mlsanity.com/paper/2512.09355/) (2025)
- [How To Discover Short, Shorter, and the Shortest Proofs of Unsatisfiability: A Branch-and-Bound Approach for Resolution Proof Length Minimization](https://mlsanity.com/paper/2411.07955/) (2024)
- [Logic-Constrained Shortest Paths for Flight Planning](https://mlsanity.com/paper/2412.13235/) (2024)
- [Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching](https://mlsanity.com/paper/2604.00094/) (2026)

## Abstract (arXiv)

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