Building global constraint models from positive examples
Résumé
We present a system which generates global constraint models from few positive examples of problem solutions. In contrast to previous constraint acquisition work, we present a novel approach based on the global constraint catalog and the Constraint Seeker tool which generates models for problems which can be expressed as regular conjunctions of similar constraints. Our system first generates regular groupings of variables in the given samples. The Constraint Seeker is then used to find ranked, typical constraints which match all given positive examples. A dominance check, which removes implied constraints based on meta-data in the constraint catalog, leads to a final ranked set of candidate constraints for each problem. The system is implemented in SICStus Prolog, and heavily relies on the constraint description and evaluators in the global constraint catalog. We show results for more than 200 example problems, ranging from puzzles to sports scheduling, placement and layout problems. The problems range from 4 to over 6000 variables, and use between one and 7000 samples, utilizing over 50 global constraints of the catalog. We achieve an overall hit-rate of about 50%.