Learning To Dive In Branch And Bound
This work addresses the inefficiency of existing diving heuristics in combinatorial optimization for applications like server load balancing and neural network verification, representing a novel method for a known bottleneck.
The paper tackled the problem of primal heuristics in mixed integer linear programs by proposing L2Dive, a method that learns diving heuristics with graph neural networks, resulting in up to 35% improvement in primal-dual integral and 29% reduction in solving time for real-world applications.
Primal heuristics are important for solving mixed integer linear programs, because they find feasible solutions that facilitate branch and bound search. A prominent group of primal heuristics are diving heuristics. They iteratively modify and resolve linear programs to conduct a depth-first search from any node in the search tree. Existing divers rely on generic decision rules that fail to exploit structural commonality between similar problem instances that often arise in practice. Therefore, we propose L2Dive to learn specific diving heuristics with graph neural networks: We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions based on the model's predictions. L2Dive is fully integrated into the open-source solver SCIP. We find that L2Dive outperforms standard divers to find better feasible solutions on a range of combinatorial optimization problems. For real-world applications from server load balancing and neural network verification, L2Dive improves the primal-dual integral by up to 7% (35%) on average over a tuned (default) solver baseline and reduces average solving time by 20% (29%).