Learning to Search in Branch and Bound Algorithms

TLDR

Branch‑and‑bound is a widely used method in combinatorial optimization, yet systematic design of the node‑searching strategy remains largely unexplored. The study aims to learn an adaptive node‑searching order applicable to any branch‑and‑bound solvable problem. Using imitation learning, the authors train strategies for linear‑programming based branch‑and‑bound on mixed‑integer programs and benchmark them against SCIP and Gurobi. The learned strategy finds better solutions faster on four benchmark MIP libraries.

Abstract

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.