Exact Combinatorial Optimization with Temporo-Attentional Graph Neural
  Networks
Mehdi Seyfi Amin Banitalebi-Dehkordi Zirui Zhou Yong Zhang
Combinatorial optimization finds an optimal solution within a discrete set of
variables and constraints. The field has seen tremendous progress both in
research and industry. With the success of deep learning in the past decade, a
recent trend in combinatorial optimization has been to improve state-of-the-art
combinatorial optimization solvers by replacing key heuristic components with
machine learning (ML) models. In this paper, we investigate two essential
aspects of machine learning algorithms for combinatorial optimization: temporal
characteristics and attention. We argue that for the task of variable selection
in the branch-and-bound (B&B) algorithm, incorporating the temporal information
as well as the bipartite graph attention improves the solver's performance. We
support our claims with intuitions and numerical results over several standard
datasets used in the literature and competitions. Code is available at:
https://developer.huaweicloud.com/develop/aigallery/notebook/detail?id=047c6cf2-8463-40d7-b92f-7b2ca998e935