@InProceedings{debruyne-correctness,
author         = {Romuald Debruyne and G{\'e}rard Ferrand and Narendra Jussien and Willy Lesaint and Samir Ouis and Alexandre Tessier},
title          = {Correctness of Constraint Retraction Algorithms},
booktitle      = {FLAIRS'03: Sixteenth international Florida Artificial Intelligence Research Society conference},
pages          = {???-???},
year           = 2003,
address        = {St. Augustine, Florida, USA},
month          = {may},
publisher      = {AAAI press},
url            = {http://www.emn.fr/jussien/publications/debruyne-FLAIRS03.pdf},
type           = {1. Theoretical foundations for explanations},
abstract       = {In this paper, we present a general scheme for incremental
constraint retraction algorithms that encompasses all existing
algorithms. Moreover, we introduce some necessary conditions to
ensure the correctness of any new incremental constraint
retraction algorithms. This rather theoretical work is based on
the notion of explanation for constraint programming and is
exemplified within the PALM system: a constraint solver
allowing dynamic constraint retractions.}
}

@InProceedings{ouis-k-relevance,
author         = {Samir Ouis and Narendra Jussien and Patrice Boizumault},
title          = {$k$-relevant explanations for constraint programming},
booktitle      = {FLAIRS'03: Sixteenth international Florida Artificial Intelligence Research Society conference},
pages          = {???-???},
year           = 2003,
address        = {St. Augustine, Florida, USA},
month          = {may},
publisher      = {AAAI press},
url            = {http://www.emn.fr/jussien/publications/ouis-FLAIRS03.pdf},
type           = {3. Using explanations for debugging},
abstract       = {This paper presents diagnosis tools and interaction-based tools which could help
the Constraint Programming user to interactively develop its applications.
The implementation of these tools rely on explanations, and more precisely on
k-relevant explanations.
An example is given to illustrate k-relevant explanations and to provide concrete
situations illustrating the functionalities of our interactive and diagnosis tools.}
}

@InProceedings{douence-non-intrusive-ciclops,
author         = {R{\'e}mi Douence and Narendra Jussien},
title          = {Non-intrusive constraint solver enhancements},
booktitle      = {Colloquium on Implementation of Constraint and {LO}gic Programming Systems (CICLOPS'02)},
year           = 2002,
pages          = {26--36},
venue          = {Copenhagen, Denmark},
series         = {CW Reports},
volume         = 344,
institution    = {Departement of Computer Science, K.U.Leuven},
adress         = {Leuven, Belgium},
accessible     = {http://www.cs.kuleuven.ac.be/publicaties/rapporten/cw/CW344.abs.html},
month          = {31} # jul,
type           = {2. Implementation of explanation-based systems},
url            = {http://www.emn.fr/jussien/publications/douence-WICLP02.pdf},
abstract       = {Using conflict sets (or nogoods) and explanations within
constraint programming has been proved very effective. However,
most constraint solvers do not provide this feature. This
statement could have been made for many other improvements.
Indeed, one of the main reasons of that fact is that many
improvements in constraint programming are intrusive:
their integration requires a general modification of the solvers'
implementation and/or architecture. The core part of constraint
solvers is often quite simple, however, it represents only a small
part of the implementation. The main part of the code is devoted
to specific constraint handling, global constraints, search
techniques, API, etc. Modifying this code requires a real
development effort that may become overly costly. Constraint
solvers need non intrusive approaches. Actually, solvers should
not be modified at all and only a general information about
implementation should be needed to integrate improvements. In this
paper, we present a technique used in software engineering to
reach that aim: aspect oriented programming. As an example, the
non intrusive integration of conflict set generation and use is
presented and some insights of what could be done are provided.}
}

@InProceedings{elkhyari-conflict-dynamic-scheduling,
author         = {Abdallah Elkhyari and Christelle Gu{\'e}ret and Narendra Jussien},
title          = {Conflict-based repair techniques for solving dynamic scheduling problems},
series         = {Lecture Notes in Computer Science},
booktitle      = {Principles and Practice of Constraint Programming (CP 2002)},
publisher      = {Springer-Verlag},
number         = 2470, 
  year         = 2002,
  pages        = {702--707},
  month        = sep,
  address      = {Ithaca, NY, USA},
url            = {http://www.emn.fr/jussien/publications/elkhyari-CP02.pdf},
type           = {4. Using explanations for solving dynamic problems},
  note         = {Short paper.}
}

@Article{jussien-local-aijournal,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {Local search with constraint propagation and conflict-based heuristics},
journal        = {Artificial Intelligence},
year           = 2002,
month          = jul,
volume         = 139,
number         = 1,
pages          = {21--45},
type           = {5. Using explanations for designing new algorithms},
url            = {http://www.emn.fr/jussien/publications/jussien-AIJ02.pdf},
abstract       = {  Search algorithms for solving CSP (Constraint Satisfaction
  Problems) usually fall into one of two main families: local search
  algorithms and systematic algorithms. Both families have their
  advantages. Designing hybrid approaches seems promising since those
  advantages may be combined into a single approach.  In this paper,
  we present a new hybrid technique.  It performs a local search over
  partial assignments instead of complete assignments, and uses
  filtering techniques and conflict-based techniques to efficiently
  guide the search.  This new technique benefits from both classical
  approaches: a priori pruning of the search space from
  filtering-based search and possible repair of early mistakes
  from local search.  We focus on a specific version of this
  technique: tabu decision-repair. Experiments done on
  open-shop scheduling problems show that our approach competes well
  with the best highly specialized algorithms.}
}

@InProceedings{ouis-coins,
author         = {Samir Ouis and Narendra Jussien and Patrice Boizumault},
title          = {COINS: a constraint-based interactive solving system},
booktitle      = {ICLP'02 12th Workshop on Logic Programming Environments (WLPE'02)},
year           = 2002,
pages          = {31 -- 46}, 
address        = {Copenhaguen, Denmark},
month          = {31 } # jul,
type           = {2. Implementation of explanation-based systems},
url            = {http://www.emn.fr/jussien/publications/ouis-WICLP02.pdf},
abstract       = {This paper describes the COINS (COnstraint-based INteractive
Solving) system: a conflict-based constraint solver. It helps
understanding inconsistencies, simulates constraint additions
and/or retractions (without any propagation), determines if a given
constraint belongs to a conflict and provides diagnosis tools (e.g.
why variable v cannot take value val). COINS also uses
user-friendly representation of conflicts and explanations.}
}

@InProceedings{ bliek-gpb,
author         = {Christian Bliek},
title          = {Generalizing Partial Order and Dynamic Backtracking},
booktitle      = {Fifth National Conference on Artificial Intelligence -- AAAI'98},
year           = 1998,
type           = {1. Theoretical foundations for explanations}
}

@InProceedings{ beringer-combinatorial,
author         = {Henri Béringer and Bruno {de Backer}},
title          = {Combinatorial problem solving in constraint logic programming with cooperative solvers},
booktitle      = {Logic Programming: Formal Methods and Practical Applications},
editor         = {North Holland},
volume         = 11,
series         = {Studies in Computer Science and Artificial Intelligence},
year           = 1995,
type           = {6. Related works}
}

@InProceedings{ beringer-piecewise,
author         = {Henri Béringer and Bruno {de Backer}},
title          = {Piecewise linear constraints under assumptions a new approach to model based diagnosis},
booktitle      = {ITESM~: Third international symposium on artificial intelligence},
year           = 1990,
address        = {Monterrey, Mexico},
type           = {6. Related works}
}

@InProceedings{ debacker91,
author         = {Bruno {de Backer} and Henri Béringer},
title          = {Intelligent Backtracking for {CLP} Languages: An Application
to {CLP(${\cal R}$)}},
booktitle      = {{ILPS'91}: Proceedings International Logic Programming Symposium},
address        = {San Diego, CA},
publisher      = {MIT Press},
editor         = {Vijay Saraswat and Kazunori Ueda},
month          = oct,
year           = 1991,
pages          = {405--419},
type           = {5. Using explanations for designing new algorithms}
}

@InProceedings{ bessiere-dynamic,
author         = {Christian Bessière},
title          = {Arc consistency in dynamic constraint satisfaction problems},
booktitle      = {National Conference on Artificial Intelligence -- AAAI'91},
year           =  1991,
type           = {4. Using explanations for solving dynamic problems}
}

@InProceedings{ bessiere-mac,
author         = {Christian Bessière and Jean-Charles Régin},
title          = {{MAC} and Combined Heuristics: Two Reasons to Forsake {FC} (and {CBJ?}) on Hard Problem},
booktitle      = {Principles and Practice of Constraint Programming (CP'96)},
year           = 1996,
address        = {Cambridge, MA},
type           = {6. Related works}
}

@InProceedings{ bessiere-nonbinary,
author         = {Christian Bessière},
title          = {Arc consistency for non-binary dynamic {CSP}s},
booktitle      = {Proceedings ECAI'92},
year           = 1992,
type           = {4. Using explanations for solving dynamic problems}
}

@Article{ doyle-tms,
author         = {J. Doyle},
title          = {A truth maintenance system},
journal        = {Artificial Intelligence},
year           = 1979,
volume         = 12,
pages          = {231--272},
type           = {6. Related works}
}

@Book{ forbus-solvers,
author         = {{Kenneth D.} Forbus and Johan {de Kleer}},
title          = {Building Problem Solvers},
publisher      = {MIT Press, Cambridge},
year           = 1993,
type           = {6. Related works}
}

@Article{ ginsberg-dynamic,
author         = {{Matthew L.} Ginsberg},
title          = {Dynamic Backtracking},
journal        = {Journal of Artificial Intelligence Research},
year           = 1993,
volume         = 1,
pages          = {25--46},
type           = {1. Theoretical foundations for explanations}
}

@Article{ kleer-atms,
author         = {Johan {de Kleer}},
title          = {An Assumption-based TMS},
journal        = {Artificial Intelligence},
volume         = 28,
year           = 1986,
pages          = {127--162},
type           = {6. Related works}
}

@Article{ kleer-extending,
author         = {Johan {de Kleer}},
title          = {Extending the {ATMS}},
journal        = {Artificial Intelligence},
volume         = 28,
year           = 1986,
pages          = {163--196},
type           = {6. Related works}
}

@Article{ kleer-solving,
author         = {Johan de Kleer},
title          = {Problem solving with the {ATMS}},
journal        = {Artificial Intelligence},
volume         = 28,
year           = 1986,
pages          = {197--224},
type           = {6. Related works}
}

@InProceedings{menezes-defeasible-linear,
author         = {Christian Holzbaur and Francisco Menezes and Pedro Barahona},
title          = {Defeasibility in CLP(Q) throught Generalized Slack Variables},
editor         = {Eugene C. Freuder},
number         = 1118,
series         = {Lecture Notes in Computer Science},
pages          = {209--223},
booktitle      = {Principles  and Practice of Constraint Programming -- CP 96},
year           = 1996,
address        = {Cambridge, MA, USA},
month          = aug,
type           = {5. Using explanations for designing new algorithms}
}

@InProceedings{ menezes-defeasible-lncs,
author         = {Francisco Menezes and Pedro Barahona},
title          = {Defeasible constraint solving},
editor         = {Michael Jampel and Eugene Freuder and Michael Maher},
number         = 1106,
series         = {Lecture Notes in Computer Science},
pages          = {151--170},
booktitle      = {Over-Constrained Systems},
year           = 1996,
publisher      = {Springer Verlag},
type           = {6. Related works}
}

@TechReport{ prosser-maccbj,
author         = {Patrick Prosser},
title          = {{MAC-CBJ}: maintaining arc-consistency with conflict-directed backjumping},
institution    = {Department of Computer Science -- University of Strathclyde},
year           = 1995,
number         = {RR - 95/177},
type           = {5. Using explanations for designing new algorithms}
}

@article{       prosser-hybrid,
author         = {Patrick Prosser},
title          = {Hybrid Algorithms for the Constraint Satisfaction Problem},
journal        = {Computational Intelligence},
year           = 1993,
volume         = 9,
number         = 3,
pages          = {268--299},
month          = aug,
note           = {(Also available as Technical Report AISL-46-91, Stratchclyde, 1991)},
type           = {6. Related works},
}

@InProceedings{ sqalli-inference,
author         = {Mohammed H. Sqalli and Eugene C. Freuder},
title          = {Inference-Based Constraint Satisfaction Supports Explanation},
booktitle      = {AAAI/IAAI, Vol. 1},
pages          = {318-325},
year           = 1996,
type           = {2. Implementation of explanation-based systems},
}

@Article{ schiex-nogood,
author         = {Thomas Schiex and Gérard Verfaillie},
title          = {Nogood {R}ecording fot {Static} and {Dynamic} {Constraint} {Satisfaction} {Problems}},
journal        = {International Journal of Artificial Intelligence Tools},
year           = 1994,
volume         = 3,
number         = 2,
pages          = {187--207},
type           = {5. Using explanations for designing new algorithms}
}

@InProceedings{ verfaillie-reuse,
author         = {{Gérard} Verfaillie and Thomas Schiex},
title          = {Solution reuse in dynamic constraint satisfaction problems},
pages          = {307--312},
booktitle      = {AAAI'94},
address        = {Seattle, WA},
year           = 1994,
type           = {4. Using explanations for solving dynamic problems}
}

@InProceedings{ bayardo-lookback,
author         = {Roberto {Bayardo Jr.} and Robert Schrag},
title          = {Using {CSP} look-back techniques to solve exceptionnaly hard {SAT} instances},
booktitle      = {CP'96},
year           = 1996,
type           = {5. Using explanations for designing new algorithms}
}

@InProceedings{ bayardo-sat,
author         = {Roberto {Bayardo Jr.} and Robert Schrag},
title          = {Using CSP look-back techniques to solve real world SAT instances},
booktitle      = {14th National Conf. on Artificial Intelligence, AAAI97},
year           = 1997,
pages          = {203-208},
type           = {5. Using explanations for designing new algorithms}
}

@InProceedings{ bayardo-complexity,
author         = {Roberto {Bayardo Jr.} and Daniel Miranker},
title          = {A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem},
booktitle      = {AAAI'96},
year           = 1996,
type           = {1. Theoretical foundations for explanations}
}

@InProceedings{ baker-hazards,
author         = {{Andrew B.} Baker},
title          = {The Hazards of Fancy Backtracking},
booktitle      = {12th National Conf. on Artificial Intelligence, AAAI94},
address        = {Seattle, WA, USA},
year           = 1994,
pages          = {288-293},
type           = {6. Related works}
}

@InProceedings{ frost-deadend,
author         = {Frost and Dechter},
title          = {Dead-end driven learning},
booktitle      = {12th National Conf. on Artificial Intelligence, AAAI94},
address        = {Seattle, WA, USA},
year           = 1994,
type           = {6. Related works}
}

@InProceedings{ junker-quickxplain,
author         = {Ulrich Junker},
title          = {{QUICKXPLAIN}: Conflict Detection for Arbitrary Constraint Propagation Algorithms},
booktitle      = {IJCAI'01 Workshop on Modelling and Solving problems with constraints},
year           = 2001,
address        = {Seattle, WA, USA},
month          = aug,
type           = {2. Implementation of explanation-based systems},
abstract       = {Existing conflict detection methods for CSPs, such
                  as [de Kleer, 1989; Ginsbert, 1993] cannot make use
                  of powerful propagation which makes unusable for
                  complex real-world problems. On the other hand,
                  powerful constraint propagation methods lack the
                  ability to extract dependencies of conflicts, which
                  makes them unusable for many advance AI reasoning
                  methods that require conflicts, as wall as
                  interactive applications that require
                  explanations. In this paper, we present a
                  non-intrusive conflict detection algorithm called
                  QuickXPlain that tackles those problems. It can be
                  applied to any propagation or inference algorithm as
                  powerful as it may be. Our algorithm improves the
                  efficiency of direct non-intrusive conflict
                  detectors  by recursively partitioning the problem
                  into sub-problems of half of the size and by
                  immediately skipping those sub-problems that do not
                  contain an element of the conflict. QuickXPlain is
                  used as epxlanation component of an advanced
                  industrial constraint-based configuration tool. }
}

@InProceedings{ gueret-combining,
author         = {Christelle Guéret and Narendra Jussien},
title          = {Combining {AI/OR} techniques for solving Open Shop problems},
booktitle      = {Workshop on Integration of Operations Research and Artifical Intelligence techniques in Constraint Programming (CP-AI-OR)},
year           = 1999,
address        = {Ferrara, Italy},
month          = {25--26 } # feb,
type           = {5. Using explanations for designing new algorithms},
url            = {http://www.emn.fr/jussien/publications/gueret-CPAIOR99.pdf},
}

@Article{gueret-using-ejor,
author         = {Christelle Guéret and Narendra Jussien and Christian Prins},
title          = {Using intelligent backtracking to improve branch and bound methods: an application to Open-Shop problems},
journal        = {European Journal of Operational Research},
year           = 2000,
volume         = 127,
number         = 2,
pages          = {344--354},
issn           = {0377-2217},
type           = {5. Using explanations for designing new algorithms},
url            = {http://www.emn.fr/jussien/publications/gueret-EJOR00.pdf},
abstract       = {Only two branch-and-bound methods have been published
so far for the Open-Shop problem. The best one has been
proposed by Brucker {\em et al.} But some
square problems from size 7 are still unsolved by it.

We present an improving technique for branch-and-bound
methods applied to Brucker {\em et al.} algorithm for Open-Shop
problems. Our technique is based on intelligent backtracking.
Intelligent backtracking techniques involve the computation of explanations
when encountering a contradiction in the search.
We present here an adaptation of
a generic explanation system we have initially developed in the constraint
programming scheme.

We tested our approach on Open-Shop problems from the literature (benchmarks of Taillard).
The search is definitely improved
: on some square problems of size 10, the number of explored nodes is reduced by more than 90\%
and we solved an open problem of size 10.

We applied our technique on Open-Shop problems, but it can easily be adapted to solve any other shop problems with a
Branch-and-Bound in which the branching scheme consists in fixing disjunctions.},
}

@InProceedings{ jussien-avoidable,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {About avoidable computations in Interval methods},
booktitle      = {SCAN -- IMACS/GAMM international symposium on Scientific Computing, Computer Arithmetic and Validated Numerics},
pages          = 66,
year           = 1998,
address        = {Budapest, Hungary},
month          = sep,
url            = {http://www.emn.fr/jussien/publications/jussien-SCAN98.pdf},
type           = {5. Using explanations for designing new algorithms},
abstract = {Interval methods for solving systems of nonlinear equations
  typically split an interval vector or a box each time the Newton
  operator $N(x, X)$ does not lead to a sufficient narrowing.  The
  drawback of such a splitting procedure is that, when applied
  recursively, it may generate many sub-boxes, and for each sub-box,
  it is necessary to apply the Newton operator from scratch: the
  Jacobian and its inverse have to be computed, what is
  computationally expensive. So, an exponential number of expensive
  computations must be done. The behavior of the overall Interval
  Newton method is generally much better, because the Newton operator
  $N(x, X)$ generally performs well, so the number of splitting is
  low. But in some very hard cases (see for example the
  problem in [3]) a great number of sub-boxes are really generated.

Two questions come to mind: How can the number of generated sub-boxes be
  decreased?  and How can the computations over a sub-box be reused for
  another sub-box?

We will address in this paper both questions. The idea is to maintain a dependency graph that allows to
  keep reusable information when leaving a sub-box $I_1$ for another one $I_2$.
  When the information which is kept is that the sub-box  $I_2$ cannot contain any zero it is easy to see that this will   avoid  $I_2$  to be tried, so possible sub-boxes of $I_2$ are not generated.

  This work is inspired by works done in Artificial Intelligence: especially that of Ginsberg [1] and  Jussien and Lhomme [2].

[1] Matthew L. Ginsberg, Dynamic Backtracking, {\it Journal of Artificial Intelligence Research} volume 1,  pages 25--46,1993.

[2] N. Jussien, O. Lhomme,  Dynamic Domain Splitting, Proceedings of ECAI--98.  Forthcoming, 1998.

[3] Van-Hentenryck, P., Puget, J-F., A Constraint Satisfaction Approach to a Circuit Design Problem.  Journal of Global Optimization (Forthcoming).}
}

@InProceedings{ jussien-bestfirst,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {A Best First approach for solving over-constrained dynamic problems},
booktitle      = {IJCAI'97},
year           = 1997,
address        = {Nagoya, Japan},
month          = aug,
note           = {(poster -- RR 97-6-INFO -- \'Ecole des Mines de Nantes)},
type           = {4. Using explanations for solving dynamic problems},
url            = {http://www.emn.fr/jussien/publications/RR97-6-INFO.pdf},
abstract = {Many real-life problems tackled using Constraint Programming are
  dynamic. Addition and deletion of constraints may lead to
  inconsistencies. When a solution is required, constraints may be
  violated in order to fulfill the user requirements. In this
  paper, we propose a best-first search method (parameterized by the domain
  of constraints and the associated solver) for solving over-constrained
  problems arising in dynamic environments.

  We propose a specialization of this approach for CSP using
  arc-consistency. We address complexity issues to show the
  tractability of our approach and describe our implementation: the
  DECORUM system.}
}

@InProceedings{ jussien-dynamic-csp,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {Dynamic Backtracking with Constraint Propagation -- Application to static and dynamic CSPs},
booktitle      = {CP97 Workshop on The Theory and Practice of Dynamic Constraint Satisfaction},
year           = 1997,
address        = {Schloss Hagenberg, Austria},
month          = {1 } # nov,
type           = {5. Using explanations for designing new algorithms},
url            = {http://www.emn.fr/jussien/publications/jussien-WCP97a.pdf},
abstract       = {Recent works on constraint relaxation provided the
DECORUM system (Deduction-based Constraint Relaxation Management).
In this paper, we show how the ideas developed in that system can be
used in order to integrate Constraint Propagation within the Dynamic
Backtracking algorithm (Ginsberg, 1993). Dynamic Backtracking
  \emph{replaces} the backtracking process by a much less blind
  behaviour that consists in local modifications of the choices made up
  to the current situation.}
}

@InProceedings{ jussien-dynamic-numeric,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {Dynamic Backtracking with Constraint Propagation -- Application to numeric CSPs},
booktitle      = {CP97 Workshop on The Theory and Practice of Dynamic Constraint Satisfaction},
year           = 1997,
address        = {Schloss Hagenberg, Austria},
month          = {1 } # nov,
type           = {5. Using explanations for designing new algorithms},
url            = {http://www.emn.fr/jussien/publications/jussien-WCP97b.pdf},
abstract       = {Recent works on constraint relaxation provided the DECORUM system
  (Deduction-based Constraint Relaxation Management).  That system can
  be seen as an integration of arc-consistency within the
  {\em dynamic backtracking} algorithm (Ginsberg, 1993).
  {\em Dynamic backtracking} \emph{replaces} the backtracking process
  by a much less blind behavior that consists in local modifications of the
  choices made up to the current situation.  In this paper, a new
  enumeration technique over numeric CSPs is proposed: {\em dynamic
    domain splitting}.  This is a domain splitting search where
  chronological backtracking is replaced by a kind of \emph{dynamic
    backtracking}.}
}

@InProceedings{ jussien-e-constraints,
author         = {Narendra Jussien},
title          = {e-constraints: explanation-based Constraint Programming},
booktitle      = {CP01 Workshop on User-Interaction in Constraint Satisfaction},
year           = 2001,
address        = {Paphos, Cyprus},
url            = {http://www.emn.fr/jussien/publications/jussien-WCP01.pdf},
month          = {1 } # dec,
type           = {1. Theoretical foundations for explanations},
abstract       = {  In this paper, we present our experience in using explanations
  within constraint programming: how to implement an explanation
  system, what to use explanations for, how to use explanations to
  develop new algorithms. More precisely, beside classical uses
  (for debugging and/or solving dynamic problems), we introduce a
  more in-depth use of explanations that leads to a new kind of
  constraint programming that we call explanation-based constraint
  programming (e-constraints). This paper summarizes and extends
  previous works from the same author.}
}

@InProceedings{ jussien-user-friendly,
author         = {Narendra Jussien and Samir Ouis},
title          = {User-friendly explanations for constraint programming},
booktitle      = {ICLP'01 11th Workshop on on Logic Programming Environments},
year           = 2001,
address        = {Paphos, Cyprus},
month          = {1 } # dec,
type           = {3. Using explanations for debugging},
url            = {http://www.emn.fr/jussien/publications/jussien-WICLP01.pdf},
abstract       = {  In this paper, we introduce a set of tools for providing
user-friendly explanations in an explanation-based constraint
programming system. The idea is to represent the constraints of a
problem as an hierarchy (a tree). Users are then represented as a
\emph{cut} in that tree. Classical explanations (sets of
constraints) just need to get projected on that representation in
order to be understandable by any user. We present here the main
interests of this idea.}
}

@InProceedings{ jussien-implementing-lncs,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {Implementing Constraint Relaxation over Finite Domains using {ATMS}},
editor         = {Michael Jampel and Eugene Freuder and Michael Maher},
number         = 1106,
series         = {Lecture Notes in Computer Science},
pages          = {265--280},
booktitle      = {Over-Constrained Systems},
year           = 1996,
publisher      = {Springer-Verlag},
url            = {http://www.emn.fr/jussien/publications/jussien-OCSCP95.pdf},
type           = {2. Implementation of explanation-based systems},
abstract       = {Many real-life Constraint Satisfaction Problems are
  over-constrained. In order to provide some kind of solution for such
  problems, this paper proposes a constraint relaxation mechanism fully
  integrated with the constraint solver. Such a constraint relaxation
  system must be able to perform two fundamental tasks: identification
  of constraints to relax and efficient constraint suppression.
  Assumption-based Truth Maintenance Systems propose a uniform
  framework to tackle those requirements. The main idea of our
  proposal is to use the ATMS to record and efficiently use all the
  information provided by the constraint solver while checking
  consistency. We detail the use of ATMS in our particular scheme
  and enlight their efficiency by comparing them with existing
  algorithms or systems (Menezes' IHCS and Bessière's DnAC4).}
}

@InProceedings{ jussien-improving,
  author       = {Narendra Jussien and Christelle Guéret},
  title        = {Improving branch and bound algorithms for Open Shop problems},
  booktitle    = {Conference of the International Federation of Operational Research Societies (IFORS'99)},
  year         = 1999,
  address      = {Beijing, China},
  month        = aug,
  type         = {5. Using explanations for designing new algorithms},
  url          = {http://www.emn.fr/jussien/publications/jussien-IFORS99.pdf},
  abstract     = {In this paper, we consider Open-shop problems of minimal makespan. We
introduce two improving techniques for branch and bound
algorithms. The first one is an "intelligent" backtracker and the
second one is a reparation technique applied on the search tree. Definite
improvements are achieved since an open problem from the literature is solved.},
}

@InProceedings{ jussien-macdbt-cp,
  author       = {Narendra Jussien and Romuald Debruyne and Patrice Boizumault},
  title        = {Maintaining Arc-Consistency within Dynamic Backtracking},
series         = {Lecture Notes in Computer Science},
booktitle      = {Principles and Practice of Constraint Programming (CP 2000)},
publisher      = {Springer-Verlag},
number         = 1894,
  year         = 2000,
  pages        = {249--261},
  month        = sep,
  address      = {Singapore},
  type         = {5. Using explanations for designing new algorithms},
  url          = {http://www.emn.fr/jussien/publications/jussien-CP00.pdf},
  abstract     = { Most of complete search algorithms over Constraint Satisfaction
Problems (csp) are based on \emph{Standard Backtracking}.
Two main enhancements of this basic scheme have been proposed~:
first, to integrate constraint propagation as \emph{mac}
which maintains arc consistency during search;
second, intelligent backtrackers which avoid repeatedly falling in the same
dead-ends by recording nogoods as
\emph{Conflict-directed BackJumping} (\emph{cbj})
or \emph{Dynamic Backtracking} (\emph{dbt}).
Integrations of constraint propagation within intelligent backtrackers have
been proposed as
\emph{mac-cbj} which maintains arc consistency in \emph{cbj}.
However, Bessi{è}re and Régin have
%stopped further research in that field by showing
shown that \emph{mac-cbj} was very rarely better than \emph{mac}.
However, the inadequacy of \emph{mac-cbj} is more related to the fact that
\emph{cbj} does not avoid thrashing$^1$ than to the cost of the management
of nogoods.

This paper describes and evaluates \emph{mac-dbt}
which maintains arc-consistency in \emph{dbt}.
Experiments show that \emph{mac-dbt} is able to solve very large problems
and that it remains very stable as the size of the problems arises.
Moreover, \emph{mac-dbt} outperforms \emph{mac} on the structured problems we have randomly generated. },
}

@InProceedings{jussien-palm,
author         = {Narendra Jussien and Vincent Barichard},
title          = {The {PaLM} system: explanation-based constraint programming},
booktitle      = {Proceedings of {TRICS}: {T}echniques fo{R} {I}mplementing {C}onstraint programming {S}ystems, a post-conference workshop of {CP 2000}},
pages          = {118--133},
year           = 2000,
address        = {Singapore},
month          = sep,
url            = {http://www.emn.fr/jussien/publications/jussien-WCP00.pdf},
type           = {2. Implementation of explanation-based systems},
abstract       = {
  Explanation-based constraint programming is a new way of solving
  constraint problems: it allows to propagate constraints of the
  problem, learning from failure and from the solver (thanks to
  recording explanations) and finally allows to get rid of
  backtrack-based complete searches by allowing more free moves in the
  search space (while remaining complete). This paper presents the
  PaLM system, an implementation of an explanation-based constraint
  programming system in CHOCO a constraint programming
  layer on top of CLAIRE.},
}

@InProceedings{jussien-pathrepair-endm,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {The path-repair algorithm},
booktitle      = {CP99 Post-conference workshop on Large scale combinatorial optimisation and constraints},
year           = 2000,
editor         = {Suzanne Heipcke and Mark Wallace},
volume         = 4,
series         = {Electronic Notes in Discrete Mathematics},
publisher      = {Elsevier Science},
type           = {5. Using explanations for designing new algorithms},
url            = {http://www.emn.fr/jussien/publications/jussien-WCP99.pdf},
abstract       = {In this paper, we introduce a new solving algorithm for Constraint Satisfaction Problems: the path-repair algorithm. The two main points of that algorithm
     are: it makes use of a repair algorithm (local search) as a basis and it works on a partial instantiation in order to be able to use filtering techniques. Different
     versions are presented and first experiments with both systematic and non systematic versions show promising results. },
}

@InProceedings{ jussien-property,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {Best-first search for property Maintenance in reactive constraints systems},
booktitle      = {International Logic Programming Symposium},
year           = 1997,
address        = {Port Jefferson, N.Y., USA},
publisher      = {MIT Press},
pages          = {339--353},
month          = oct,
url            = {http://www.emn.fr/jussien/publications/jussien-ILPS97.pdf},
type           = {4. Using explanations for solving dynamic problems},
abstract = {Real-life dynamic problems may lead to inconsistent
constraints systems for which a solution must be found even if
constraints have to be relaxed. In this paper, we propose a best-first
search to handle such problems. Classical backtracking search
algorithms are extended in two ways: identification of good backtrack
points as in Intelligent Backtracking techniques and maximum use of
independant work (that would have been discarded with a mere
\emph{backtrack}).  We first describe an operational semantics
for our search method. Then we specialize it to handle constraint
relaxation over finite domains. The practical use of this approach is
demonstrated by theoretical complexity analysis and experiments. }
}

@InProceedings{ jussien-splitting,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {Dynamic domain splitting for numeric CSP},
booktitle      = {European Conference on Artificial Intelligence},
pages          = {224--228},
year           = 1998,
address        = {Brighton, United Kingdom},
month          = aug,
url            = {http://www.emn.fr/jussien/publications/jussien-ECAI98.pdf},
type           = {5. Using explanations for designing new algorithms},
abstract       = {In this paper, a new search technique over numeric CSPs
is presented: {\em dynamic domain splitting}.  The usual search technique
over numeric CSPs is a dichotomic search interleaved with a consistency
filtering, which is called domain splitting.  This  paper proposes to
replace chronological backtracking at the core of domain splitting by a
non destructive backtracking technique.}
}

@PhdThesis{ jussien-these,
author         = {Narendra Jussien},
title          = {Relaxation de Contraintes pour les problèmes dynamiques},
school         = {Université de Rennes I},
year           = 1997,
month          = {24 } # oct,
type           = {1. Theoretical foundations for explanations},
url            = {http://www.emn.fr/jussien/publications/jussien-THESIS.pdf},
abstract = {  La programmation par contraintes, carrefour de diverses disciplines,
  a montré son intér\^et dans de nombreux domaines d'application.
  De nombreux problèmes réels sont dynamiques~: le système de
  contraintes les définissant n'est donc pas figé. Pour résoudre
  un problème dynamique, il faut assurer une certaine
  incrémentalité et \^etre capable de traiter les systèmes de
  contraintes contradictoires. En effet, il est souvent indispensable
  de fournir une solution quitte \`a ne pas respecter certaines
  contraintes. On parle alors de relaxation de contraintes.

  Durant cette thèse, nous nous sommes intéressés \`a la
  définition d'un système de relaxation de contraintes permettant
  de maintenir une propriété donnée dans un environnement
  dynamique.  Nous avons mené ces travaux depuis une présentation
  abstraite d'un tel système jusqu'\`a son implémentation.

   Nous présentons un schéma algorithmique général abstrait de
  la recherche d'une solution \`a un problème sur-contraint basée
  sur l'exploration en meilleur d'abord d'un espace de configurations.
  Nous en donnons trois instances pour traiter les contraintes
  linéaires sur les rationnels, les {\em Constraint Satisfaction Problems} et
  les CSP numériques. Les deux dernières sont
  définies \`a l'aide d'un système de maintien de déduction dont
  la ma\^{\i}trise raisonnée nous a permis de donner une
  implémentation de ces instances ayant une \emph{bonne}
  complexité~: le système DECORUM.

  Nous montrons, par le biais d'un certain nombre
  d'expérimentations, que l'utilisation de DECORUM permet de
  retrouver les résultats classiques sur la transition de phase, de
  résoudre raisonnablement des problèmes de grande taille et
  d'utiliser la structure du problème résolu pour améliorer la
  recherche.

  Enfin, nous proposons la contrainte one-of permettant de
  modéliser et de résoudre une disjonction de contraintes en
  tirant profit du mécanisme d'exploration de DECORUM. Nous
  validons l'intér\^et de la contrainte one-of sur des
  problèmes d'ordonnancement : les Open-Shop.}
}

@InProceedings{gueheneuc-ptidej,
author         = {Yann-Gaël Guéhéneuc and Narendra Jussien},
title          = {Using explanations for design-patterns identification},
booktitle      = {IJCAI'01 Workshop on Modelling and Solving problems with constraints},
year           = 2001,
address        = {Seattle, WA, USA},
month          = aug,
type           = {3. Using explanations for debugging},
url            = {http://www.emn.fr/jussien/publications/gueheneuc-WIJCAI01.pdf},
pages          = {57--64 },
abstract       = {  Design-patterns describe micro-architectures that
                  solve recurrent architectural problems in
                  objec-oriented programming languages. It is
                  important to identify these micro-architectures
                  during the maintenant of objec-oriented
                  programs. But, these micro-architectures often
                  appear distorted in the source code. We present an
                  application of explanation-based constraint
                  programming for identifying these distorted
                  micro-architectures. },
}

@InProceedings{ albin-amiot-identifying,
author         = {Hervé Albin-Amiot and Pierre Cointe and Yann-Gaël Guéhéneuc and Narendra Jussien},
title          = {Instantiating and Detecting Design Patterns: Putting Bits and Pieces Together},
booktitle      = {16th IEEE conference on Automated Software Engineering (ASE'01)},
year           = 2001,
address        = {San Diego, USA},
month          = nov,
url            = {http://www.emn.fr/jussien/publications/albin-amiot-ASE01.pdf},
type           = {3. Using explanations for debugging},
abstract       = {Design patterns ease designing, understanding, and re-engineering software. Achieving a well-designed piece of software require a deep understanding and a good practice of design patterns. Understanding existing software relies on the ability to identify architectural forms resulting of the implementation of design patterns. Maintaining software involves spotting places that can be improved using better design decisions, like those advocated by design patterns. Nevertheless, there is a lack of tools automatizing the use of design patterns to achieve well-designed pieces of software, to identify recurrent architectural forms, and to maintain software. In this paper, we present a set of tools and techniques to help OO software practitioners design, understand, and re-engineer a piece of software, using design-patterns. A first prototype tools, Patterns-Box, provides assistance in designing the architecture of a new piece of softwaren, while a second prototype tool, Ptidej, identifies design patterns used in an existing one. These tools, in combination, support maintenance by higlighting and applying corrections based on widely-accepted design patterns solutions. }
}

@InProceedings{ bakker-diagnosing,
author = {{R. R.} Bakker and F. Dikker and F. Tempelman and {P. M.} Wognum},
title = {Diagnosing and solving over-determined constraint satisfaction problems},
booktitle = {Proceedings IJCAI'93},
year = 1993,
pages = {276--281},
type           = {6. Related works}
}

@InProceedings{ siqueira-explanation,
author = {N. {de Siqueira} and {J. F.} Puget},
title = {Explanation-based generalisation of failures},
booktitle = {Proceedings ECAI'88},
year = 1988,
pages = {339--344},
address = {Munich, Germany},
type           = {6. Related works}
}

@Article{ marquis-02,
author = {J. Amilhastre and H. Fargier and P. Marquis},
title  = {Consistency restoration and explanations in dynamic CSPs - Application to configuration},
journal = {Artificial Intelligence},
year = 2002,
volume = 135,
number = 2002,
pages = {199-234},
type           = {6. Related works}
}

@InProceedings{ FreuderLikitvivatanavongWallace:2000,
author        = {Freuder, Eugene C. and Likitvivatanavong, Chavalit and Wallace, Richard J.},
title         = {A Case Study in Explanation and Implication},
year          = {2000},
booktitle     = {In CP2000 Workshop on Analysis and Visualization of Constraint Programs and Solvers},
type           = {6. Related works}
}