When you post a constraint, the constraint is used immediately to reduce the domains of the constrained variables that it involves. Solver reduces a domain by removing those values that cannot satisfy the constraint and thus cannot participate in a solution.

Posting a constraint is reversible: the constraint is removed when Solver backtracks to choice points set before that constraint was posted.

If constraint propagation causes a domain to be reduced to a single value, then the constrained variable will be bound to that remaining value.

In addition, when you post a constraint, the constraint is saved so that whenever any of the variables to which it applies is modified, the constraint will be activated, and the modification will be transmitted to the other variables that the constraint involves. This activity is called constraint propagation.

The algorithm used for constraint propagation in Solver is straightforward in principle. Solver maintains a queue of variables, called the constraint propagation queue. When a constrained variable is modified, that variable is put at the end of that queue if it is not already in the queue. As long as there are variables in that queue, the algorithm takes the first variable from the queue. We then say this particular variable is in process.

When a variable is processed, it is first removed from the propagation queue. Then each constraint posted on that variable is examined. For one such constraint, all the variables on which it is posted are in turn examined: their domains are reduced by removing those values that are inconsistent with it. If a variable is already in process, then this domain reduction will be deferred until it is no longer in process. If some of these variables are modified during this activity, they, too, are put into the queue if they are not yet in the queue. The algorithm continues as long as there is a variable in the queue to process. The algorithm automatically reduces domains as necessary and halts in either of two situations: when all domains contain only values consistent with the constraints, or when a domain becomes empty. For performance considerations, it does not carry out all the reductions theoretically possible.

This algorithm has several important properties:

• This algorithm always halts.
• It lets you use constraints (such as arithmetic constraints, for example) on more than two variables at a time.
• It lets you handle problems dynamically; that is, you can solve problems where new constraints can be added during the search for a solution.
• Regardless of the order in which the constraints are considered, the domains will always be the same at the end of the execution of the propagation.

See the concepts Choice Point, Domain-Delta, Goal, Propagation Events, Reversibility, and State for more information.

See Also

IlcConstraint