Franco Alberto Cardillo, Hamza Khyari, Riccardo Paoli, Umberto Straccia.

MILP-SAT-GNN: Yet Another Neural SAT solver.

In Proceedings of the 30th International Conference on Knowledge-Based and Intelligent Information \& Engineering Systems (KES-26),  2026.

Abstract:

We propose a novel method that enables Graph Neural Networks (GNNs) to solve SAT problems by leveraging a technique developed for applying GNNs to Mixed Integer Linear Programming (MILP). Specifically, k-CNF formulae are mapped into MILP problems, which are then encoded as weighted bipartite graphs and subsequently fed into a GNN for training and testing. We illustrate some theoretical results and conduct an experimental evaluation showing that, despite the simplicity of the neural architecture, the method achieves promising results.