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. In PaLM, the command becauseOf(theDom(v)), if v is the emptied variable will give such an explanation. It will use the properties recalled on equation 3 on the introduction page.

• Why cannot variable x take the value a ?
  Just checking the associated removal explanation will help answering the question. In PaLM, the command becauseOf(theHole(v, a)) will provide the required explanation (it just sends back ¹ )

• 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].

Applications

• The PTIDEJ system [Guéhéneuc and Jussien, 2001] is an automated system for identifying distorted micro-architectures in object-oriented source code (the idea is to find quasi solutions to an over-constrained problem by identifying set of constraints that cannot be simultaneously verified).
  

  PTIDEJ dedicated page (contributed by Yann-Gaël Guéhéneuc)

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.

When one uses an explanation-based system, incremental constraint retraction of a given constraint c can be achieved this way:

1. Disconnecting The first step is to cut c from the constraint network. c needs to be completely disconnected (no further propagation, ...).
2. Setting back values The second step, is to undo the past effects (direct and indirect ones) of the constraint. This can be done considering all the explanations containing the removed constraint: all the associated events (value removal) are no more valid and those values need to be put back in their respective domain.
3. Controlling what has been done Of course, there can exist several different explanations for a given removal. Therefore, some values that has been put back actually need to get removed if another explanation can be found.
4. Repropagation In order to get to a consistent state, those new removals need to be propagating.

As we saw, we can use a same tool (explanations) to both compute an explanation for contradiction (see using explanations for debugging) and to incrementally remove a constraint in a given constraints system. Using explanation for solving over-constrained problems naturally comes to the mind: : 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. \cite{jussien-property}

Applications

• DECorum demo program: DynSPS is a demonstration program for the C++ library DECorum. It is a toy program used to solve dynamic Shop scheduling Problems. You can have a look at it on this website.
  

  DynSPS dedicated page

• Most of the applications cited in this page use dynamic handling of constraints. See debugging-related applications, new programming habits applications, ...
• [Jussien and Boizumault, 1997] presents that way of handling over-constrained problems in details. The PaLM system implements those mechanisms.

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.

• From backtrack-based to explanation-based constraint solving
  Algorithm 1 presents the solve method that looks for a solution in a given CSP. In this algorithm, a step of computation consists in adding an enumeration constraint ⁴ and propagate it through the constraint network.

  Our proposal consists in using the same overall process but replacing backtrack (that would occur on line 15 of algorithm 1 when a contradiction is identified) by a more specific handling.

  Algorithm 1. solving a CSP

  [solve(pb: Problem): boolean -> unassignedVars := pb.vars, try ( while not(empty(unassignedVars)) ( 5 let idx := nextVarToAssign(pb), // variable choice v := unassignedVars[idx], a := selectValToAssign(pb, v) // value choice in ( try ( 10 unassignedVars :delete v, post(pb, v == a), // instantiation propagate(pb) ) catch (LabelingContradiction) ( // An empty domain found 15 handleContradiction(pb) // classically: BACKTRACK ) ), true // A solution exists ) 20 catch (ProblemContradiction) ( false // No solution )]

• Generic contradiction handling
  Algorithm 2 introduces a general schema for handling contradictions. Once identified, a contradiction can be explained by the system (see line 2 in algorithm 2 and recall that a contradiction is identified when the domain of a variable - the failing variable - becomes empty). In order to overcome the contradiction, at least one constraint in it must be removed from the system (hence the selection in ligne 7 and the removal on line 12).

  In order to ensure that the same context will not get explored twice, we add the negation (using the opposite method) of the removed constraint (line 15) into the system (this behavior is the translation into explanation-based constraint programming of switching branch in a backtrack-based approach). Obviously, that new constraint must not be a permanent one: it remains only valid if each of the other constraints in the original explanation (e in algorithm 2) remains active. Such a constraint is called an indirect constraint ⁵ .

  Algorithm 2. handling contradictions

  [handleContradiction(pb: Problem): void -> let e: Explanation := becauseOf(theDom(getFailingVariable(pb))) in ( if (empty(e)) // The problem has no solution 5 raiseProblemContradiction() else ( let ct := selectConstraint(e) // select a to be removed choice in ( if known?(ct) ( // it exists 10 unassignedVars :add ct.v1, try ( remove(ct), // actual constraint removal e :delete ct, // the negation is added (indirect constraint) 15 post(pb, opposite(ct), e), propagate(pb)) // achieving consistency ) catch LabelingContradiction ( handleContradiction(pb) // recursive handling 20 ) ) else ( // no more enumeration constraint raiseProblemContradiction() ) 25 ) )) ]

  Note that while removing a constraint or propagating its negation a contradiction might occur. Hence, the recursive handling provided on line 19.

  Thus, an explanation-based constraint solver capable of incremental and efficient constraint retraction (see above) can easily replace a backtrack-based approach (one just need sto ensure the completeness of the search).

• A versatile framework
  Different algorithms are obtained according to the used algorithms for selecting a constraint or computing explanations. For example, one can get the following variations:
  • Standard backtracking: Considering that all the constraints of the system constitutes an explanation for any event (this is clearly the case although it is not a very precise information) and systematically choosing the most recent enumeration constraint in the contradiction explanation leads to a classical backtrack-based solver.

  • Intelligent backtracking: Using a more precise explanation schema (see this page), one can define an intelligent backtracker (i.e. that will backtrack higher in the search tree: to a really relevant choice point with no solution loss à la CBJ [Prosser, 1993]). One just has to remove not only the most recent constraint in the explanation but also all the other enumeration constraints added since that removed one.

  • Dynamic backtracking: When using the explanation system described here and removing only the most recent constraint in the contradiction explanation, we obtain an implementation of dynamic backtracking [Ginsberg, 1993] that handles constraint propagation in each step of the resolution: this is the MAC-DBT algorithm [Jussien et al., 2000].

  Each of the preceding algorithms performs a complete search. As far as the last one is concerned, [Bliek, 1998] even introduces conditions to verify in order to overcome the most recent limitation in the choice of the constraint to relax. Note that if all choices are left for that selection, the obtained search may not remain complete but can give a very efficient local search: this is the path-repair/decision-repair algorithm class [Jussien and Lhomme, 2002].

Applications

• Solving open-shop problems [Guéret et al., 2000] presents an intelligent backtracker for solving classical open-shop scheduling problems.
• MAC-DBT [Jussien et al., 2000] is a complete search algorithm for CSP that maintains arc-consistency at each step of Dynamic Backtracking [Ginsberg, 1993]. Explanations were necessary here to develop that algorithm.
  

  MAC-DBT dedicated page

• Path-repair [Jussien and Lhomme, 2002] is a heuristic search algorithm for CSP that can be seen as MAC-DBT with much more choices left to the user for selecting repairs to be done.
  

  path-repair/decision-repair dedicated page

• PaLM search The PaLM system provides many tools to develop new search algorithms actively using explanations.
  

  PaLM search dedicated page