2.1.4 The Method: Propagate and Distribute

By now, you should be convinced that it is simply not practical to generate the full search tree in usual combinatorial problems. Even interleaving generate and test will not scale: in the case of 15 variables it results in a search tree with 917477 nodes; now suppose we had 100 variables. Clearly this just won't do. So what can we do instead?

The idea is to take the interleaving idea even further: we don't want the tests to simply be passive and check whether they are satisfied or violated; rather we want them to be active and propagate constraints. In our example both V1 and V2 take values in {1,...,15}. Furthermore we have the constraint that:

V1 < V2

This means that the value of V2 must be at least 1 greater than that of V1. Therefore V1 must actually take values in {1,...,14} and V2 in {2,...,15}. We can repeat this reasoning with V2 and V3, etc, until V14 and V15, at which point we obtain the conclusion that V15 must take values in {15}. In other words the only possible value for V15 is 15. By iterating this process we deterministically arrive at the conclusion that V1=1, ... , V15=15. Thus the search tree now contains a single node:

In general, however, we may still have to perform search, but the idea is to first derive as much as possible through deterministic inference using the available constraints and only then make a non-deterministic choice if still necessary. This is the general method of constraint programming which can be paraphrased as `propagate and distribute'. A propagation step restricts the set of possible solutions using simple, deterministic inference. A distribution step performs a non-deterministic case distinction and should only be considered when no further inferences are possible through propagation alone. In this fashion, the search tree requires much fewer choice points: propagation is said to `prune' the search tree.

Constraints as concurrent agents

In concurrent constraint programming, each constraint is implemented by a concurrent agent, also called a `propagator', which observes what is currently known and attempts to derive and contribute new conclusions. This common pool of information is called the `constraint store' and only contains simple statements of the form X must take values in {1,2,7}. Whenever a propagator can make an inference, it updates the constraint store: the effect of an inference is to remove possible values for one or more variables. This update may in turn cause another propagator to be able to make an inference and so on. One can imagine a constraint store with its propagators as follows: