Estimation of the size of Branch-and-Bound trees using ML

Question

A short background:

A paper [1] published in 2006 intends to show that the time needed to solve mixed-integer programming problems by branch and bound can be roughly predicted early in the solution process. Authors mentioned that "The application of the branch-and-bound algorithm can be limited by both the computing time and the storage space required (even when storing nodes on a hard disk). The solution process may take hours or days and there is very little a priori indication of how difficult a model will be to solve. Unfortunately, there is no known method to extract this information from the problem formulation."

on the other hand, commercial solvers are like black boxes, from which extracting useful data about the number of nodes, number of branches and so on, is very hard (I tried to extract related data from Cplex callback functions in Matlab but the trial was unsuccessful). My question is:

Is there any way to use ML techniques to estimate the branch and bound tree size? Are open-source solvers provide such data that can be used to train an ML model and then test the model on benchmark problems?

Doing my homework on searching for answers before asking the question, I can mention the following papers that also aimed to tackle the problem:

• Knuth's method: In [2], two new online methods for estimating the size of backtracking search tree are proposed. They mentioned that, "Knuth’s method estimates $N$, the size of a backtrack tree as $1 + b_1 + b_1.b_2 + . . .$ where $b_i$ is the branching rate observed at depth $i$ using random probing".

• Mentioning the effect of choosing the right variable to branch on, the authors in [3] mentioned that "branching on a variable that does not lead to any serious simplifications on any of the (two) children can be seen as doubling the size of the tree with no improvement, thus leading to extremely large (out of control) search trees."

[1] Cornuéjols, Gérard, Miroslav Karamanov, and Yanjun Li. "Early estimates of the size of branch-and-bound trees." INFORMS Journal on Computing 18.1 (2006): 86-96.

[2] Kilby, Philip, et al. "Estimating search tree size." Proc. of the 21st National Conf. of Artificial Intelligence, AAAI, Menlo Park. 2006.

[3] Lodi, Andrea, and Giulia Zarpellon. "On learning and branching: a survey." Top 25.2 (2017): 207-236.

Answer 1

Great question. You might be interested in this paper here:

Learning MILP Resolution Outcomes Before Reaching Time-Limit by Martina Fischetti, Andrea Lodi, and Giulia Zarpellon.

They don't exactly answer your question but you may see why the question is hard to answer and what partial progress can be made.

A priori estimating the tree size is estimating whether a model is hard to solve or not. From the static features of the instance, without any runtime knowledge (and even with it!), I personally deem this task virtually undoable. But this is just gut feeling.

edit concerning the data: B&B solvers do not provide such data, but of course you can collect this from B&B runs a posteriori.