Neural Algorithmic Reasoning for Combinatorial Optimisation

Dobrik Georgiev Georgiev, Danilo Numeroso, Davide Bacciu, Pietro Lio
Proceedings of the Second Learning on Graphs Conference, PMLR 231:28:1-28:15, 2024.

Abstract

Solving NP-hard/complete combinatorial problems with neural networks is a challenging research area that aims to surpass classical approximate algorithms. The long-term objective is to outperform hand-designed heuristics for NP-hard/complete problems by learning to generate superior solutions solely from training data. Current neural-based methods for solving CO problems often overlook the inherent "algorithmic" nature of the problems. In contrast, heuristics designed for CO problems, e.g. TSP, frequently leverage well-established algorithms, such as those for finding the minimum spanning tree. In this paper, we propose leveraging recent advancements in neural algorithmic reasoning to improve the learning of CO problems. Specifically, we suggest pre-training our neural model on relevant algorithms before training it on CO instances. Our results demonstrate that, using this learning setup, we achieve superior performance compared to non-algorithmically informed deep learning models.

Cite this Paper

BibTeX
@InProceedings{pmlr-v231-georgiev24a, title = {Neural Algorithmic Reasoning for Combinatorial Optimisation}, author = {Georgiev, Dobrik Georgiev and Numeroso, Danilo and Bacciu, Davide and Lio, Pietro}, booktitle = {Proceedings of the Second Learning on Graphs Conference}, pages = {28:1--28:15}, year = {2024}, editor = {Villar, Soledad and Chamberlain, Benjamin}, volume = {231}, series = {Proceedings of Machine Learning Research}, month = {27--30 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v231/georgiev24a/georgiev24a.pdf}, url = {https://proceedings.mlr.press/v231/georgiev24a.html}, abstract = {Solving NP-hard/complete combinatorial problems with neural networks is a challenging research area that aims to surpass classical approximate algorithms. The long-term objective is to outperform hand-designed heuristics for NP-hard/complete problems by learning to generate superior solutions solely from training data. Current neural-based methods for solving CO problems often overlook the inherent "algorithmic" nature of the problems. In contrast, heuristics designed for CO problems, e.g. TSP, frequently leverage well-established algorithms, such as those for finding the minimum spanning tree. In this paper, we propose leveraging recent advancements in neural algorithmic reasoning to improve the learning of CO problems. Specifically, we suggest pre-training our neural model on relevant algorithms before training it on CO instances. Our results demonstrate that, using this learning setup, we achieve superior performance compared to non-algorithmically informed deep learning models.} }
Endnote
%0 Conference Paper %T Neural Algorithmic Reasoning for Combinatorial Optimisation %A Dobrik Georgiev Georgiev %A Danilo Numeroso %A Davide Bacciu %A Pietro Lio %B Proceedings of the Second Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2024 %E Soledad Villar %E Benjamin Chamberlain %F pmlr-v231-georgiev24a %I PMLR %P 28:1--28:15 %U https://proceedings.mlr.press/v231/georgiev24a.html %V 231 %X Solving NP-hard/complete combinatorial problems with neural networks is a challenging research area that aims to surpass classical approximate algorithms. The long-term objective is to outperform hand-designed heuristics for NP-hard/complete problems by learning to generate superior solutions solely from training data. Current neural-based methods for solving CO problems often overlook the inherent "algorithmic" nature of the problems. In contrast, heuristics designed for CO problems, e.g. TSP, frequently leverage well-established algorithms, such as those for finding the minimum spanning tree. In this paper, we propose leveraging recent advancements in neural algorithmic reasoning to improve the learning of CO problems. Specifically, we suggest pre-training our neural model on relevant algorithms before training it on CO instances. Our results demonstrate that, using this learning setup, we achieve superior performance compared to non-algorithmically informed deep learning models.
APA
Georgiev, D.G., Numeroso, D., Bacciu, D. & Lio, P.. (2024). Neural Algorithmic Reasoning for Combinatorial Optimisation. Proceedings of the Second Learning on Graphs Conference, in Proceedings of Machine Learning Research 231:28:1-28:15 Available from https://proceedings.mlr.press/v231/georgiev24a.html.

Related Material