• A dedicated class to represent explanation (eg. in PaLM we find the Explanation class).
• A storage slot within variables in order to keep the explanations associated to value removals (see the introduction page for definitions).
• Some new domain modifications methods that accept a supplementary parameter: an explanation. Those methodes will be used to link computed explanations to their related event
• Tools for accessing recorded explanations
• Many other tools for dealing with explanations ...

Many constraint solvers use an event-based model (eg. choco [Laburthe, 2000]): during propagation, constraints are awaken (like agents or daemons) each time a variable domain is reduced (this is an event ² ) possibly generating new events (value removals). Such an architecture is well suited for solver that maintains a local consistency (arc-consistency and others) but is not so well suited for consistencies that are defined upon several constraints at the same time.

In such a model, a constraint is fully characterized by its behavior regarding the basic events:

• value removal from the domain of a variable (method awakeOnRem),
• domain bound updates (methods awakeOnInf and awakeOnSup - see example 1)
• and a variable instantiation (method awakeOnInst).

[awakeOnSup(c:GreaterOrEqualxyc, idx:integer) : void
 -> if (idx = 1) updateSup(c.v2, c.v1.sup - c.cste)]

Explanations for events need to be computed when the events are generated i.e. within the propagation code of the constraints (namely the awakeOn(Inf,Sup,Rem,Inst) methods of choco). In order to make it as simple as possible, one only need to add an extra information to the updateInf or updateSup calls: the actual explanation. Example 2 shows how such an explanation can be computed and what is the resulting code for a basic constraint. Example 3 gives another point of view on explanations for classical binary CSP.

[awakeOnSup(c:PalmGreaterOrEqualxyc, idx:integer) : void
  -> if (idx = 1) updateSup(c.v2, c.v1.sup - c.cste, becauseOf(c, theSup(c.v1)))]

Example 3. Explanations for classical binary CSP

Explanations for classical binary CSP where constraints are expressed by a list of allowed tuples of values for their variables can be easily stated. When applying constraint Cxy between variables x and y and willing to remove value a from the domain of x, this situation is due to the removal of all supporting value for a in the domain of y regarding constraint Cxy which can be expressed this way: That equation translates into: let expl := becauseOf(Cxy) in ( for b in supports(Cxy, x, a) expl := expl U becauseOf(theHole(y, b)), removeVal(x, a, expl))

Such a modified constraint solver is ready to provide explanations when needed. Unfortunately, other additions are needed in order to get an e-constraints system.

One of the many interesting uses of explanations is performing dynamic constraint retraction (see the applications page of this website).

The past effects deletion process of such a dynamic handling arises the necessity of a new kind of event: value restoration (or bound restoration) in a domain of a variable. In order to achieve the third step (control) of the constraint retraction process, one can call the related constraint in order to check the validity of the value restoration. This can be done using new ³   constraint related methods:

• awakeOnRestoreInf (resp. awakeOnRestoreSup) calls a constraint on the restoration of the lower (upper bound) of one of its intervening variables.
• awakeOnRestoreVal calls a constraint on the restoration of one value in the domain of one of its intervening variable.

The intented semantics of such a method is to check that this restoration is compatible with the current domains of the other variable regarding the constraint (see example 4). Note that, therefore, the domain restoration need to be all done before awaking constraints that way. This is an important point: e-constraints programming needs to clearly separate domain modifications and constraint propagation and also as it is shown on the global constraint section data structure maintenance and constraint propagation.

[awakeOnRestoreInf(c: PalmGreaterOrEqualxyc, idx: integer) : void
 -> if (idx = 1) awakeOnInf(c, 2)]

[awakeOnRestoreSup(c: PalmGreaterOrEqualxyc, idx: integer) : void
 -> if (idx = 2) awakeOnSup(c, 1)]

Providing explanations for basic constraints is quite easy: the existing code explicitly states what are the real triggering conditions (as shown in example 2). Unfortunately, when dealing with global constraints, it is not so easy.

Indeed,triggering occurs when an accumulation of information modifies a data structure enough to reject parts of a domain of a variable.

Unfortunately, when triggering the propagation rule, all those pieces of information have not been kept. Therefore computing a precise explanation may not be that easy. There is always a generic explanation: the current state of the domains of the variables of the constraints. Such an explanation is useless if used with all the constraints of the system: everything will depend on everything else!

When adding explanations to global constraints, it is thus highly recommended to get back to the overall algorithm in order to make it explanation-friendly. And do not forget that precise explanation system will act as a good documentation for the global constraint!

Another point about global constraint is that they absolutely need to get data structures synchronized at every moment with the current state of the domain. As shown in the applications page, we cannot rely upon backtracking for modifying data structures when undoing some previous choice. Moreover, a clear separation is needed between data structure maintenance and propagation in order to make sure that everything stays synchronized.

One of the major interests of what is presented here is that both space and time complexities remain polynomial. Indeed, as the explanation network sort of traces the behavior of the solver; a single value will be removed only once, leading to a single explanation. Thus, the space complexity for CSP defined upon n discrete variables of maximum domain size d upon wich are posted e constraints is in O((e + n) x n x d). There are at most n x d explanations (one for each value) of maximum size e (all the constraints of the problem) + n (one assignment constraint for each variable).

Experimental results presented in [Jussien et al., 2000] (see also the MAC-DBT page) show that computing explanations while filtering leads to a time overhead (due to actual computing and storing of explanations) but this overhead remains quite constant whatever the nature of the problem (highly constrained problems vs. under-constrained problems). Moreover, that overhead is rewarded when actively using those explanations for, for example, guiding the search (see the applications page).

The choice made so fat was to forbid modification of the classical mechanisms of constraint programming (filtering, enumeration, ...). As we saw, the explanation computation mechanism sort of provides a trace of the solver. The computed explanations are therefore non minimal nor exhaustive and are highly dependant on the solver mechanisms and implementation. It is a pragmatic point of view on computing explanations.

Alternatives exist: finding mechanisms or enumeration ordering that are efficient for producing both solutions and explanations, computing explanations in a lazy way (keeping less information - as in [Bessière, 1991]), even completely investing in explanations and radically modify solving mechanisms, ...

Another promising approach is to develop non intrusive techniques (no need to modify the existing propagation code). Some work is under way at École des Mines de Nantes, France about using Aspect Oriented Programming (AOP [Kiczales et al., 1997] - see also Mario Sudholt's AOP page) for monitoring a constraint solver from the outside and still providing precise explanations for its behavior.