Abstract
Strong Branching (SB) is a cornerstone of all modern branching rules used in the Branch-and-Bound (BnB) algorithm, which is at the center of Mixed-Integer Programming solvers. In its full form, SB evaluates all variables to branch on and then selects the one producing the best relaxation, leading to small trees, but high runtimes. State-of-the-art branching rules therefore use SB with working limits to achieve both small enough trees and short run times. So far, these working limits have been established empirically. In this paper, we introduce a theoretical approach to guide how much SB to use at each node within the BnB. We first define an abstract stochastic tree model of the BnB algorithm where the geometric mean dual gains of all variables follow a given probability distribution. This model allows us to relate expected dual gains to tree sizes and explicitly compare the cost of sampling an additional SB candidate with the reward in expected tree size reduction. We then leverage the insight from the abstract model to design a new stopping criterion for SB, which fits a distribution to the dual gains and, at each node, dynamically continues or interrupts SB. This algorithm, which we refer to as Probabilistic Lookahead Strong Branching, improves both the tree size and runtime over MIPLIB instances, providing evidence that the method not only changes the amount of SB, but allocates it better.
Introduction: The Challenge of Strong Branching
Mixed-Integer Programming (MIP) solvers rely on the Branch-and-Bound (BnB) algorithm. At every step, the solver must choose a variable to "branch" on. Strong Branching (SB) is the gold standard for making this choice: it pre-calculates the "dual gain" (improvement in the objective bound) for potential candidates.
The catch? SB is incredibly expensive because it requires solving multiple linear programs (LPs) for every candidate. To keep solvers fast, developers use a lookahead limit ($L$): if the solver tests $L$ variables without finding a new "best" one, it stops and picks the current leader. In the popular solver SCIP, $L$ is traditionally fixed at 9. This paper addresses the fact that a one-size-fits-all $L$ is theoretically ungrounded and often suboptimal.
The Limitations of Empirical Defaults
Empirical evidence suggests that the default settings for lookahead limits are highly tuned. As shown in the table below, simply adjusting the fixed lookahead limit $L$ or the iteration limit $K$ typically results in performance degradation across both time and node counts.
This data confirms that the default $L=9$ is a robust local optimum for fixed heuristics, necessitating a more sophisticated, dynamic approach to improve solver efficiency.
Methodology: A Stochastic Approach to Branching
The authors bridge the gap between theory and practice using a three-step approach:
- Pandora’s MVB: They introduce a new abstract model called the Pandora’s Multi-Variable Branching problem. This combines the classic "Pandora’s Box" problem (where you pay a cost to reveal a hidden reward) with the Multi-Variable Branching model. Here, dual gains are treated as random variables revealed only through the "cost" of an SB call.
- Stochastic Modeling: They assume that the geometric mean of dual gains at a node follows a specific probability distribution. After testing several candidates, they fit a Mixed Distribution (a mass point at zero for variables that provide no gain, plus a continuous tail like a Pareto or Exponential distribution) to the observed data.
- The PL-SB Algorithm: They derive a stopping criterion based on the expected number of nodes. At each iteration of SB, the algorithm asks: "Is the expected reduction in the final tree size greater than the cost of performing one more SB evaluation?" If the answer is no, the solver stops immediately.
Key Insights: Modeling the Dual Gain Distribution
- The "Mass Point at Zero": One of the most important observations is that many branching candidates yield zero dual gain. Standard distributions fail to capture this. By using a "Mixed" distribution that explicitly accounts for these zeros, the model becomes much more accurate.
- Better Allocation, Not Just Less Work: The goal of the Probabilistic Lookahead (PL-SB) isn't necessarily to do less Strong Branching overall, but to allocate it where it matters. The algorithm might stop early on "easy" nodes but persist longer on "critical" nodes where a better branch could prune thousands of future subproblems.
- Geometric Mean as a Proxy: The authors use the geometric mean of "up" and "down" gains. This aligns with state-of-the-art scoring functions used in solvers, providing a solid link between their abstract model and practical solver implementation.
Experimental Results
The authors implemented PL-SB in the SCIP solver and evaluated it on the MIPLIB 2017 and MINLPLib benchmarks. The results demonstrate that PL-SB consistently outperforms the default fixed-lookahead strategy:
- Hard Instances: On "hard" MIPLIB instances (those taking >1000 seconds to solve), PL-SB reduced the running time by 8% and the number of nodes by 9%.
- Efficiency: The algorithm stopped SB earlier than the default lookahead in about 20% of calls, yet it found better branching candidates often enough to reduce the total tree size.
- Generalization: On MINLP instances, the method yielded a 2% reduction in time and 4% in nodes, suggesting the underlying stochastic model is robust across different problem types.
Conclusion and Future Work
While PL-SB offers a significant step forward, it has limitations. The algorithm requires a minimum number of SB samples (at least 60% of the maximum lookahead) to fit a distribution reliably. Furthermore, the model currently assumes dual gains are independent and identically distributed (i.i.d.) at a given node, which may not hold in practice due to variable correlations.
Future research could involve a Bayesian approach—using dual gains observed at previous nodes to inform the distribution at the current node, potentially allowing the algorithm to make informed stopping decisions even earlier in the branching process.
Summary updated