Learning to Branch in Combinatorial Optimization with Hybrid Convolutional and Attentional Graph Neural Networks

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.