Learning to Branch in Combinatorial Optimization with Graph Pointer Networks
This work addresses the efficiency of combinatorial optimization solvers, which is crucial for operations research and logistics, though it is incremental as it builds on existing branch-and-bound and machine learning techniques.
The paper tackled the problem of variable selection in branch-and-bound for combinatorial optimization by proposing a graph pointer network model, which significantly outperformed expert-designed rules and state-of-the-art machine learning methods in solving speed and search tree size on benchmark problems.
Branch-and-bound is a typical way to solve combinatorial optimization problems. This paper proposes a graph pointer network model for learning the variable selection policy in the branch-and-bound. We extract the graph features, global features and historical features to represent the solver state. The proposed model, which combines the graph neural network and the pointer mechanism, can effectively map from the solver state to the branching variable decisions. The model is trained to imitate the classic strong branching expert rule by a designed 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. Our approach also outperforms the 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.