Estimating the Size of Branch-and-Bound Trees

Gregor Hendel (), Daniel Anderson (), Pierre Le Bodic () and Marc E. Pfetsch ()
Additional contact information
Gregor Hendel: Zuse Institute Berlin, Berlin 14195, Germany
Daniel Anderson: Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Pierre Le Bodic: Faculty of Information Technology, Monash University, Melbourne, Victoria 3800, Australia
Marc E. Pfetsch: Department of Mathematics, TU Darmstadt, Darmstadt 64289, Germany

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 934-952

Abstract: This paper investigates the problem of estimating the size of branch-and-bound (B&B) trees for solving mixed-integer programs. We first prove that the size of the B&B tree cannot be approximated within a factor of 2 for general binary programs, unless P = N P . Second, we review measures of progress of the B&B search, such as the well-known gap and the often-overlooked tree weight, and propose a new measure, which we call leaf frequency . We study two simple ways to transform these progress measures into B&B tree-size estimates, either as a direct projection or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using machine learning techniques, which yield more precise estimates than any individual measure. The best method that we have identified uses all individual measures as features of a random forest model. In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B&B tree sizes within a factor of 3 on the set of unseen test instances, even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor of 2 over the entire search on each of the six additional sets of homogeneous instances that we tested. All techniques are available in version 7 of the branch-and-cut framework SCIP. Summary of Contribution: This manuscript develops a method for online estimation of the size of branch-and-bound trees, thereby combining methods of mixed-integer programming and machine learning. We show that high-quality estimations can be obtained using the presented techniques. The methods are also useful in everyday use of branch-and-bound algorithms to obtain approximate search-completion information. The manuscript is accompanied by an extensive online supplement comprising the code used for our simulations and an implementation of all discussed methods in the academic solver SCIP, together with the tools and instructions to train estimators for custom instance sets.

Keywords: branch and bound; tree-size estimation; time-series forecasting; machine learning (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1103 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:2:p:934-952

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().