Classical constraint programming systems (such as Solver from Ilog, Chip from Cosytec, gnuProlog from INRIA, ...) are helpless when the constraints system to solve has no solution. Indeed, only a no solution message is provided. The user is left alone to find out why: is it because of the problem itself (no solution exists), a bad modelling, a bug in the solver, ...

In order to help spreading constraint programming, the constraints community needs to address that issue. For example, the user can be helped by pointing out a set of constraints that left alone lead to the unexpected situation. A promising technique for providing such an information seems to be using explanations [Jussien and Barichard, 2000]. An explanation is a set of constraints justifying an action of the solver (value removal, bound update, contradiction, ...).

We consider here CSP represented by a couple (V,C). V is a set of variables and C a set of constraints on those variables. Note that domains are considered as unary constraints. Moreover, the enumeration mechanism is handled as a series of constraints additions and retractions. Those constraints are specific and are called decision constraints. Indeed, we chose not to limit our tools to value assignments but to allow any kind of decision constraint (eg. ordering constraints between tasks in scheduling, splitting constraints in numeric CSP, ...)

A contradiction explanation (a.k.a. nogood [Schiex and Verfaillie, 1994]) is a subset of the current constraints system of the problem that, left alone, leads to a contradiction (no feasible solution contains a nogood). A contradiction explanation divides into two parts: a subset of the original set of constraints (C' subset of C) in the following equation) and a subset of decision constraints introduced so far in the search (here dc₁, ..., dc_k).

Equation 1 : contradiction explanation

An operational viewpoint of contradiction explanations can be made explicit rewriting equation 1 the following way:

Equation 2 : an operational explanation

Let consider dc_j: v = a in the previous formula. The left hand side of the implication is called an eliminating explanation (explanation for short) because it justifies the removal of value a from the domain d(v) of variable v. It will be noted: .

Filtering operations in CSP can be considered as a sequence of value removals which can all be explained as in equation 2. The simplest of all explanations is to merely consider the complete set of currently active constraints (i.e. the initial constraints of the problem and the set of all the decisions -- and their associated enumeration constraint -- made so far). Note that much more useful explanations can be provided (see the section of this web site devoted to implementation issues).

Explanations can be combined with other ones to provide new ones. Indeed, let suppose that is the set of all possible choices for a given decision (set of possible values, set of possible sequences, ...). If there exists a set of explanations , a new explanation can be derived: . Moreover, from the empty domain of a variable v, one can compute a contradiction explanation:

Equation 3 : A contradiction explanation

Note that when a contradiction explanation does not contain any decision constraint, the associated problem is proved to be over-constrained.

There exist generally several eliminating explanations for the removal of a given value. Recording all of them leads to an exponential space complexity. Another technique relies on forgetting (erasing) explanations that are no longer relevant ¹ to the current variable assignment. By doing so, interesting complexity results are obtained.

The computation of eliminating explanation is addressed in another section of this web site. Consider for the following that you have access to a constraint solver that provides eliminating explanations (such as PaLM).

3.1. Understanding the current situation

Explanations can be directly used to help the user (the application developer, the solver developer, ...) understanding the current situation within the constraint solver:

• Why does my problem have no solution ?
  Identifying lack of solutions is usually done by finding a variable that cannot be assigned any value that will respect all the constraints of the system: its domain has been emptied. Checking the explanation of this situation will help understanding the situation by narrowing the problem to relevant constraints. Equation 3 gives us an explanation.

• Why cannot variable x take the value a ?
  Just checking the associated removal explanation will help answering the question.

• What if constraint c gets back into the system ?
  In such a situation, keeping track of explanations that contained constraint c before its retraction will allow a glimpse (a necessary partial but still valid one) on the effects of the activation of c since events related to those explanations would become valid. Note that keeping such invalid explanation can be done using what is called k-relevance in [Bayardo and Miranker, 1996].

3.2. Dynamic constraint retraction

Explanations can be very useful when dealing with dynamic problems. Incremental constraint addition to a problem is a well known issue but incremental constraint retraction is not so easy. [Bessière, 1991] already used a simplified explanation system (using justifications ² ) to perform such a retraction.

The retraction process when using an explanation-based system can be achieved in the following way:

1. disconnecting the constraint from the propagation network
2. setting back values whose retraction was due (directly or not) by the removed constraint - one just needs to take into account the events associated to explanations that do contain the removed constraint
3. controlling that was has been done is consistent with the remaining constraint network by testing each value restoration against the remaining constraint
4. propagating the possibly the value removals

3.3. Solving over-constrained problems

As we saw, we can use a same tool to both compute an explanation for contradiction and to incrementally remove a constraint in a given constraints system: namely the eliminating explanations.

One naturally thinks about using those explanations for solving over-constrained problems [Jussien and Boizumault, 1997]: consider solving the constraints system as usual and, if necessary (i.e. once the problem proved as being over-constrained), use explanations to identify the constraint(s) to be removed (using a comparator that will take into account the user's preferences) and incrementally remove it (or them). That process being iterated as necessary to obtain a suitable solution for the resulting constraint system. The use of the comparator guarantees the optimality of the solution [Jussien and Boizumault, 1997].

The originality of such an approach is two-fold:

• All the constraints of the problem can be propagated from the beginning of the search and comparison criteria can be delayed to the last moment [Jussien and Boizumault, 1997]. Indeed, choice criteria (reflecting the user opinion about relaxing constraints) are used only for selecting a set of constraints among the ones appearing in the current contradiction explanation. Thus, classifying constraints is only needed when encountering a contradiction and only between relevant constraints.
• The search is done into the space of possible relaxations opposed to the space of possible affectations in more classical approaches ([Borning et al, 1989] or [Schiex and Verfaillie, 1995]).

Using explanations within a constraint programming language leads to new programming gimmicks, new approaches, ... Most of CSP solving algorithms are derived from a backtrack-based complete search. The drawbacks of such an approach have been known for long now: thrashing and inappropriate behavior. Previous solutions to solve those problem were not really convincing (time or space overhead, no real advantages). Nevertheless, more recently, the MAC-DBT algorithm [Jussien et al., 2000] showed that backtrack-based algorithms were not the panacea in real-world situation compared to explanation-based algorithms.

Using explanations within constraint programming changes everything in constraint solving. Indeed, using explanations allows the replacement of chronological backtracking by a real repair of the current situation (instead of a mere restart from scratch from the last choice point). Explanation-based search can benefit from both repair-based algorithms such as Dynamic Backtracking [Ginsberg, 1993] and constraint propagation leading to a new way of computing: explanation-based constraint programming.

The applications section of this web site contains details on how to make active use of explanations for developing new search algorithms (see for example MAC-DBT or path-repair).