A SAT-Based Version Space Algorithm for Acquiring Constraint Satisfaction Problems
Abstract
Constraint programming is rapidly becoming the technology of choice for modelling and solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their problems appropriately. The lack of availability of such expertise is a significant bottleneck to the broader uptake of constraint technology in the real world. We present a new SAT-based version space algorithm for acquiring constraint satisfaction problems from examples of solutions and non-solutions of a target problem. An important advantage is the ease with which domain-specific knowledge can be exploited using the new algorithm. Finally, we empirically demonstrate the algorithm and the effect of exploiting domain-specific knowledge on improving the quality of the acquired constraint network.
Cite
Text
Bessiere et al. "A SAT-Based Version Space Algorithm for Acquiring Constraint Satisfaction Problems." European Conference on Machine Learning, 2005. doi:10.1007/11564096_8Markdown
[Bessiere et al. "A SAT-Based Version Space Algorithm for Acquiring Constraint Satisfaction Problems." European Conference on Machine Learning, 2005.](https://mlanthology.org/ecmlpkdd/2005/bessiere2005ecml-satbased/) doi:10.1007/11564096_8BibTeX
@inproceedings{bessiere2005ecml-satbased,
title = {{A SAT-Based Version Space Algorithm for Acquiring Constraint Satisfaction Problems}},
author = {Bessiere, Christian and Coletta, Remi and Koriche, Frédéric and O'Sullivan, Barry},
booktitle = {European Conference on Machine Learning},
year = {2005},
pages = {23-34},
doi = {10.1007/11564096_8},
url = {https://mlanthology.org/ecmlpkdd/2005/bessiere2005ecml-satbased/}
}