Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation

Daniel Anderson, Gregor Hendel, Pierre Le Bodic, Merlin ViernickelAAAI 2019 · DOI

Introduction

Mixed-Integer Programming (MIP) solvers primarily utilize the Branch-and-Bound (B&B) algorithm to navigate complex search spaces. A fundamental challenge in B&B is the sensitivity of the search to early branching decisions. Decisions made at the top of the tree, where the solver has minimal information, can lead to disproportionately large search trees. While fields like Satisfiability (SAT) solving have long used restarts to mitigate poor early choices, MIP solvers lack a robust mechanism to determine when a restart is beneficial. This paper introduces a "clairvoyant" restart strategy that uses online tree-size estimation to make informed decisions about abandoning inefficient searches.

Measuring Progress via Node Hardness

To predict the final size of a search tree, the authors first establish a formal measure of search progress called "hardness." In this framework, the root node is assigned a hardness value of 1. This value is then distributed among its children such that the sum of the children's hardness equals the parent's. As the solver explores the tree, it accumulates "completed hardness" whenever a leaf is reached or a subtree is pruned.

Figure 1: Hardness schemes for tree nodes. (a) shows a uniform distribution, while (b) shows a non-uniform distribution ($p_k$) based on branching probabilities.

While the authors primarily utilized uniform probabilities for their core implementation, they also explored non-uniform schemes ($p_k$) that incorporate branching information to more accurately reflect the difficulty of different subtrees.

Static linear extrapolation often fails to predict tree size because search progress is non-linear. To address this, the authors propose a dynamic estimation technique inspired by physics, treating the search as a moving object with velocity and acceleration:

  • Velocity-based estimation: Measures the rate of progress over a moving window of recent nodes, allowing the solver to adapt to local search conditions.
  • Acceleration-based estimation: Accounts for the tendency of search to slow down as it reaches deeper, more complex levels of the tree. This captures trends that static models miss, such as the sudden pruning enabled by finding a new primal solution.
Figure 2: Progress measure vs. leaves sampled for a sample instance. The plot compares the uniform ($p_u$) and non-uniform ($p_k$) estimators against the actual search progress.

As shown in Figure 2, these estimators track the actual progress of the search, providing a basis for predicting the total number of nodes required to complete the tree.

The Clairvoyant Restart Strategy

The "clairvoyant" strategy triggers a restart when the estimated total tree size ($T$) is significantly larger than the work already performed. Specifically, if the estimate suggests the tree will be 100 times larger than the current node count, the solver "bails out." To ensure stability and prevent infinite restart loops, the strategy includes safeguards: the restart condition must be met for 50 consecutive nodes, and a minimum of 1,000 nodes must have been processed.

The primary goal of the restart is not just to start over, but to improve branching heuristics. The information gathered during the initial, failed search is used to make better decisions at the root upon restarting.

Experimental Results

The strategy was implemented in the SCIP solver and evaluated against the MMMc benchmark, a collection of 496 instances from MIPLIB and COR@L. The researchers focused on "hard" instances (those requiring $\ge$ 1,000 nodes).

The "window-acc" (moving window with acceleration) configuration proved most effective:

  • Overall Performance: Achieved a 4% average speedup across the entire benchmark.
  • Hard Instances: On the most difficult problems, the strategy yielded a 10.5% reduction in runtime and a 14% reduction in nodes explored.

These results are significant given that modern MIP solvers like SCIP are already highly optimized. The clairvoyant strategy successfully outperformed default settings by identifying and correcting poor early branching paths.

Conclusion and Future Work

This research demonstrates that online tree-size estimation is a viable and effective trigger for restarts in MIP. By treating search progress as a dynamic process with acceleration, solvers can better predict the utility of continuing a search versus restarting. Future work may explore sequences of multiple restarts and more aggressive information transfer—such as generating cutting planes—from the initial search to the restarted one.

Summary updated

BibTeX
@inproceedings{anderson2019clairvoyant,
  author = {Daniel Anderson and Gregor Hendel and Pierre Le Bodic and Merlin Viernickel},
  title = {{Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33011427},
}
Figure