ML Anthology

Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks

Mehdi Seyfi, Amin Banitalebi-Dehkordi, Zirui Zhou, Yong Zhang
ECML-PKDD 2023 pp. 268-283
doi:10.1007/978-3-031-43421-1_16 /ecmlpkdd/2023/seyfi2023ecmlpkdd-exact/

Abstract

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

PDF ECML-PKDD Semantic Scholar

Cite

Text

Seyfi et al. "Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2023. doi:10.1007/978-3-031-43421-1_16

Markdown

[Seyfi et al. "Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2023.](https://mlanthology.org/ecmlpkdd/2023/seyfi2023ecmlpkdd-exact/) doi:10.1007/978-3-031-43421-1_16

BibTeX

@inproceedings{seyfi2023ecmlpkdd-exact,
  title     = {{Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks}},
  author    = {Seyfi, Mehdi and Banitalebi-Dehkordi, Amin and Zhou, Zirui and Zhang, Yong},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2023},
  pages     = {268-283},
  doi       = {10.1007/978-3-031-43421-1_16},
  url       = {https://mlanthology.org/ecmlpkdd/2023/seyfi2023ecmlpkdd-exact/}
}