A language for optimizing constraint propagation
William S. Havens, Greg Sidebottom · 1993
This thesis describes projection constraints (PCs), a language for compiling and optimizing constraint propagation in the numeric and Boolean domains. An optimizing compiler based on PCs has been implemented in Nicolog, a constraint logic programming (CLP) language. In Nicolog, like other CLP languages such as CHIP, Echidna, CLP(BNR), cc(FD), and clp(FD), domains for variables are explicitly represented and constraint processing is implemented with consistency algorithms. Nicolog compiles each constraint into a set of arc revision procedures, which are expressed as PCs. Instead of using full arc revision based on enumeration, Nicolog uses regions where functions are monotonic to express arc revision procedures in terms of interval computations and branching constructs. Nicolog compiles complex constraints directly, not needing to approximate them with a restricted set of basic constraints or to introduce extra variables for subexpressions. The Nicolog compiler can handle a very general class of constraints, allowing an arbitrary mixture of integer, real, and Boolean operations with a variety of domain representations. The only requirement is that for each domain, it must be possible to compute a set of intervals whose union contains that domain. Nicolog also lets the user program using PCs directly making it possible to implement sophisticated arc revision procedures. This thesis shows that PCs are a simple, efficient, and flexible way to implement consistency algorithms for complex mixed numeric and boolean constraints. Empirical results with a prototype Nicolog implementation show it can solve hard problems with speed comparable to the fastest CLP systems.