narendra jussien

full professor, constraints group

école des mines de nantes - lina

» home » research

My research activities began with the design of an expert-system to recognise sea worms [Jussien et al., 1994]. Then, and it acts now as my principal research topic, I work in the field of constraint programming.

on line notes of the Dynamic Constraint Solving tutorial given at CP'03 in october 2003 [Verfaillie and Jussien, 2003]

knowledge-based systems
constraint programming
main publications (see complete list of publications)

knowledge-based systems

I started research back in 1992 when I worked on an expert-system for the recognition of annelid polychaetes (marine worms). The resulting system has been presented at an internation conference [Jussien et al., 1992] and reported in an international journal paper [Jussien et al., 1994]. Moreover, our expert-system is referenced in the Annelid Worm Bio-diversity resources web site.

constraint programming

Constraint programming is a research topic benefiting from many other areas: discrete mathematics, numerical analysis, artificial intelligence, operations research, and formal calculus. It has proven its interest and its efficiency in various domains: combinatorial optimization, scheduling, finance, simulation and synthesis, diagnosis, molecular biology, or geometrical problems.

The efficiency of constraint programming is due to several reasons:

one of the hypotheses of constraint programming, search of solutions in a bounded domain, is often naturally verified in practice where unknown values represent physical values;
tools and methods are of very general application, they are not restricted to a particular problem;
developed techniques remain usable even when considering modifications of the structure of the used constraints evolves.

However, there are still limitations to constraint programming. Many difficulties have not yet been satisfactorily solved:

designing stable and generic techniques for solving any kind of problem;
handling dynamic problems (for which the constraint system evolves): how not to solve a problem from scratch each time a modification occurs, how to only undo what is necessary when handling modifications, etc;
providing debugging and analysis tools for promoting constraint programming to non-specialists.

Broadly, one can say that I am working on extensions of current constraint systems in order to provide a complete systems able to efficiently handle dynamic problems. This leads to several research topics in the field: improving search techniques, designing analysis and debugging tools, etc. The key concept of my work is the notion of explanation [Jussien, 2003] (see also e-constraints.net).

In a few words, an explanation can be considered as a limited trace of the past activity of the constraint solver. This concept has emerged during my PhD thesis [Jussien, 1997]. I introduced a formal framework for explanations (and their extensions [Ouis et al., 2003]) in constraint programming [Jussien and Boizumault, 1997][Boizumault et al., 1994][Jussien, 2001][Jussien, 2003].

From that work, in association with Olivier Lhomme, we introduced a formal framework for describing search algorithms for constraint satisfaction problems. This framework is based upon the combination of three basic components: propagation, learning, and move. The link between those components is made through explanations [Jussien and Lhomme, 2003][Jussien and Lhomme, 2002]. This works is not only theoretical, an implementation exists: the PaLM system [Jussien and Boizumault, 1996][Jussien and Barichard, 2000][Jussien and Boizumault, 1995]. Explanations can be used for several purposes:

providing information to the user. See [Jussien and Ouis, 2001]. [Ghoniem et al., 2003] [Ouis et al., 2003][Ouis et al., 2002]
solving (over-constrained) dynamic problems. See [Jussien and Boizumault, 1996][Jussien and Boizumault, 1997] [Debruyne et al., 2003]. [Jussien and Boizumault, 1997]. and applications in software engineering [Albin-Amiot et al., 2001] or in planning and scheduling [Elkhyari et al., 2003]).
improving search. Using explanations provides new gimmicks and new techniques. This is what I call e-constraints: explanation-based constraint programming. New algorithms were introduced: MAC-DBT [Jussien et al., 2000], DynDS [Jussien and Lhomme, 1998], improved tree search for solving open-shop scheduling problems [Gu{\'e}ret et al., 2000], DECISION-REPAIR [Jussien and Lhomme, 2002][Jussien and Lhomme, 2003].

main publications

Narendra Jussien

"The versatility of using explanations within constraint programming" , École des Mines de Nantes, technical report, no. 03-04-INFO, 2003

reference, abstract, article [pdf, 18 KB]

This research report is a complete synthesis of my research activity in the filed of explanations.

International journals

Narendra Jussien, Olivier Lhomme

"Local search with constraint propagation and conflict-based heuristics" , in: "Artificial Intelligence", vol. 139, no. 1, pp. 21-45, 2002

reference, abstract, article [pdf, 170 KB]

Using explanations to outperform specialised algorithms for solving open-shop scheduling problem. Introduction of the DECISION-REPAIR algorithm

Christelle Guéret, Narendra Jussien, Christian Prins

"Using intelligent backtracking to improve branch and bound methods: an application to Open-Shop problems" , in: "European Journal of Operational Research", vol. 127, no. 2, pp. 344-354, 2000

reference, abstract, article [pdf, 146 KB]

First steps with explanations for solving scheduling problems

Selected papers

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Solving dynamic timetabling problems as dynamic resource constrained project scheduling problems using new constraint programming tools" , The Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Springer-Verlag, to appear, 2003

reference, abstract, article [pdf, 286 KB]

Solving timetabling problems as dynamic RCPSPs

International conferences

Romuald Debruyne, Gérard Ferrand, Narendra Jussien, Willy Lesaint, Samir Ouis, Alexandre Tessier

"Correctness of Constraint Retraction Algorithms" , FLAIRS'03: Sixteenth international Florida Artificial Intelligence Research Society conference, pp. 172-176, AAAI press, 2003

reference, abstract, article [pdf, 134 KB]

Theoretical work on incremental constraint retraction

Narendra Jussien, Romuald Debruyne, Patrice Boizumault

"Maintaining Arc-Consistency within Dynamic Backtracking" , Principles and Practice of Constraint Programming (CP 2000), Lecture Notes in Computer Science, no. 1894, pp. 249-261, Springer-Verlag, 2000

reference, abstract, article [pdf, 221 KB]

The MAC-DBT algorithm

Narendra Jussien, Olivier Lhomme

"Dynamic domain splitting for numeric CSP" , European Conference on Artificial Intelligence, pp. 224-228, 1998

reference, abstract, article [pdf, 165 KB]

The DynDS algorithm

Narendra Jussien, Patrice Boizumault

"Best-first search for property Maintenance in reactive constraints systems" , International Logic Programming Symposium, pp. 339-353, MIT Press, 1997

reference, abstract, article [pdf, 320 KB]

First introduction of explanations within constraint programming