Learning to Branch in Combinatorial Optimization with Graph Pointer Networks

Rui Wang

doi:10.1109/JAS.2023.124113

Learning to Branch in Combinatorial Optimization with Graph Pointer Networks

2024-01-01

0

OA

AI

DOI：10.1109/JAS.2023.124113

Original

Original request for help

Save

Abstract

En 中文

Traditional expert-designed branching rules in branch-and-bound (B&B) are static, often failing to adapt to diverse and evolving problem instances. Crafting these rules is labor-intensive, and may not scale well with complex problems. Given the frequent need to solve varied combinatorial optimization problems, leveraging statistical learning to auto-tune B&B algorithms for specific problem classes becomes attractive. This paper proposes a graph pointer network model to learn the branch rules. Graph features, global features and historical features are designated to represent the solver state. The graph neural network processes graph features, while the pointer mechanism assimilates the global and historical features to finally determine the variable on which to branch. The model is trained to imitate the expert strong branching rule by a tailored top-k Kullback-Leibler divergence loss function. Experiments on a series of benchmark problems demonstrate that the proposed approach significantly outperforms the widely used expert-designed branching rules. It also outperforms state-of-the-art machine-learning-based branch-and-bound methods in terms of solving speed and search tree size on all the test instances. In addition, the model can generalize to unseen instances and scale to larger instances.

Keywords:

Branch-and-bound (B&B)

combinatorial optimization

deep learning

graph neural network

imitation learning

Learning to Branch in Combinatorial Optimization with Graph Pointer Networks

Abstract

Journal

Organization