A constraint network (CN) consists of a set of variables; domains of possible values associated with each of these variables; and a set of constraints that link up the variables and define the set of combinations of values that are allowed. The search for an instantiation of all variables that satisfies all the constraints is called a Constraint Satisfaction Problem (CSP), and such an instantiation is called a solution of a CSP.
A lot of problems can be easily coded in terms of CSP. For instance, CSP has already been used to solve problems of scene analysis, placement, resource allocation, crew scheduling, time tabling, scheduling, frequency allocation, car sequencing, and so on.
Unfortunately, a CSP is an NP-Complete problem. Thus, much work has been carried out in order to try to reduce the time needed to solve a CSP. Constraint Programming (CP) is one of these techniques.
Constraint Programming proposes to solve CSPs by associating with each constraint a filtering algorithm that removes some values of variables that cannot belong to any solution of the CSP. These filtering algorithms are repeatedly called until no new deduction can be made. This process is called the propagation mechanism. Then, CP uses a search procedure (like a backtracking algorithm) where filtering algorithms are systematically applied when the domain of a variable is modified. Therefore, with respect to the current domains of the variables and thanks to filtering algorithms, CP removes once and for all certain inconsistencies that would have been discovered several times otherwise. Thus, if the cost of the calls of the filtering algorithms at each node is less than the time required by the search procedure to discover many times the same inconsistency, then the resolution will be speeded up.
