Design, Implementation, and Evaluation of the Constraint Language cc(FD)

This paper describes the design, implementation, and applications of the constraint logic language cc(FD). cc(FD) is a declarative nondeterministic constraint logic language over finite domains based on the cc framework [28], an extension of the CLP scheme [17]. Its constraint solver includes (non-linear) arithmetic constraints over natural numbers which are approximated using domain and interval consistency. The main novelty of cc(FD) is the inclusion of a number of general-purpose combinators, in particular cardinality, constructive disjunction, and blocking implication, in conjunction with new constraint operations such as constraint entailment and generalization. These combinators significantly improve the operational expressiveness, extensibility, and flexibility of CLP languages and allows issues such as the definition of non-primitive constraints and disjunctions to be tackled at the language level. The implementation of cc(FD) (about 40,000 lines of C) includes a WAM-based engi..