PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers

Abstract

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.

Neuro-symbolic Methods, Neural Combinatorial Optimization, Geometric Deep Learning

References in corpus (9)

• Modularity and community structure in networks
• Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling
• Geometric deep learning: going beyond Euclidean data
• Learning Combinatorial Optimization Algorithms over Graphs
• SATzilla: Portfolio-based Algorithm Selection for SAT
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• Deeply Learning the Messages in Message Passing Inference
• Comparing Beliefs, Surveys and Random Walks

Cited by in corpus (6)

• Goal-Aware Neural SAT Solver
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• Deep Reasoning Networks: Thinking Fast and Slow
• From Shallow to Deep Interactions Between Knowledge Representation, Reasoning and Machine Learning (Kay R. Amel group)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis
• The deep learning and statistical physics applications to the problems of combinatorial optimization