## An Example

To see the outlined propagate and branch method at a concrete example, consider the problem specified by the following constraints:
X 7   Z 2   X - Z = 3 . Y
To solve the problem, we start with a space whose store constrains the variables X, Y, and Z to the given domains. We also create three propagators imposing the constraints X 7, Z 2, and X - Z = 3 . Y . We assume that the propagator for X - Z = 3 . Y realizes interval propagation, and that the propagators for the disequations X 7 and Z 2 realize domain propagation.

The propagators for the disequations immediately write all their information into the store and disappear. The store then knows the domains

where denotes the finite domain {1} {3,..., 10}. The interval propagator for X - Z = 3 . Y can now further narrow the domains to
Now propagation has reached a fixpoint. Thus, we continue with a first branching step. We choose to branch with the constraint X = 4. Figure 3 shows the resulting search tree.

The space obtained by adding a propagator for X = 4 can be solved by propagation and yields the solution

X = 4   Y = 1   Z = 1
The space obtained by adding a propagator for X 4 reaches a fixpoint immediately after this propagator has written its information into the constraint store, which then looks as follows:
This time we branch with respect to the constraint X = 5.

The space obtained by adding a propagator for X = 5 fails since X - Z = 3 . Y is inconsistent with the store obtained by adding X = 5.

The space obtained by adding a propagator for X 5 reaches a fixpoint immediately after this propagator has written its information into the constraint store, which then looks as follows:

Now we branch with respect to the constraint X = 6.

The space obtained by adding a propagator for X = 6 can be solved by propagation and yields the solution

X = 6   Y = 1   Z = 3
Finally, the space obtained by adding a propagator for X 6 can also be solved by propagation, yielding the third and final solution
X = 8   Y = 1   Z = 5
An alternative to the propagate and branch method is a naive enumerate and test method, which would enumerate all triples (X, Y, Z) admitted by the initial domain constraints and test the constraints X 7, Z 2 , and X - Z = 3 . Y for each triple. There are 8 * 10 * 10 = 800 candidates. This shows that constraint propagation can reduce the size of the search tree considerably.

Andreas Rossberg 2006-08-28