Unsupervised Constraint Acquisition

Constraint programming has been successfully used to model and solve problems in many domains, but its application can require significant expertise. This is sometimes called a modelling bottleneck, and the aim of constraint acquisition (CA) is to remove the bottleneck by automating constraint modelling. Current CA methods use forms of supervised learning: they learn constraints from a dataset of known solutions and (usually) non-solutions. Unfortunately this incurs a data collection bottleneck, as preparing such a dataset requires human effort. Removing this bottleneck might lead to the full automation of CA, for example allowing the use of data scraped from the Web without human intervention. In this paper we propose an unsupervised CA method inspired by data mining techniques, and show that it can learn several CA benchmarks. We also show that it has additional useful properties: it is robust under data errors, can learn from non-solutions only, and can learn over-constrained models.