Tönshoff, Jan and Ritzert, Martin and Wolf, Hinrikus and Grohe, Martin (2021) Graph Neural Networks for Maximum Constraint Satisfaction. Frontiers in Artificial Intelligence, 3. ISSN 2624-8212
pubmed-zip/versions/1/package-entries/frai-03-580607.pdf - Published Version
Download (1MB)
Abstract
Many combinatorial optimization problems can be phrased in the language of constraint satisfaction problems. We introduce a graph neural network architecture for solving such optimization problems. The architecture is generic; it works for all binary constraint satisfaction problems. Training is unsupervised, and it is sufficient to train on relatively small instances; the resulting networks perform well on much larger instances (at least 10-times larger). We experimentally evaluate our approach for a variety of problems, including Maximum Cut and Maximum Independent Set. Despite being generic, we show that our approach matches or surpasses most greedy and semi-definite programming based algorithms and sometimes even outperforms state-of-the-art heuristics for the specific problems.
Item Type: | Article |
---|---|
Subjects: | European Repository > Multidisciplinary |
Depositing User: | Managing Editor |
Date Deposited: | 03 Jan 2023 06:28 |
Last Modified: | 02 Mar 2024 04:10 |
URI: | http://go7publish.com/id/eprint/888 |