Learning to Branch in Combinatorial Optimization with Hybrid Convolutional and Attentional Graph Neural Networks
Xilin Zhang, Shenshen Gu · 2024
Solving combinatorial optimization problems holds significant practical importance, and many such problems can be transformed into MILP problems. Currently, Branch-and-Bound (B&B) is a typical method for solving Mixed-Integer Linear Programming (MILP) problems. In this paper, we propose a hybrid convolutional and attentional graph neural network to learn the variable selection policy in B&B. The model combines graph convolutional and graph attention mechanisms, achieving more efficient node embeddings and reducing computational time. The mathematical model of MILP is transformed into a bipartite graph structure, which effectively extracts features. The B&B solving process is mapped to a Markov decision process, and imitation learning is used to train the model. By solving a series of combinatorial optimization problems that can be transformed into MILP problems, we validate that our model can improve B&B. Experimental results show that our model outperforms state-of-the-art branching machine learning methods and generalizes to problems of different scales.