TL;DR
This paper introduces a novel offline method for estimating the size of Branch & Bound (B&B) search trees by combining Knuth's sampling technique with domain knowledge derived from abstract B&B models. This approach significantly reduces estimation error compared to standard sampling, paving the way for more efficient B&B algorithm development and analysis.
What Problem Does This Paper Address?
Branch & Bound (B&B) algorithms are fundamental for solving complex optimization problems, particularly Mixed-Integer Programming (MIP). A critical challenge in B&B is estimating the size (and thus the runtime) of the search tree that will be explored. This is difficult because the search space can be enormous, and a provably optimal solution might take years to find with current methods. Accurate tree-size estimation is crucial for several reasons: informing users about expected termination times, selecting optimal search strategies, guiding restart procedures, and enabling efficient parallelization through better load balancing. While online estimation (predicting during the search) is the ultimate goal, this paper focuses on offline estimation (predicting from a known subtree), which is a necessary precursor. The core problem is how to leverage existing knowledge about the B&B process to make these estimations more precise.
Methods
The paper builds upon two key existing techniques:
- Knuth's Sampling Method [Knuth, 1975]: This method estimates tree size by randomly sampling paths from the root to leaves. The core idea is that the expected value of these samples is an unbiased estimator of the true tree size. However, using uniform sampling probabilities can lead to high variance in estimates.
- Abstract Models of B&B Trees [Le Bodic and Nemhauser, 2017]: These models provide a simplified yet insightful framework for understanding B&B tree growth, particularly for the Single Variable Branching (SVB) problem. They derive characteristic growth rates (represented by $\phi$) that describe how the tree expands.
The paper's novel contribution is the combination of these two methods. Specifically, they propose using the domain knowledge extracted from the abstract B&B models (the growth rate $\phi$) to define importance sampling probabilities for Knuth's algorithm. Instead of sampling uniformly, the algorithm now samples branches with probabilities proportional to the expected distribution of nodes in the B&B tree, derived from $\phi$. This "domain-knowledge-informed" sampling aims to reduce the variance of the tree-size estimates.
Datasets
The paper evaluates its method on 87 MIP instances from the MIPLIB 2010 benchmark set. After filtering out instances that timed out, exceeded memory limits, were too small, or generated excessively large output files, 63 instances were used for the experiments.
Key Insights and Ideas
- Domain Knowledge is Key to Variance Reduction: The most significant insight is that incorporating knowledge about how B&B trees grow (even from simplified models) dramatically reduces the variance of tree-size estimates. This is because the sampling becomes more "intelligent," focusing on more probable branches.
- Abstract Models Provide Practical Probabilities: The abstract models, while simplified, provide a quantifiable measure ($\phi$) that can be directly translated into practical sampling probabilities. This bridges the gap between theoretical B&B properties and algorithmic implementation.
- Offline Estimation is a Strong Precursor: The success in offline estimation suggests that the underlying principles are sound and can potentially be adapted for online prediction, although significant challenges remain.
- Complementarity of Methods: The paper highlights how Knuth's sampling and the abstract B&B models are not competing but rather complementary techniques, each providing essential components for a more effective estimation system.
Key Results
- Offline Estimation Error Halved: The proposed method using domain-knowledge-informed sampling (pk) more than halved the imprecision compared to uniform sampling (pu) in offline tree-size estimation. This was measured by the Mean Absolute Percentage Error (MAPE).
- Improved Precision: For the 63 MIP instances, the pk method won in terms of estimation precision over pu in 509 cases compared to 121 wins for pu.
- Variance Reduction: Experiments showed a drastic reduction in variance when using probabilities derived from domain knowledge, especially when compared to uniform probabilities.
- Online Estimation Challenges: While the offline results are promising, the paper notes that applying the method to the online setting (using the actual traversal order of leaves) leads to significantly degraded performance and peculiar estimation patterns, indicating that further research is needed.
Limitations and Future Work
- Online Estimation Performance: The primary limitation is the poor performance of the proposed method in the online setting. The estimation error can be substantial, and the patterns observed are often impractical. The authors acknowledge that this requires further investigation.
- Need for Further Research in Online Settings: Future work should focus on understanding why the online performance differs so drastically from the offline results. Potential directions include developing resampling techniques within traversed leaves or finding methods that can explain the observed behavior.
- Applicability to Other Procedures: The direct applicability of this method is currently limited to B&B algorithms for which domain knowledge on node distribution is available. However, the authors anticipate that this study will lead to similar improvements for other search-tree-based procedures.
Summary updated