Estimating the Branch-and-Bound Search Tree Size

Abstract: "When will this run finish?" is undoubtedly a popular question among users of branch-and-bound based mixed integer programming solvers.

In this talk, we focus on online estimations of the final tree size during the search. We first review existing measures of the search progress such as the (in-)famous gap, and introduce a new measure called leaf-frequency. We then discuss and compare the suitability of the individual measures as predictors of the final tree size either by direct projection or by time series forecasting. Finally, we combine these measures as input of a simple Machine Learning model, which significantly outperforms the prediction accuracy of all individual measures.

This work manifests as a new display column in SCIP 7.0 that displays the approximate search progress percentage, which can be trained further to user instances of interest.

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

---

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.

---