Using deep learning to construct stochastic local search SAT solvers with performance bounds

The article by Maximilian J. Kramer and Paul Boes from Porsche Digital GmbH focuses on the use of deep learning to improve the performance of Stochastic Local Search (SLS) SAT solvers. The authors train oracles using Graph Neural Networks (GNN) and evaluate their performance on two SLS solvers on random SAT instances. Their findings indicate that access to GNN-based oracles significantly boosts the performance of both solvers. This work bridges the gap between theoretical computer science and practical research on deep learning for constraint satisfaction problems.

Publication date: 20 Sep 2023
Project Page: https://arxiv.org/abs/2309.11452v1
Paper: https://arxiv.org/pdf/2309.11452