  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.

Machine Learning;Neural and Evolutionary Computing;Combinatorics