An Example

To see the outlined propagate and branch method at a concrete example, consider the problem specified by the following constraints:
X $ \neq$ 7   Z $ \neq$ 2   X - Z = 3 . Y mathend000#
$ X \in \ensuremath{\{1,\dots,8\}} \hspace{4mm} Y \in \ensuremath{\{1,\dots,10\}} \hspace{4mm} Z \in \ensuremath{\{1,\dots,10\}} $ mathend000#
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 $ \neq$ 7, Z $ \neq$ 2 mathend000#, and X - Z = 3 . Y mathend000# . We assume that the propagator for X - Z = 3 . Y mathend000# realizes interval propagation, and that the propagators for the disequations X $ \neq$ 7 mathend000# and Z $ \neq$ 2 mathend000# realize domain propagation.

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

$ X \in [\ensuremath{\{1,\dots,6\}} ; 8] \hspace{4mm} Y \in \ensuremath{\{1,\dots,10\}}
\hspace{4mm} Z \in [1 ; \ensuremath{\{3,\dots,10\}}]$ mathend000#
where $ [1 ; \ensuremath{\{3,\dots,10\}}]$ mathend000# denotes the finite domain {1} $ \cup$ {3,..., 10} mathend000#. The interval propagator for X - Z = 3 . Y mathend000# can now further narrow the domains to
$ X\in[\ensuremath{\{4,\dots,6\}} ; 8] \hspace{4mm} Y \in \ensuremath{\{1,2\}}
\hspace{4mm} Z\in[1 ; \ensuremath{\{3,\dots,5\}}].$ mathend000#
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.

Figure 3: A search tree containing 3 choice nodes, 1 failure node, and 3 solution nodes.

\includegraphics[scale=0.7, clip]{figs/search-tree-exmpl.eps}

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 mathend000#
The space obtained by adding a propagator for X $ \neq$ 4 mathend000# reaches a fixpoint immediately after this propagator has written its information into the constraint store, which then looks as follows:
$ X \in [\ensuremath{\{5,\dots,6\}} ; 8] \hspace{4mm} Y \in \ensuremath{\{1,2\}}
\hspace{4mm} Z \in [1 \; \ensuremath{\{3,\dots,5\}}]$ mathend000#
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 mathend000# is inconsistent with the store obtained by adding X = 5.

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

$ X \in [6 \; 8] \hspace{4mm} Y \in \ensuremath{\{1,2\}}
\hspace{4mm} Z \in [1 \; \ensuremath{\{3,\dots,5\}}]$ mathend000#
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 mathend000#
Finally, the space obtained by adding a propagator for X $ \neq$ 6 mathend000# can also be solved by propagation, yielding the third and final solution
X = 8   Y = 1   Z = 5 mathend000#
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 $ \neq$ 7, Z $ \neq$ 2 mathend000# , and X - Z = 3 . Y mathend000# for each triple. There are 8 * 10 * 10 = 800 candidates. This shows that constraint propagation can reduce the size of the search tree considerably.

Guido Tack 2007-04-26