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