Description
This project tries to build an end-to-end graph neural network model to predict the satisfiability of decision pseudo-Boolean problem, which is known as NP-Complete. The model mainly consists of four parts: i) constraint normalization, ii) graph construction, iii) message passing and iv) readout. From experimental results, the model achieves good accuracy on different benchmarks with ~40 variables.
The paper Learning the Satisfiability of Pseudo-Boolean Problem with Graph Neural Networks is presented at CP 2020, which could be downloaded through this link. An introductory video is available here.