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 [Formula: see text]. 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.

Many practical applications require the solution of numerically challenging linear programs (LPs) and mixed integer programs (MIPs). Scaling is a widely used preconditioning technique that aims at reducing the error propagation of the involved linear systems, thereby improving the numerical behavior of the dual simplex algorithm and, consequently, LP-based branch-and-bound. A reliable scaling method often makes the difference whether these problems can be solved correctly or not. In this paper, we investigate the use of machine learning to choose at the beginning of the solution process between two common scaling methods: Standard scaling and Curtis-Reid scaling. The latter often, but not always, leads to a more robust solution process, but may suffer from longer solution times. Rather than training for overall solution time, we propose to use the attention level of a MIP solution process as a learning label. We evaluate the predictive power of a random forest approach and a linear regressor that learns the (square-root of the) difference in attention level. It turns out that the resulting classification not only reduces various types of numerical errors by large margins, but it also improves the performance of the dual simplex algorithm. The learned model has been implemented within the FICO Xpress MIP solver and it is used by default since release 8.9, May 2020, to determine the scaling algorithm Xpress applies before solving an LP or a MIP.

We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for MixedInteger Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.