Formalization as a Constraint Satisfaction Problem

A CSP is a triple $<X,D,C>$ where:

• $X$ is a set of decision variables $\{X_1,...,X_n\}$
• $D$ is a set of domains $\{D_1,...,D_n\}$ for $X$:
  • $D_i$ is a set of possible values for $X_i$
  • Usually non-binary and assume finite domain
• $C$ is a set of constrains $\{C_1,...,C_n\}$
  • $C_i$ is a relation over a subset of variables $\{X_j,...,X_k\}$, denoted as $C_i(X_j,...,X_k)$
  • $C_i$ is a set of combinations of allowed values $C_i\subseteq D(X_j)\wedge ...\wedge D(X_k)$

A solution to a CSP is an assignment of values to the variables which satisfies all constraints simultaneously

Formally, $<X,D,C,f>$ where f is the formalization of the optimization criterion as an objective variable. Goal: minimize f (maximize –f).

• Choice of variables and domains defines the search space size
• Choice of constraints defines:
  • how search space can be reduced;
  • how search can be guided.

Properties of Constraints

• The order of imposition does not matter.
  • X + Y ≤ Z is the same as Z ≥ X + Y.
• Non-directional.
  • A constraint between X and Y can be used to infer domain information on Y given domain information on X and vice versa.
• Rarely independent.
  • Shared variables as communication mechanism between different constraints.