General Guidelines to the Use of Domains

The send more money example already shows the general principle of solving problems using finite domain constraints:

• First the variables are defined and their domains are specified.

• Then the constraints are imposed on these variables. In the above example the constraints are simply built-in predicates. For more complicated problems it is often necessary to define Prolog predicates that process the variables and impose constraints on them.

• If stating the constraints alone did not solve the problem, one tries to assign values to the variables. Since every instantiation immediately wakes all constraints associated with the variable, and changes are propagated to the other variables, the search space is usually quickly reduced and either an early failure occurs or the domains of other variables are reduced or directly instantiated. This labeling procedure is therefore incomparably more efficient than the simple generate and test algorithm.

The complexity of the program and the efficiency of the solving depends very much on the way these three points are performed. Quite frequently it is possible to state the same problem using different sets of variables with different domains. A guideline is that the search space should be as small as possible, and thus e.g. five variables with domain 1..10 (i.e. search space size is

10^5 ) are likely to be better than twenty variables with domain 0..1 (space size

2^20 ).

The choice of constraints is also very important. Sometimes a redundant constraint, i.e. one that follows from the other constraints, can speed up the search considerably. This is because the system does not propagate all information it has to all concerned variables, because most of the time this would not bring anything, and thus it would slow down the search. Another reason is that the library performs no meta-level reasoning on constraints themselves (unlike the CHR library). For example, the constraints

X + Y #= 10, X + Y + Z #= 14

allow only the value 4 for Z, however the system is not able to deduce this and thus it has to be provided as a redundant constraint.

The constraints should be stated in such a way that allows the system to propagate all important domain updates to the appropriate variables.

Another rule of thumb is that creation of choice points should be delayed as long as possible. Disjunctive constraints, if there are any, should be postponed as much as possible. Labeling, i.e. value choosing, should be done after all deterministic operations are carried out.

The choice of the labeling procedure is perhaps the most sensitive one. It is quite common that only a very minor change in the order of instantiated variables can speed up or slow down the search by several orders of magnitude. There are very few common rules available. If the search space is large, it usually pays off to spend more time in selecting the next variable to instantiate. The provided predicates deleteff/3 and deleteffc/3 can be used to select the most constrained variable, but in many problems it is possible to extract even more information about which variable to instantiate next.

Often it is necessary to try out several approaches and see how they work, if they do. The profiler and the statistics package can be of a great help here, it can point to predicates which are executed too often, or choice points unnecessarily backtracked over.