Graph Neural Networks for Maximum Constraint Satisfaction.

Area of Science:

• Artificial Intelligence
• Computer Science
• Operations Research

Background:

• Combinatorial optimization problems are frequently modeled as constraint satisfaction problems.
• Existing methods for solving these problems often lack generality or require extensive computational resources.

Purpose of the Study:

• To develop a generic graph neural network architecture capable of solving a wide range of binary constraint satisfaction problems.
• To demonstrate the effectiveness of unsupervised training on smaller instances for generalization to larger problem sizes.

Main Methods:

• Introduction of a novel, generic graph neural network architecture.
• Unsupervised training methodology applied to smaller problem instances.
• Experimental evaluation on diverse combinatorial optimization problems, including Maximum Cut and Maximum Independent Set.

Main Results:

• The proposed graph neural network architecture demonstrates effectiveness across various binary constraint satisfaction problems.
• Networks trained on small instances generalize well to instances at least 10 times larger.
• The generic approach matches or exceeds the performance of specialized greedy and semi-definite programming algorithms.

Conclusions:

• The developed graph neural network offers a powerful and generalizable approach to combinatorial optimization.
• This method provides a competitive alternative to existing state-of-the-art heuristics and algorithms.
• The unsupervised learning strategy enables efficient training and broad applicability.