Glossary of CP terms

Some terms commonly used in CP might require some explanation for readers with an Operations Research background. The following list is an extract from [Hei99].

Finite domain constraint problem/constraint satisfaction problem (CSP): defined by a finite set of variables taking values from finite domains and a (conjunctive) set of constraints on these variables. The objective may be either finding one solution (any or an optimal) or all solutions (consistent assignment of values to the variables so that all the constraints are satisfied simultaneously) for the given instance. The term constraint network is frequently employed to denote CP problems in allusion to the graphical representation as a hyper graph (constraint graph), where nodes represent variables, and constraints are (hyper) arcs linking several nodes. There is no standard problem representation in CP.

Model: a CP model specifies all variables, their domains and their declarative meaning and conceptual constraints imposed on them (as opposed to actual constraints that are used to implement the properties of the solution and the search process). In CP in general, a model preserves much problem-specific knowledge about variables and the relations between them. This allows the development and application of more efficient specialized solution strategies.

Variable: object that has a name and a domain (also referred to as decision variable).

Domain: the set of values (also: labels) a variable may take. In Xpress Kalis, it may consist of discrete values, or intervals of integers. When solving CP problems active use of the domain concept is made. At any stage, the domain of a variable is the set of values that cannot be proved to be inconsistent (with the constraints on this variable) using the available consistency checking methods. Assigning or restricting domains is often interpreted as unary constraints on the corresponding variables.

Instantiation of a set of variables is an assignment of a value to each variable from its domain, also called labeling of each variable with a value from its domain.

Consistent instantiation of a constraint network is an instantiation of the variables such that the constraints between variables are satisfied, also called admissible/satisfied instantiation, consistent assignment of values, or consistent labeling. Solution is often used as a synonym for consistent instantiation, but may also denote the result after applying any (local/partial) consistency algorithm.

Constraint: a relation over a set of variables limiting the combination of values that these variables can take; constraints may also be interpreted as mappings from the domains of the variables onto the Boolean values true and false. A (conceptual) constraint can sometimes be implemented in different ways enforcing various levels of consistency (see below) with different computational overhead. So-called global constraints subsume a set of other constraints (for instance an `all-different' relation on a set of variables replaces pair wise disequality constraints). Global constraints use specific propagation/consistency algorithms that render them more efficient than the set of constraints they replace.

Redundant constraints: a constraint is redundant with respect to a set of constraints, if it is satisfied when the set of constraints is satisfied. Although redundant constraints do not change the set of solutions (consistent instantiations) of a problem, in practice it may be useful to add redundant constraints to the model formulation because they can help CP solution procedures, particularly by achieving more powerful constraint propagation.

System of constraints: a conjunctive set of constraints, usually built up incrementally.

Constraint solving: deciding the consistency or satisfiability of a system of constraints.

Solution methods: finite domain CP problems are usually solved by tree search methods (Branch-and-Bound for optimization, Branch-and-Prune for decision problems) that enumerate the possible values of the variables coupled with consistency algorithms. In tree search methods with consistency checking the local consistency algorithm is triggered by the propagation of the domain changes of the branching variable. For optimization usually a cost constraint is introduced that propagates to the variables. It is updated (in the case of minimization: bounded to be smaller than the solution value) each time a new solution is found.

Consistency techniques and constraint propagation: Consistency algorithms remove inconsistent values from the domains of variables. Informally speaking, a consistency algorithm is `stronger' than another one if it reduces the domains further, i.e., it establishes a higher level of consistency. In finite domain CP, typically local consistency algorithms are used. Local or partial consistency signifies that only subsets of the constraints of a system of constraints are simultaneously satisfied. A locally consistent (according to some notion of consistency, such as arc-consistency) constraint network can be obtained by propagating iteratively the effects of each constraint to all other constraints it is connected to through its variables until a stable state is reached. This process is referred to as constraint propagation. Propagation properties of constraints vary, e.g., due to their implementation, or the types of variables used. Possible events triggering their evaluation may be variable instantiation, modification of domain bounds, removing of value(s) from a domain, etc.

Backtrack search augmented by constraint propagation:
while not solved and not infeasible
 check/establish (local) consistency
 if a dead end is detected
   then backtrack to the first open node
 else
   select a variable
   select a value for the variable

Search algorithms/strategies: The values for variables come out of an enumeration process. `Intelligent' enumeration strategies adapted to special types of constraints and variables are a central issue in CP. The search is controlled by problem specific heuristics, strategies from Mathematical Programming or the expert's knowledge; fixing variables to trial values is possible. One can distinguish variable and value selection heuristics. Due to the way the backtracking mechanism works, usually depth-first search is used.

Constraint solver: (Also: constraint engine.) Distinction between exact and incomplete solvers. Exact solvers guarantee the satisfiability of the system of constraints at any stage of the computations, they usually work on rational numbers (trees of rationals and linear constraints). Incomplete solvers are designed for more complex domains such as integers where checking and maintaining consistency of the overall system is too expensive or not possible with presently known algorithms. These solvers work with simplified calculations establishing some sort of partial (local) consistency among constraints; usually simply stating constraints does not produce a solution, an enumeration phase (searching for solutions) is necessary.