How to deal with Constraints having Large or Infinite Domains.

Question

This presentation gives an overview of Constraint Satisfaction Problems (CSPs). An example they give is this:

• Variables: $X = \{X_1, X_2, X_3\}$
• Domains: $D(X_1) = \{1,2\}, D(X_2) = \{0,1,2,3\}, D(X_3) = \{2,3\}$
• Constraints: $X_1 > X_2 \land X_1 + X_2 = X_3 \land X_1 ≠ X_2 ≠ X_3 ≠ X_1$
• Solution: $X_1 = 2$, $X_2 = 1$, $X_3 = 3$ $\quad alldifferent([X_1, X_2, X_3])$

However the domains are tiny, $D(X_1) = \{1,2\}$, etc. just 2 values. I am wondering how they handle the situation where a variable is say a start time and can take any possible time value (assuming millisecond resolution integer representation of temporal values). So the domain could be $D(X_t) = \{1,\dotsc,10^{10}\}$ or something large. The backtracking algorithm does essentially $\forall d \in D(X_t), \dots$, where you enumerate over every value in the domain. I don't see how this is possible in practice if you are working with time (for example), or any large integer values or more generic data values.

Wondering if one could shed some light on how to deal with Constraint Satisfaction Problems where you have a large or infinite domain, because enumerating all the values seems impractical.

Answer 1

I'm not very familiar with infinite domains, so I'll answer the part concerning large domains.

Domains are not always represented as explicit lists of individual values, they can also be represented as ranges of values, which is more compact.

Furthermore, filtering algorithms (the algorithms which find inconsistent values in domains associated with a constraint and remove those values from these domains) can be applied with various levels of strictness. Domain consistency is very strict and will filter all values which are inconsistent. Bounds consistency is less strict and will only ensure that the lowest and highest values of a domain are consistent. This means that, for example, a very large domain represented as a range of values, when filtered with bounds consistency algorithms, will not repeatedly fragment its range of values into multiple smaller ranges, and does not necessarily render a problem intractable.