PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers
This work addresses the problem of improving neural-based solvers for constraint satisfaction problems, offering a novel framework that could benefit researchers in AI and optimization, but it appears incremental as it builds on existing neural embedding models.
The paper tackles the challenge of learning constraint satisfaction solvers with neural networks by proposing a general framework called PDP that learns search strategies beyond greedy search through probabilistic inference and unsupervised training. The results show effectiveness in SAT solving compared to neural and state-of-the-art baselines, though no concrete numbers are provided.
There have been recent efforts for incorporating Graph Neural Network models for learning full-stack solvers for constraint satisfaction problems (CSP) and particularly Boolean satisfiability (SAT). Despite the unique representational power of these neural embedding models, it is not clear how the search strategy in the learned models actually works. On the other hand, by fixing the search strategy (e.g. greedy search), we would effectively deprive the neural models of learning better strategies than those given. In this paper, we propose a generic neural framework for learning CSP solvers that can be described in terms of probabilistic inference and yet learn search strategies beyond greedy search. Our framework is based on the idea of propagation, decimation and prediction (and hence the name PDP) in graphical models, and can be trained directly toward solving CSP in a fully unsupervised manner via energy minimization, as shown in the paper. Our experimental results demonstrate the effectiveness of our framework for SAT solving compared to both neural and the state-of-the-art baselines.