<< Prev | - Up - | Next >> |

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.

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:

<< Prev | - Up - | Next >> |

Denys Duchier, Claire Gardent and Joachim Niehren

Version 1.2.4 (20020829)