Tech Report CS-91-62

Constraint Satifaction Using Constraint Logic Programming

Pascal Van Hentenryck, Helmut Simonis and Mehmet Dincbas

November 1991


Constraint logic programming is a new class of declarative programming languages whose primitive operations are based on constraints (e.g. constraint solving and constraint entailment). CLP languages naturally combine constraint propagation with nondeterministic choices. As a consequence, they are particularly appropriate for solving a variety of combinatorial search problems (using the global search paradigm) with a short development time and an efficiency comparable to procedural tools (using the same approach). In this paper, we describe how the CLP language {\em cc(FD)}, a successor of CHIP using consistency techniques over finite domains, can be used to solve two practical applications: test-pattern generation and car-sequencing. For both applications, we present the $cc(FD)$ program, describe how constraint solving is performed, report experimental results, and compare the approach with existing tools.

(complete text in pdf)