Hong Xu, Sven Koenig, and T. K. Satish Kumar. Effective deep learning for constraint satisfaction problems. In Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming (CP). 2018.
[full text] [BibTeX▼]


A lot of research has been dedicated to applying machine learning techniques to constraint satisfaction problems (CSPs). However, none of them have made use of the recent advances in deep learning. In this paper, we apply deep learning to predict the satisfiabilities of CSPs. To the best of our knowledge, this is the first effective application of deep learning to CSPs that yields \(>99.99\%\) prediction accuracy on random CSPs (with no obvious features that indicate their satisfiabilities). We use a deep convolutional neural network on a matrix representation of CSPs. Since CSPs are NP-hard, labeled data required for training this neural network are in general costly to produce and are thus scarce. We address this issue using the asymptotic behavior of generalized Model A, a new random CSP generation model, along with domain adaptation and data augmentation techniques for CSPs. We demonstrate the effectiveness of our deep learning techniques using experiments on Boolean binary CSPs.

Full Text

Your browser does not support viewing the PDF file inline. Please click the link below to download the file.