Learning to Search in Branch-and-Bound Algorithms ⇤
Branch-and-bound is a widely used method in combinatorial optimization, including mixed integer programming, structured prediction and MAP inference. While most work has been focused on developing problem-specific techniques, little is known about how to systematically design the node searching strategy on a branch-and-bound tree. We address the key challenge of learning an adaptive node searching order for any class of problem solvable by branch-and-bound. Our strategies are learned by imitation learning. We apply our algorithm to linear programming based branch-and-bound for solving mixed integer programs (MIP). We compare our method with one of the fastest open-source solvers, SCIP; and a very efficient commercial solver, Gurobi. We demonstrate that our approach achieves better solutions faster on four MIP libraries.
The paper present a heuristic for node selection in Branch and Bound for Mixed Integer Programs based on machine learning.     Although machine learning used for node selection is not new the paper present a new approach (to the best of my knowledge).    They utilize a classifier together with an oracle for training two aspects: a node selection policy and a node pruning policy.    The first one is used to enforce a linear order/priority on the current open nodes of the Branch and Bound while the second one is used to further shrink the list of open nodes by pruningthe unpromising ones. The results look very promising compared to a state-of-the-art solver (Gurobi).The paper is well written and easy to follow, however I would have liked to read more details on their experimental setup. In particular it is not clear which kind of LP solver is used together with DAgger (is it Gurobi itself or another one?). Also some tuning parameters in page 6 are reported without explaining the process to arrive to such parameters.The related work section should also be strengthened. Here, I report a couple of references that might be worth considering:- "A Supervised Machine Learning Approach to Variable Branching in Branch-And-Bound" by Alvarez, Louveaux, Wehenkel- "Guiding Combinatorial Optimization with UCT" by Sabharwal, Samulowitz, ReddyDespite the encouraging results, a more thorough experimental section would be also helpful and insightful.For instance, it is not clear to me what is the main contribution that comes from the node selection independently from node pruning. A more extensive experimental result section showing these two aspects separetely would be insightful. Furthermore, despite the optimality gap compared to Gurobi looks indeed good, the method is inherently incomplete because of the pruning (as pointed out by the authors as well). How does it compare if only $\pi_s$ is used? A comparison based on a larger data set (not in term of instances but in term of different classes of problems) would also be welcome addition.Which were the features extracted for training that were the most relevant among the one you used?Finally, the presence of an oracle knowing the optimal solution is necessary in your setup. This is rarely the case when solving real-life problems. One could easily think of running an off-the-shelf solver with a reasonable timeout on those problems and then use the best solution found for training. The question would then be: how robust is the solution proposed when used with sub-optimal oracles?[Minor Comments]- I would suggest the author to use a grey-scale friendly version of figures (that otherwise are difficult to follow when printed in grey-scale)- Page 3, 3rd paragraph: there is a reference to a "Figure 3". Is it the correct reference?- Page 4, Figure 2: I believe the state machine describing the online algorithm is missing the case in which there are no feasible solutions.- Page 4, end of the page: "at any time there can be at most one optimal node on the queue". This is in general not true for a traditional Branch and Bound setting. You may want to specify that this applies only to the specific setup.Addendum: Thanks for answering a good portion of the questions above in the rebuttal.