Hybrid models for learning to branch

Conference item

A recent Graph Neural Network (GNN) approach for learning to branch has been shown to successfully reduce the running time of branch-and-bound (B&B) algorithms for Mixed Integer Linear Programming (MILP). While the GNN relies on a GPU for inference, MILP solvers are purely CPU-based. This severely limits its application as many practitioners may not have access to high-end GPUs. In this work, we ask two key questions. First, in a more realistic setting where only a CPU is available, is the GNN model still competitive? Second, can we devise an alternate computationally inexpensive model that retains the predictive power of the GNN architecture? We answer the first question in the negative, and address the second question by proposing a new hybrid architecture for efficient branching on CPU machines. The proposed architecture combines the expressive power of GNNs with computationally inexpensive multi-layer perceptrons (MLP) for branching. We evaluate our methods on four classes of MILP problems, and show that they lead to up to 26% reduction in solver running time compared to state-of-the-art methods without a GPU, while extrapolating to harder problems than it was trained on. The code for this project is publicly available at https://github.com/pg2455/Hybrid-learn2branch.

Authors: Gupta, P; Gasse, M; Khalil, EB; Mudigonda, P; Lodi, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Conference on Neural Information Processing Systems
• Host title: Advances in Neural Information Processing Systems 33 (NeurIPS 2020)
• Publication date: 2020-12-12
• Acceptance date: 2020-09-25
• Event title: NeurIPS 2020
• Event series: Annual Conference on Neural Information Processing Systems
• Event location: Online
• Event website: https://nips.cc/Conferences/2020
• Event start date: 2020-12-06
• Event end date: 2020-12-12
• Language: English
• Keywords: FFR