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.

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.

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.

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.

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.

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.

Only two branch-and-bound methods have been published so far for the Open-Shop problem. The best one has been proposed by Brucker 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 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.

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).

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.

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 replaces the backtracking process by a much less blind behaviour that consists in local modifications of the choices made up to the current situation.

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 dynamic backtracking algorithm (Ginsberg, 1993). Dynamic backtracking 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 dynamic backtracking.

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.

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

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).

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.

Most of complete search algorithms over Constraint Satisfaction Problems (csp) are based on Standard Backtracking. Two main enhancements of this basic scheme have been proposed : first, to integrate constraint propagation as mac which maintains arc consistency during search; second, intelligent backtrackers which avoid repeatedly falling in the same dead-ends by recording nogoods as Conflict-directed BackJumping (cbj) or Dynamic Backtracking (dbt). Integrations of constraint propagation within intelligent backtrackers have been proposed as mac-cbj which maintains arc consistency in cbj. However, Bessière and Régin have %stopped further research in that field by showing shown that mac-cbj was very rarely better than mac. However, the inadequacy of mac-cbj is more related to the fact that cbj does not avoid thrashing^1 than to the cost of the management of nogoods.

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

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.

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.

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

In this paper, a new search technique over numeric CSPs is presented: 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.

La programmation par contraintes, carrefour de diverses disciplines, a montré son intérêt 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 être capable de traiter les systèmes de contraintes contradictoires. En effet, il est souvent indispensable de fournir une solution quitte à ne pas respecter certaines contraintes. On parle alors de relaxation de contraintes.

Durant cette thèse, nous nous sommes intéressés à 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'à son implémentation.

Nous présentons un schéma algorithmique général abstrait de la recherche d'une solution à 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 Constraint Satisfaction Problems et les CSP numériques. Les deux dernières sont définies à l'aide d'un système de maintien de déduction dont la ma\^\itrise raisonnée nous a permis de donner une implémentation de ces instances ayant une 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êt de la contrainte one-of sur des problèmes d'ordonnancement : les Open-Shop.

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.

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.