A theoretical and computational analysis of full strong-branching

Santanu S. Dey, Yatharth Dubey, Marco Molinaro, Prachi Shah

TL;DR

This paper provides a comprehensive theoretical and computational analysis of "strong-branching," a popular heuristic for solving mixed-integer linear programs (MILPs). It proves that strong-branching is provably good for vertex cover problems but can be provably bad for other instances, while empirical results show it's remarkably efficient in practice, producing trees only up to twice the size of optimal ones.

What Problem Does This Paper Address?

Solving Mixed-Integer Linear Programs (MILPs) is a fundamental problem in optimization, often tackled using branch-and-bound (B&B) algorithms. A key component of B&B is the "variable selection rule," which dictates which variable to branch on when a fractional solution is encountered. "Strong-branching" is a well-known, highly effective rule that, while computationally expensive, has been observed to significantly reduce the size of the B&B tree. However, a deep theoretical understanding of why it works so well, and when it might fail, has been lacking. This paper aims to bridge that gap by providing both theoretical guarantees and empirical evidence of strong-branching's performance.

Methods

The paper employs a multi-pronged approach:

  • Theoretical Analysis:
    • Vertex Cover: They prove theoretical upper bounds on the B&B tree size for vertex cover instances, parameterized by the integrality gap. They also demonstrate how strong-branching naturally leverages the "persistency" property (Nemhauser-Trotter property) of vertex cover, ensuring that integral variables in LP relaxations are handled efficiently. Crucially, they construct an instance where strong-branching yields an exponentially smaller tree than a reasonable alternative.
  • "Provably Bad" Instances: They identify a class of instances where strong-branching can lead to exponentially larger B&B trees compared to a specialized B&B approach that branches on integral variables.
  • Optimal B&B Tree Algorithm: They develop a dynamic programming algorithm to compute the size of an optimal B&B tree for binary MILPs, which serves as a benchmark for their computational studies.
  • Computational Experiments:
    • They conduct extensive experiments on various MILP problem classes (packing, covering, lot-sizing, vertex cover, chance-constrained programming, etc.).
  • They compare the performance of strong-branching (using two scoring functions: linear and product) against other rules (most infeasible, random) and the optimal B&B tree size.

Datasets

The paper uses several standard benchmark problem instances for their computational experiments, including:

  • General Packing and Covering IPs (P5, C5, G22)
  • Lot-sizing problems and variants (Capacitated, Big-bucket)
  • Minimum Vertex Cover
  • Chance Constraint Programming (CCP) models (Multiperiod Power Planning, Portfolio Optimization)
  • Stable Set on Bipartite Graph with Knapsack Constraint

No new datasets were introduced; instead, they generated randomized instances based on established problem formulations.

Key Insights and Ideas

  • Strong-branching is "almost optimal" for Vertex Cover: The theoretical results for vertex cover show that strong-branching is remarkably efficient, achieving bounds comparable to specialized algorithms and outperforming naive approaches by an exponential margin in some cases. This is partly due to its natural handling of the persistency property.
  • Strong-branching can be "provably bad": The paper highlights that strong-branching isn't universally superior. They construct specific instances where it leads to exponentially larger trees than alternative strategies, particularly when compared to methods that leverage integral variables more aggressively.
  • Empirical Dominance: Despite theoretical worst-case scenarios, strong-branching consistently performs best in practice across a wide range of problems, producing B&B trees that are, on average, within a factor of two of the optimal size. This suggests its heuristic power is very strong.
  • The "Optimal" B&B Tree is Hard to Find: The development of a dynamic programming algorithm to find the optimal B&B tree size is a significant theoretical contribution, but its exponential complexity ($3^n$) limits its applicability to small instances, underscoring the need for effective heuristics like strong-branching.

Key Results

  • Vertex Cover Bounds: An upper bound of $2^{2\Gamma(I)+2} + O(n)$ on the B&B tree size for vertex cover using strong-branching, parameterized by the integrality gap $\Gamma(I)$.
  • Exponential Separation: Construction of vertex cover instances where strong-branching yields an exponentially smaller tree than a greedy rule, and conversely, instances where strong-branching yields an exponentially larger tree than a specialized B&B approach.
  • Computational Performance: Across various MILP classes, strong-branching (both SB-L and SB-P variants) consistently outperformed random and most-infeasible branching rules. The geometric mean of B&B tree sizes using strong-branching was less than twice the size of the optimal B&B tree for all tested instances.
  • Optimal B&B Tree Algorithm: A dynamic programming algorithm with a running time of $poly(data) \cdot 3^{O(n)}$ for computing the optimal B&B tree size.

Limitations and Future Work

  • Computational Limits: The optimal B&B tree algorithm's exponential complexity limits computational experiments to instances with up to 20 binary variables. The authors acknowledge that observations from these small instances may not extrapolate to larger problems.
  • "Optimal" Tree Definition: The definition of an "optimal" B&B tree can be sensitive to the LP solver's behavior. The paper makes an assumption (Assumption 1) to ensure a well-defined notion of optimality for their analysis.
  • Future Work: The authors suggest exploring machine learning techniques to learn better branching strategies, especially for problem classes like CCP portfolio optimization where strong-branching, while good, still shows room for improvement. Investigating the relationship between branching on integer variables in the optimal tree and the performance of strong-branching is also an open area.

Summary updated

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: (1) an upper bound on the size of the branch-and-bound tree using strong-branching as a function of the additive integrality gap; (2) 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 tree; (3) 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 the strong-branching tree is exponentially larger than another branch-and-bound tree for solving these instances. On the computational side, 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 (on small instances) is that for all these instances the size of the strong-branching tree is within a factor of two of the size of the optimal branch-and-bound tree.
BibTeX
@inproceedings{dey2024theoretical,
  author = {Santanu S. Dey and Yatharth Dubey and Marco Molinaro and Prachi Shah},
  title = {{A theoretical and computational analysis of full strong-branching}},
  booktitle = {Math. Program},
  year = {2024},
  url = {https://openreview.net/forum?id=uqdLl37Co0},
}
Figure