narendra jussien

professeur, équipe contraintes

école des mines de nantes - lina

» home » research » publications » by year » references

"Constraint Networks" , ISTE/Wiley, 2009

abstract, article [php?f=a&ACTION=View&id=250]

@Book{lecoutre-constraint-networks,
author         = {Christophe Lecoutre},
title          = {Constraint Networks},
publisher      = {ISTE/Wiley},
year           = 2009,
month          = june, 
isbn           = {9781848211063},
kind           = {LEDL},
url            = {http://iste.co.uk/index.php?f=a&ACTION=View&id=250},
abstract       = { major challenge in constraint programming is to develop efficient generic approaches to solve instances of the constraint satisfaction problem (CSP).
With this important aim in mind, this book provides an accessible synthesis of the field, including direct access to the authorÕs research in this area, divided into four main topics: representation, inference, search and learning.
The results obtained, and presented in this book, have a wide applicability, regardless of the nature of the problem to be solved or the type of constraints involved, making it an extremely user-friendly resource for those involved in this field. },
}

Christine Solnon

"Optimisation par colonies de fourmis" , Collection Programmation par Contraintes dirig{\'e}e par Narendra Jussien, Hermès Science, 2008

abstract, article [asp?id=3LKFX3BRSX2OVN]

@Book{solnon-fourmis,
author         = {Christine Solnon},
title          = {Optimisation par colonies de fourmis},
publisher      = {Herm\`es Science},
series         = {Collection Programmation par Contraintes dirig{\'e}e par Narendra Jussien},
year           = 2008, 
isbn           = {9782746218635},
kind           = {LEDL},
url            = {http://lavoisier.fr/fr/livres/not2.asp?id=3LKFX3BRSX2OVN},
abstract       = {L'optimisation par colonies de fourmis s'inspire du comportement collectif des fourmis dans la nature pour rŽsoudre des problmes d'optimisation combinatoires. Initialement proposŽe pour rŽsoudre le problme du voyageur de commerce, elle a ŽtŽ appliquŽe avec succs ˆ un grand nombre de problmes NP-difficiles. La programmation par contraintes permet de dŽcrire des problmes combinatoires de faon dŽclarative, la rŽsolution de ces problmes Žtant prise en charge par des algorithmes intŽgrŽs au langage. Cette vision de la programmation par contraintes montre les bŽnŽfices de l'optimisation par colonies de fourmis de manire large et novatrice ainsi que ses connections avec les principales approches existantes pour la rŽsolution de problmes combinatoires. Didactique, Optimisation par colonies de fourmis dresse tout d'abord un panorama des diverses mŽthodes pour la rŽsolution de problmes combinatoires et prŽsente ensuite l'optimisation par colonies de fourmis. Des chapitres applicatifs permettent une comprŽhension en profondeur de ce sujet novateur.},
}

Lakhdar Sa"is

"Problème SAT : Progrès et défis" , Collection Programmation par Contraintes dirig{\'e}e par Narendra Jussien, Hermès Science, 2008

abstract, article [asp?texte=2746218860&select=isbn&from=Hermes]

@Book{sais-sat,
author         = {Lakhdar Sa{\"i}s},
title          = {Probl\`eme SAT : Progr\`es et d\'efis},
publisher      = {Herm\`es Science},
series         = {Collection Programmation par Contraintes dirig{\'e}e par Narendra Jussien},
year           = 2008, 
isbn           = {2746218860},
kind           = {LEDL},
url            = {http://www.lavoisier.fr/fr/livres/index.asp?texte=2746218860&select=isbn&from=Hermes},
abstract       = {Cet ouvrage analyse les techniques actuelles du probl{\`e}me de satisfiabilit{\'e} propositionnelle (SAT) et {\'e}tudie ses d{\'e}fis majeurs. Ce probl{\`e}me fondamental se trouve au c\oe ur de la th{\'e}orie de la complexit{\'e} et intervient dans de nombreux domaines tels que la logique math{\'e}matique, la d{\'e}duction automatique et la programmation par contraintes. Les avanc{\'e}es spectaculaires obtenues sur la r{\'e}solution pratique de ce problme NP-Complet de r{\'e}f{\'e}rence font aujourd'hui de SAT un formalisme puissant de mod{\'e}lisation et de r{\'e}solution de nombreux probl{\`e}mes importants incluant la v{\'e}rification de mat{\'e}riel et de logiciels. Ces r{\'e}sultats ont b{\'e}n{\'e}fici{\'e} d'une synergie forte entre la th{\'e}orie, les d{\'e}veloppements algorithmiques et les applications industrielles. Probl{\`e}me SAT, progr{\`e}s et d{\'e}fis couvre divers aspects qui vont de la th{\'e}orie aux applications industrielles en passant par les techniques modernes de r{\'e}solution de SAT. Il constitue une r{\'e}f{\'e}rence id{\'e}ale pour l'{\'e}tudiant, le chercheur ou l'ing{\'e}nieur. Ce large public y trouvera donc un expos{\'e} clair et d{\'e}taill{\'e} des diff{\'e}rentes facettes d'un formalisme g{\'e}n{\'e}rique de r{\'e}solution de probl{\`e}mes difficiles.},
}

Thierry Benoist

"Décomposition combinatoires et applications industrielles" , Collection Programmation par Contraintes dirig{\'e}e par Narendra Jussien, Hermès Science, 2007

abstract, article [asp?texte=2746215690&select=isbn&from=Hermes]

@Book{benoist-decomposition,
author         = {Thierry Benoist},
title          = {D\'ecomposition combinatoires et applications industrielles},
publisher      = {Herm\`es Science},
series         = {Collection Programmation par Contraintes dirig{\'e}e par Narendra Jussien},
year           = 2007, 
isbn           = {2746215690},
kind           = {LEDL},
url            = {http://www.lavoisier.fr/fr/livres/index.asp?texte=2746215690&select=isbn&from=Hermes},
abstract       = {D{\'e}compositions combinatoires et applications industrielles propose des sch{\'e}mas de d{\'e}composition originaux applicables {\`a} la r{\'e}solution de problmes combinatoires de grande taille. Prenant appui sur les outils classiques de la recherche op{\'e}rationnelle comme l'optimisation lin{\'e}aire, la programmation par contraintes ou les m{\'e}ta-heuristiques, cet ouvrage d{\'e}veloppe des techniques de d{\'e}composition g{\'e}n{\'e}riques souvent hybrides. Ces algorithmes sont appliqu{\'e}s sur des cas r{\'e}els, issus de plusieurs ann{\'e}es de pratique de la recherche op{\'e}rationnelle au sein d'un grand groupe industriel diversifi{\'e}. Neuf applications concr{\`e}tes sont ainsi prŽsent{\'e}es, dans les domaines de la construction, de la t{\'e}l{\'e}phonie et de la t{\'e}l{\'e}vision.},
}

Arnaud Malapert, Hadrien Cambazard, Christelle Guéret, Narendra Jussien, André Langevin, Louis-Martin Rousseau

"An Optimal Constraint Programming Approach to solve the Open-Shop Problem" , in: "Journal of Computing", no. CIRRELT-2009-25, 2009

, article [pdf, 695 KB]

@ARTICLE{malapert.ea-09,
author         = {Arnaud Malapert and Hadrien Cambazard and Christelle Gu\'eret and Narendra Jussien and Andr\'e Langevin and Louis-Martin Rousseau},
title          = {An Optimal Constraint Programming Approach to solve the Open-Shop Problem},
journal        = {Journal of Computing},
year           = 2009,
number         = {CIRRELT-2009-25},
kind           = {RR},
type           = {Technical Report},
url            = {http://www.emn.fr/jussien/publications/malapert-CIRRELT-2009-25.pdf},

}

Julien Vion, Thierry Petit, Narendra Jussien

"A generic scheme for integrating strong consistencies into constraint solvers" , 14th ERCIM International Workshop on Constraint Solving and Constraint Logic Programming (CSCLP'09), 2009

, article [pdf]

@InProceedings{vion-al-wCSCLP-2009,
  author       = {Julien Vion and Thierry Petit and Narendra Jussien},
  title        = {A generic scheme for integrating strong consistencies into constraint solvers},
  booktitle    = {14th ERCIM International Workshop on Constraint Solving and Constraint Logic Programming (CSCLP'09)},
  year         = 2009,
  kind         = {MIADR},
  url          = {http://vion.free.fr/perso/publi/CSCLP2009strong.pdf},
}

Guillaume Richaud, Xavier Lorca, Narendra Jussien

"Des contraintes globales prêtes à brancher" , Cinquièmes Journées Francophones de Programmation par Contraintes (JFPC'09), pp. 115-124, 2009

abstract, article [pdf, 164 KB]

@InProceedings{richaud-pretes-a-brancher,
author         = {Guillaume Richaud and Xavier Lorca and Narendra Jussien},
title          = {Des contraintes globales pr\^etes \`a brancher},
booktitle      = {Cinqui{\`e}mes Journ{\'e}es Francophones de Programmation par Contraintes (JFPC'09)},
year           = 2009,
address        = {OrlŽans, France},
month          = jun,
kind           = {MNSA},
pages          = {115--124},
url            = {http://www.emn.fr/jussien/publications/richaud-JFPC09.pdf},
abstract       = {Les contraintes globales reprŽsentent un outil indispensable dans la rŽsolution et la modŽlisation de problmes combinatoires. Il sÕagit dÕun concept clŽ de la programmation par contraintes qui, par sa gŽnŽralitŽ, peut s'Žtendre ˆ dÕautres paradigmes. Pourtant, concevoir, implŽmenter et maintenir des contraintes globales sont des exercices difÞciles, trs liŽs au solveur sous-jacent dans lequel elles sont implŽmentŽes. Cet article vise ˆ jeter les bases de contraintes \emph{prtes ˆ brancher} clairement dŽcouplŽes du solveur h™te. Ainsi, trois points sont particulirement ŽtudiŽs : comment une contrainte globale est liŽe ˆ un solveur ? comment rendre indŽpendantes du solveur les structures de donnŽes internes des contraintes ? dans quelle mesure ce dŽcouplage introduit-il un surcožt ?  },
remark         = {new},
}

Julien Vion, Thierry Petit, Narendra Jussien

"Un schéma générique pour intégrer des consistances fortes dans les solveurs de contraintes" , Cinquièmes Journées Francophones de Programmation par Contraintes (JFPC'09), pp. 315-324, 2009

abstract, article [pdf, 366 KB]

@InProceedings{vion-fortes,
author         = {Julien Vion and Thierry Petit and Narendra Jussien},
title          = {Un sch\'ema g\'en\'erique pour int\'egrer des consistances fortes dans les solveurs de contraintes},
booktitle      = {Cinqui{\`e}mes Journ{\'e}es Francophones de Programmation par Contraintes (JFPC'09)},
year           = 2009,
address        = {OrlŽans, France},
month          = jun,
kind           = {MNSA},
pages          = {315--324},
url            = {http://www.emn.fr/jussien/publications/vion-JFPC09.pdf},
abstract       = {Nous prŽsentons un schŽma gŽnŽrique pour appliquer  
  les consistances fortes avec les outils standard de programmation par 
  contraintes. Ce schŽma est notamment applicable aux solvers Žvnementiels.  Nous proposons d'encapsuler un sous-ensemble des contraintes du modle
  dans une contrainte globale. Notre approche permet de spŽcifier un
  niveau de consistance diffŽrent pour diffŽrents sous-ensembles de
  contraintes d'un mme modle. De plus, nous montrons comment des
  consistances fortes peuvent tre appliquŽes ˆ diffŽrents types de
  contraintes, dont des contraintes dŽfinies par l'utilisateur. Afin de  
  soulligner l'efficacitŽ pratique de notre paradigme, nous proposons un
  nouvel algorithme ˆ gros grain pour Žtablir Max-RPC, nommŽ 
  Max-RPC$^{rm}$. 
  Nos expŽrimentations confirment l'intŽrt d'utiliser 
  des consistances fortes au sein des outils de programmation par
  contraintes, particulirement lorsqu'on applique un niveau de consistance 
  diffŽrent pour diffŽrents sous-ensembles de 
  contraintes dans un mme rŽseau.  },
remark         = {new},
}

Julien Vion, Thierry Petit, Narendra Jussien

"Integrating Strong Local Consistencies into Constraint Solvers" , École des Mines de Nantes, technical report, no. 09-01-INFO, 2009

@TechReport{vion-strong-rr,
title          = {Integrating Strong Local Consistencies into Constraint Solvers},
institution    = {\'Ecole des Mines de Nantes},
year           = 2009,
number         = {09-01-INFO},
address        = {Nantes, France},
kind           = {RR},
type           = {Research Report},
}

Guillaume Richaud, Xavier Lorca, Narendra Jussien

"Toward Plug & Solve Global Constraints" , École des Mines de Nantes, technical report, no. 09-02-INFO, 2009

@TechReport{richaud-plug-and-solve-rr,
author         = {Guillaume Richaud and Xavier Lorca and Narendra Jussien},
title          = {Toward Plug \& Solve Global Constraints},
institution    = {\'Ecole des Mines de Nantes},
year           = 2009,
number         = {09-02-INFO},
address        = {Nantes, France},
kind           = {RR},
type           = {Research Report},
}

Julien Menana, Sophie Demassey, Narendra Jussien

"Relaxation lagrangienne pour le filtrage d'une contrainte-automate à coûts multiples" , 10ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2009), 2009

@InProceedings{menana-relaxation,
author         = {Julien Menana and Sophie Demassey and Narendra Jussien},
title          = {Relaxation lagrangienne pour le filtrage d'une contrainte-automate {\`a} co{\^u}ts multiples},
booktitle      = {10{\`e}me congr{\`e}s de la Soci{\'e}t{\'e} Fran\c{c}aise de Recherche Op{\'e}rationnelle et d'Aide {\`a} la D{\'e}cision (ROADEF 2009)},
year           = 2009,
address        = {Nancy, France},
month          = feb,
kind           = {MNSA},
}

Hadrien Cambazard, Narendra Jussien

"Learning from the past to dynamically improve search: a case study on the MOSP problem" , Post-proceedings volume of Learning on Intelligent OptimizatioN (LION) II, Lecture Notes in Computer Science, no. 5313, pp. 69-80, Springer-Verlag, 2008

abstract

@InProceedings{cambazard-learning-lncs,
author         = {Hadrien Cambazard and Narendra Jussien},
title          = {Learning from the past to dynamically improve search: a case study on the MOSP problem},
editor         = {Vittorio Maniezzo and Roberto Battiti and Jean-Paul Watson},
year           = 2008,
number         = 5313,
booktitle      = {Post-proceedings volume of Learning on Intelligent OptimizatioN (LION) II},
publisher      = {Springer-Verlag},
kind           = {CDL},
pages          = {69--80},
isbn           = {},
series         = {Lecture Notes in Computer Science},
abstract       = {This paper presents a study conducted on the minimum number of open
stacks problem (MOSP) which occurs in various production environments
where an efficient simultaneous utilization of resources (stacks) is
needed to achieve a set of tasks. We investigate through this problem
how classical look-back reasonings based on explanations could be used
to prune the search space and design a new solving
technique. Explanations have often been used to design
intelligent backtracking mechanisms in Constraint Programming whereas
their use in nogood recording schemes has been less investigated.
In this paper, we introduce a generalized nogood (embedding explanation mechanisms) for the MOSP that leads to a new solving technique and can provide explanations.},
}

Arnaud Malapert, Christelle Guéret, Narendra Jussien, André Langevin, Louis-Martin Rousseau

"Two-Dimensional Pickup and Delivery Routing Problem with Loading Constraints" , Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport (CIRRELT), technical report, no. CIRRELT-2008-37, 2008

abstract, article [pdf, 430 KB]

@TechReport{malapert-CIRRELT-2008-37,
author         = {Arnaud Malapert and Christelle Gu{\'e}ret and Narendra Jussien and Andr{\'e} Langevin and Louis-Martin Rousseau},
title          = {Two-Dimensional Pickup and Delivery Routing Problem with Loading Constraints},
institution    = {Centre Interuniversitaire de Recherche sur les R{\'e}seaux d'Entreprise, la Logistique et le Transport (CIRRELT)},
year           = 2008,
number         = {CIRRELT-2008-37},
address        = {Montr{\'e}al, Canada},
kind           = {RR},
type           = {Research Report},
url            = {http://www.emn.fr/jussien/publications/CIRRELT-2008-37.pdf},
abstract       = {In this paper, a special case of the vehicle routing problem in which the demands consist in a set of rectangular two-dimensional weighted items is considered. The vehicles have a two-dimensional loading surface and a maximum weight capacity. These problems have a routing and a packing component. A framework to handle the loading of a vehicle is proposed. A Constraint Programming loading model based on a scheduling approach is developed. It is also shown that the non-overlapping rectangle constraint can be extended to handle a practical constraint called sequential loading constraint.},
}

Pierre-Emmanuel Hladik, Hadrien Cambazard, Anne-Marie Déplanche, Narendra Jussien

"Solving a Real-Time Allocation Problem with Constraint Programming" , in: "Journal of Systems and Software", vol. 81, no. 1, pp. 132-149, Elsevier, 2008

abstract, article [pdf, 584 KB]

@Article{hladik-allocation-real-time,
 author         = {Pierre-Emmanuel Hladik and Hadrien Cambazard and Anne-Marie D{\'e}planche and Narendra Jussien},
 title          = {Solving a Real-Time Allocation Problem with Constraint Programming},
 journal        = {Journal of Systems and Software},
 publisher      = {Elsevier},
 year           = 2008,
 volume         = 81, 
 number         = 1, 
 pages          = {132--149},
 kind           = {RIAS},
 issn           = {0164 1212},
 url            = {http://www.emn.fr/jussien/publications/hladik-JSS07.pdf},
 abstract       = {In this paper, we present an original approach (CPRTA for "Constraint Programming for solving Real-Time Allocation")  based on constraint programming to solve a static allocation problem of hard real-time tasks. This problem consists in assigning periodic tasks to distributed processors in the context of fixed priority preemptive scheduling. CPRTA is built on dynamic constraint programming together with a learning method to find a feasible processor allocation under constraints. Two efficient new approaches are proposed and validated with experimental results. Moreover, CPRTA exhibits very interesting properties. It is complete (if a problem has no solution, the algorithm is able to prove it); it is non-parametric (it does not require specific tuning) thus allowing a large diversity of models to be easily considered. Finally, thanks to its capacity to explain failures, it offers attractive perspectives for guiding the architectural design process.}
}

Narendra Jussien, Guillaume Rochart, Xavier Lorca

"The CHOCO constraint programming solver" , CPAIOR'08 workshop on Open-Source Software for Integer and Contraint Programming (OSSICP'08), 2008

abstract, article [pdf, 861 KB]

@InProceedings{jussien-invited-ossicp08,
author         = {Narendra Jussien and Guillaume Rochart and Xavier Lorca},
title          = {The CHOCO constraint programming solver},
booktitle      = {CPAIOR'08 workshop on Open-Source Software for Integer and Contraint Programming (OSSICP'08)},
  year         = 2008,
  month        = jun,
  address      = {Paris, France},
  kind         = {MIADR},
url            = {http://www.emn.fr/jussien/publications/jussien-OSSICP08.pdf},
abstract       = {Choco is a java library for constraint satisfaction problems (CSP), constraint programming (CP) and explanation-based constraint solving (e-CP). It is built on a event-based propagation mechanism with backtrackable structures. In this talk, we will present the general philosophy of the solver, its architecture and the new features of the v2 version which is currently being developed.},
}

Émilie Grellier, Pierre Dejax, Narendra Jussien

"Multiperiodic VRP models and hybrid solution techniques for closed loops-reverse logistics" , VIP'08: International Workshop on Vehicle Routing in Practice, 2008

, article [pdf, 93 KB]

@InProceedings{grellier-mvrp,
author         = {{\'E}milie Grellier and Pierre Dejax and Narendra Jussien},
title          = {Multiperiodic VRP models and hybrid solution techniques for closed loops-reverse logistics},
booktitle      = {VIP'08: International Workshop on Vehicle Routing in Practice},
year           = 2008,
address        = {Oslo, Norway},
month          = jun,
url            = {http://www.emn.fr/jussien/publications/grellier-VIP08.pdf},
kind           = {MIADR},
}

Charlotte Truchet, Damien Noguès, Narendra Jussien

"Un modèle markovien pour GSAT et WalkSAT - résultats préliminaires" , Quatrièmes Journées Francophones de Programmation par Contraintes (JFPC'08), pp. 327-336, 2008

abstract, article [pdf, 233 KB]

@InProceedings{truchet-gsat,
author         = {Charlotte Truchet and Damien Nogu\`{e}s and Narendra Jussien},
title          = {Un mod\`ele markovien pour GSAT et WalkSAT -- r\'esultats pr\'eliminaires},
booktitle      = {Quatri{\`e}mes Journ{\'e}es Francophones de Programmation par Contraintes (JFPC'08)},
year           = 2008,
address        = {Nantes, France},
pages          = {327--336},
month          = jun,
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/truchet-JFPC08.pdf},
abstract       = {Les algorithmes de recherche locale reposent toujours sur une part alŽatoire : choix du meilleur voisin, probabilitŽ de random walk, random restart, etc. Cependant,  au regard de la production de tels algorithmes, assez peu d'Žtudes les ont formalisŽs d'un point de vue probabiliste. En gŽnŽral, la convergence asymptotique est prouvŽe (Tabu Search par [Glover, Hanafi, Discrete App. Math. 2002], WalkSAT par [Hoos, AAAI, 1999]). La plupart des Žtudes plus prŽcises concernent le recuit simulŽ et les algorithmes gŽnŽtiques. Quelques unes concernent SAT, notamment [Krishnamachari et al., CP, 00] qui montre que le cožt de la meilleure solution trouvŽe est un polyn™me en p et teste la valeur optimale de p sur de trs petites instances (7 variables, 30 clauses).},
}

Arnaud Malapert, Christelle Guéret, Narendra Jussien, André Langevin, Louis-Martin Rousseau

"Two-dimensional Pickup and Delivery Routing Problem with Loading Constraints" , First CPAIOR Workshop on Bin Packing and Placement Constraints (BPPC'08), 2008

@InProceedings{malapert-2D,
author         = {Arnaud Malapert and Christelle Gu\'eret and Narendra Jussien and Andr\'e Langevin and Louis-Martin Rousseau},
title          = {Two-dimensional Pickup and Delivery Routing Problem with Loading Constraints},
booktitle      = {First CPAIOR Workshop on Bin Packing and Placement Constraints (BPPC'08)},
year           = 2008,
address        = {Paris, France},
month          = may,
kind           = {MIADR},
}

Christelle Guéret, Narendra Jussien

"Reactive approaches" , Resource-Constrained Project Scheduling - Models, algorithms, extensions and applications, pp. 191-201, ISTE/Wiley, 2008

, article [php?p=a&ACTION=View&id=172]

@InCollection{gueret-reactive,
author         = {Christelle Gu\'eret and Narendra Jussien},
title          = {Reactive approaches},
chapter        = {13},
editor         = {Christian Artigues and Sophie Demassey and Emmanuel N{\'e}ron},
booktitle      = {Resource-Constrained Project Scheduling -- Models, algorithms, extensions and applications},
year           = 2008,
publisher      = {ISTE/Wiley},
isbn           = {978-1-84821-034-9},
month          = feb, 
url            = {http://www.iste.co.uk/index.php?p=a&ACTION=View&id=172},
month          = feb, 
pages          = {191--201},
kind           = {CDL},
}

Fabien Hermenier, Xavier Lorca, Hadrien Cambazard, Jean-Marc Menaud, Narendra Jussien

"Reconfiguration dynamique du placement dans les grilles de calcul dirigée par les objectifs" , Sixième Conférence Française sur les Systèmes d'Exploitation (CFSE'08), 2008

, article [pdf, 386 KB]

@InProceedings{hermenier-reconfiguration,
author         = {Fabien Hermenier and Xavier Lorca and Hadrien Cambazard and Jean-Marc Menaud and Narendra Jussien},
title          = {Reconfiguration dynamique du placement dans les grilles de calcul dirig{\'e}e par les objectifs},
booktitle      = {Sixi{\`e}me Conf{\'e}rence Fran\c{c}aise sur les Syst{\`e}mes d'Exploitation (CFSE'08)},
year           = 2008,
address        = {Fribourg, France},
month          = feb,
url            = {http://www.emn.fr/jussien/publications/hermenier-CFSE08.pdf},
kind           = {MNSA},
}

Hadrien Cambazard, Narendra Jussien

"Learning from the past to dynamically improve search: a case study on the MOSP problem" , Learning and Intelligent OptimizatioN, 2007

abstract, article [pdf, 111 KB]

@InProceedings{cambazard-learning,
author         = {Hadrien Cambazard and Narendra Jussien},
title          = {Learning from the past to dynamically improve search: a case study on the MOSP problem},
booktitle      = {Learning and Intelligent OptimizatioN},
year           = 2007,
venue          = {Trento, Italy},
month          = dec,
kind           = {MISA},
taux           = {26/52},
url            = {http://www.emn.fr/jussien/publications/cambazard-WAAAI07.pdf},
abstract       = {This paper presents a study conducted on the minimum number of open
stacks problem (MOSP) which occurs in various production environments
where an efficient simultaneous utilization of resources (stacks) is
needed to achieve a set of tasks. We investigate through this problem
how classical look-back reasonings based on explanations could be used
to prune the search space and design a new solving
technique. Explanations have often been used to design
intelligent backtracking mechanisms in Constraint Programming whereas
their use in nogood recording schemes has been less investigated.
In this paper, we introduce a generalized nogood (embedding explanation mechanisms) for the MOSP that leads to a new solving technique and can provide explanations.},
}

Narendra Jussien

"Learning from the past to dynamically improve search" , Learning and Intelligent OptimizatioN, 2007

abstract, article [pdf, 204 KB]

@InProceedings{jussien-learning,
author         = {Narendra Jussien},
title          = {Learning from the past to dynamically improve search},
booktitle      = {Learning and Intelligent OptimizatioN},
year           = 2007,
venue          = {Trento, Italy},
month          = dec,
kind           = {MIADR},
taux           = {26/52},
url            = {http://www.emn.fr/jussien/publications/cambazard-LION07.pdf},
abstract       = {This paper presents a study conducted on the minimum number of open stacks problem (MOSP) which occurs in various production environments where an efficient simultaneous utilization of resources (stacks) is needed to achieve a set of tasks. We investigate through this problem how classical look-back reasonings based on explanations could be used to prune the search space and design a new solving technique. Explanations have often been used to design intelligent backtracking mechanisms in Constraint Programming whereas their use in nogood recording schemes has been less investigated. In this paper, we introduce a generalized nogood (embedding explanation mechanisms) for the MOSP that leads to a new solving technique and can provide explanations.},
}

Guillaume Richaud, Xavier Lorca, Narendra Jussien

"A portable and efficient implementation of global constraints: the TREE constraint case" , Seventh Colloquium on Implementation of Constraint and LOgic Programming Systems (CICLOPS'07), 2007

abstract, article [pdf, 105 KB]

@InProceedings{richaud-portable,
author         = {Guillaume Richaud and Xavier Lorca and Narendra Jussien},
title          = {A portable and efficient implementation of global constraints: the {TREE} constraint case},
booktitle      = {Seventh Colloquium on Implementation of Constraint and {LO}gic Programming Systems (CICLOPS'07)},
year           = 2007,
venue          = {Porto, Portugal},
month          = sep,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/richaud-CICLOPS07.pdf},
abstract       = {Global constraints represent invaluable modeling tools for
Constraint Programming (CP). Efficiently solving recurrent
subproblems is a key point for CP successes. However, global
constraints mainly remain strongly attached to a given constraint
solver. Indeed, they heavily rely on internal mechanisms in order to
be as efficient as possible. In this paper, we emphasize the
interest of decoupling global constraint implementations from the
underlying solver. We show, on a TREE constraint, that even more
decoupling it by providing fully dynamic algorithms enhances
efficiency and, which is much more important, allow an efficient
portability of the constraint. We illustrate this for the
Choco and Gecode solvers.},
}

Narendra Jussien

"Les contraintes au secours du décisionnel" , Table ronde de la session industrielle des JFPC 2007, 2007

@Misc{jussien-jfpc07,
author        = {Narendra Jussien},
title         = {Les contraintes au secours du d{\'e}cisionnel},
howpublished  = {Table ronde de la session industrielle des JFPC 2007},
month         = jun,
year          = 2007,
address       = {Rocquencourt, France},
kind          = {DIVERS},
}

Hadrien Cambazard, Narendra Jussien

"Solving the Minimum number of Open Stacks Problem with explanation-based techniques" , AAAI-07 Workshop Explanation-aware Computing (ExaCt2007), 2007

abstract, article [pdf, 111 KB]

@InProceedings{cambazard-mosp-exact,
author         = {Hadrien Cambazard and Narendra Jussien},
title          = {Solving the Minimum number of Open Stacks Problem with explanation-based techniques},
booktitle      = {AAAI-07 Workshop Explanation-aware Computing (ExaCt2007)},
year           = 2007,
address        = {Vancouver, Canada},
month          = jul,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/cambazard-WAAAI07.pdf},
abstract       = {This paper presents a study conducted on the minimum number of open
stacks problem (MOSP) which occurs in various production environments
where an efficient simultaneous utilization of resources (stacks) is
needed to achieve a set of tasks. We investigate through this problem
how classical look-back reasonings based on explanations could be used
to prune the search space and design a new solving
technique. Explanations have often been used to design
intelligent backtracking mechanisms in Constraint Programming whereas
their use in nogood recording schemes has been less investigated.
In this paper, we introduce a generalized nogood (embedding explanation mechanisms) for the MOSP that leads to a new solving technique and can provide explanations.},
}

Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie Déplanche, Narendra Jussien

"Une contrainte globale pour l'ordonnançabilité des tâches temps réel dur" , Troisièmes Journées Francophones de Programmation par Contraintes (JFPC'07), pp. 367-376, 2007

, article [pdf, 366 KB]

@InProceedings{cambazard-temps-reel-global,
author         = {Hadrien Cambazard and Pierre-Emmanuel Hladik and Anne-Marie D{\'e}planche and Narendra Jussien},
title          = {Une contrainte globale pour l'ordonnan\c{c}abilit\'e des t\^aches temps r\'eel dur},
booktitle      = {Troisi{\`e}mes Journ{\'e}es Francophones de Programmation par Contraintes (JFPC'07)},
year           = 2007,
address        = {Rocquencourt, France},
month          = jun,
pages          = {367--376},
url            = {http://www.emn.fr/jussien/publications/cambazard-JFPC07.pdf},
kind           = {MNSA},
taux           = {37/47},
abstract       = {Rsoudre des problmes de placement de täches temps rel est un challenge pour les communauts issues de la recherche oprationnelle et de la programmation par contraintes. La difficult principale de tels problmes rside dans la prise en considration des contraintes temporelles spcifiques aux systmes temps rel. Ces contraintes sont difficilement exprimables pour un solveur et mritent donc un traitement particulier. Dans ce papier, nous proposons une approche novatrice qui introduit ces aspects temporels par le biais d'une contrainte globale et donc directement dans les mcanismes de la ppc. Nous finalisons l'tude en montrant ö travers de nombreuses exprimentations que cette mthode est viable et efficace.}, 
}

Émilie Grellier, Pierre Dejax, Narendra Jussien

"An Inventory Pick-up and Delivery Problem in the Reverse Logistics Context: Optimization using a GRASP and hybrid approach" , 7th Metaheuristics International Conference (MIC'2007), 2007

abstract, article [pdf, 21 KB]

@InProceedings{grellier-inventory,
author         = {{\'E}milie Grellier and Pierre Dejax and Narendra Jussien},
title          = {An Inventory Pick-up and Delivery Problem in the Reverse Logistics Context: Optimization using a GRASP and hybrid approach},
booktitle      = {7th Metaheuristics International Conference (MIC'2007)},
year           = 2007,
address        = {Montreal, Canada},
month          = jun,
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/grellier-MIC07.pdf},
abstract       = {We consider the multiperiodic planning and optimization of transport activities (direct and reverse), and inventory management in a two level distribution network. The goal is to satisfy the customers demands while minimizing the routing and storage costs. We use the GRASP and a hybrid approach to solve this problem.},
}

Émilie Grellier, Pierre Dejax, Narendra Jussien

"Heuristiques de construction et améliorations pour les problèmes de tournés de livraisons multi-périodiques incluant les concepts de logistique inverse" , École des Mines de Nantes, technical report, no. 07-01-AUTO, 2007

@TechReport{grellier-heuristiques-rr,
author         = {{\'E}milie Grellier and Pierre Dejax and Narendra Jussien},
title          = {Heuristiques de construction et am{\'e}liorations pour les probl{\`e}mes de tourn{\'e}s de livraisons multi-p{\'e}riodiques incluant les concepts de logistique inverse},
institution    = {\'Ecole des Mines de Nantes},
year           = 2007,
number         = {07-01-AUTO},
address        = {Nantes, France},
kind           = {RR},
type           = {Research Report},
}

Frédéric Benhamou, Narendra Jussien, Barry O'Sullivan

"Trends in Constraint Programming" , ISTE, 2007

abstract, article [php?f=a&ACTION=View&id=154]

@Book{benhamou-jussien-sullivan-trends,
author         = {Fr{\'e}d{\'e}ric Benhamou and Narendra Jussien and Barry O'Sullivan},
title          = {Trends in Constraint Programming},
publisher      = {ISTE},
year           = 2007,
month          = may, 
isbn           = {1905209975},
kind           = {LEDL},
url            = {http://iste.co.uk/index.php?f=a&ACTION=View&id=154},
abstract       = {Constraint programming is a constantly evolving field, something which is explored at the annual International Conference on Principles and Practice of Constraint Programming. This conference provides papers and workshops which produce new insights, concepts and results which those involved in this area can then use to develop their own work. This title provides an accessible overview of this by bringing together the best papers on a range of topics within this subject area, thus allowing those involved in constraint programming to benefit from the new innovations and results created as a result of the conference.  },
}

Narendra Jussien

"A to Z of sudoku" , ISTE, 2007

abstract, article [php?f=x&ACTION=View&id=188]

@Book{jussien-sudoku-english,
author         = {Narendra Jussien},
title          = {A to Z of sudoku},
publisher      = {ISTE},
year           = 2007,
isbn           = {9781847040008},
kind           = {LEDL},
url            = {http://iste.co.uk/index.php?f=x&ACTION=View&id=188},
abstract       = {The science behind Sudoku ... Sudoku is a logic puzzle that has become a worldwide phenomenon in the last few years: but where has it come from? How does it work? And what is the science behind sudoku - what are the rules for generating and solving grids? Answers to all of these questions can be found in the A-Z of Sudoku. As its title suggests, this book provides a "one stop shop" on sudoku, covering the history of the puzzle, its development and growth in the world's media, before moving on to the mathematics of sudoku and various techniques that can be used to solve grids by hand. Next, the essentials of software development relating to sudoku are presented along with the recent branch of computer science devoted to solving such problems: constraint programming, showing how the principle behind solving sudoku grids can be used in other contexts. Finally, the book concludes with a large number of grids ranging in difficulty from "very easy" to "expert" which the reader can use to apply the techniques they have acquired from the book in a practical context. Those interested in finding out more about the theory behind sudoku, its origins, it applications in other fields and (of course) how to improve their ability to solve it will find this book a must-read.  },
}

Émilie Grellier, Pierre Dejax, Narendra Jussien

"Problème de tournées de collectes et livraisons multi-périodique : résolution grâce au GRASP" , 5èmes journées Francophones de Recherche Opérationnelle (FRANCORO V) 8ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2007), 2007

, article [pdf, 163 KB]

@InProceedings{grellier-grasp,
author         = {{\'E}milie Grellier and Pierre Dejax and Narendra Jussien},
title          = {Probl{\`e}me de tourn{\'e}es de collectes et livraisons multi-p{\'e}riodique~: r{\'e}solution gr{\^a}ce au {GRASP}},
booktitle      = {5{\`e}mes  journ{\'e}es Francophones de Recherche Op{\'e}rationnelle (FRANCORO V) 8{\`e}me congr{\`e}s de la Soci{\'e}t{\'e} Fran\c{c}aise de Recherche Op{\'e}rationnelle et d'Aide {\`a} la D{\'e}cision (ROADEF 2007)},
year           = 2007,
address        = {Grenoble, France},
month          = feb,
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/grellier-ROADEF07.pdf},
}

Hadrien Cambazard, Narendra Jussien

"Des explications pour reconna\^\itre et exploiter les structures cachées d'un problème combinatoire" , in: "RAIRO - Operations Research", vol. 40, no. 4, pp. 381-401, EDP Science, 2006

abstract, article [pdf, 1372 KB]

@Article{cambazard-structures-rairo,
 author         = {Hadrien Cambazard and Narendra Jussien},
 title          = {Des explications pour reconna{\^\i}tre et exploiter les structures cach{\'e}es d'un probl{\`e}me combinatoire},
 journal        = {RAIRO -- Operations Research},
 publisher      = {EDP Science},
 year           = 2006,
 kind           = {RIAS},
 issn           = {0399 0559},
 volume         = 40,
 number         = 4, 
 pages          = {381--401},
 url            = {http://www.emn.fr/jussien/publications/cambazard-RAIRO06.pdf},
 abstract       = {L'identification de structures propres ˆ un problme est souvent une Žtape clef pour la conception d'heuristiques de recherche comme pour la comprŽhension de la complexitŽ du problme. De nombreuses approches en Recherche OpŽrationnelle emploient des stratŽgies de relaxation ou de dŽcomposition ds lors que certaines struc- tures idoines ont ŽtŽ identifiŽes. L'Žtape suivante est la conception d'algorithmes de rŽsolution qui puissent intŽgrer ˆ la volŽe, pendant la rŽsolution, ce type d'information. Cet article propose d'utiliser un solveur de contraintes ˆ base d'explications pour collecter une information pertinente sur les structures dynamiques et statiques inhŽrentes au problme.},
}

François Fages, Narendra Jussien, Christine Solnon

"Special Issue: Journés Francophones de Programmation par Contraintes 2005" , RAIRO -- Operations Research, vol. 40, no. 4, EDP Science, 2006

, article [pdf, 29 KB]

@Book{fages-jussien-solnon-rairo-jfpc,
editor         = {Fran\c{c}ois Fages and Narendra Jussien and Christine Solnon},
title          = {Special Issue: Journ{\'e}s Francophones de Programmation par Contraintes 2005},
publisher      = {EDP Science},
year           = 2006,
volume         = 40,
number         = 4, 
series         = {RAIRO -- Operations Research},
issn           = {0399 0559},
kind           = {LEDL},
url            = {http://www.emn.fr/jussien/publications/fages-RAIRO06.pdf},
}

Narendra Jussien

"Le dŽcisionnel secouru par la programmation par contraintes" , in: "01 informatique", no. 1882, pp. 34, Groupe Tests, 2006

, article [pdf, 400 KB]

@Article{jussien-decisionnel-01info,
 author         = {Narendra Jussien},
 title          = {Le dŽcisionnel secouru par la programmation par contraintes},
 journal        = {01 informatique},
 publisher      = {Groupe Tests},
 year           = 2006,
 number         = {1882}, 
 month          = {24 } # nov,
 pages          = {34},
 kind           = {RSS},
 url            = {http://www.emn.fr/jussien/publications/jussien-01informatique.pdf},
}

Hadrien Cambazard, Narendra Jussien, François Laburthe, Guillaume Rochart

"The CHOCO Constraint Solver" , INFORMS Annual meeting, 2006

abstract

@InProceedings{cambazard-choco-informs,
author         = {Hadrien Cambazard and Narendra Jussien and Fran\c{c}ois Laburthe and Guillaume Rochart},
title          = {The CHOCO Constraint Solver},
booktitle      = {INFORMS Annual meeting},
year           = 2006,
address        = {Pittsburgh, PA, USA},
month          = nov,
kind           = {MIADR},
abstract       = {The CHOCO constraint solver is an emanation of a French academic group. Choco is a java library for constraint satisfaction problems, constraint programming, and explanation-based constraint solving. It is built on an event-based propagation mechanism with backtrackable structures. Choco also provides explanations as both an analysing and solving tool for constraint programming, uncommon search mechanisms including the decision-repair and the logical Benders decomposition schemes, etc.},
}

Narendra Jussien

"Combien de grilles de sudoku" , in: "Sudoku de la Fédération Française", no. 7, pp. 5, Keesing, 2006

, article [pdf, 974 KB]

@Article{jussien-sudoku-decembre2006,
 author         = {Narendra Jussien},
 title          = {Combien de grilles de sudoku},
 journal        = {Sudoku de la F{\'e}d{\'e}ration Fran\c{c}aise},
 publisher      = {Keesing},
 year           = 2006,
 number         = 7, 
 pages          = {5},
 kind           = {RSS},
 url            = {http://www.emn.fr/jussien/publications/jussien-SUDOKU06d.pdf},
}

Narendra Jussien

"PrŽcis de Sudoku" , Hermes Science, 2006

abstract, article [asp?texte=2746215594&select=isbn&from=Hermes]

@Book{jussien-sudoku,
author         = {Narendra Jussien},
title          = {PrŽcis de Sudoku},
publisher      = {Hermes Science},
year           = 2006,
isbn           = {2746215594},
kind           = {LEDL},
url            = {http://www.lavoisier.fr/fr/livres/index.asp?texte=2746215594&select=isbn&from=Hermes},
abstract       = {Le sudoku est devenu un jeu de logique trs populaire. Ce PrŽcis de sudoku permet de dŽcouvrir les origines de ce jeu et d'apprendre ˆ le rŽsoudre par la prŽsentation de rgles mathŽmatiques ou logiques. Prs de quinze rgles et techniques sont ŽtudiŽes, illustrŽes d'exemples et d'exercices progressifs, depuis les grilles trs faciles aux grilles experts. Ce prŽcis explique les principes essentiels de la programmation d'un logiciel pour rŽsoudre n'importe quelle grille de sudoku. Il expose les aspects importants du processus de gŽnŽration de grilles et du procŽdŽ d'Žvaluation de leur difficultŽ. L'ouvrage propose aussi plus de cent vingt grilles de niveau croissant pour mieux ma”triser ce jeu.  },
}

Hadrien Cambazard, Narendra Jussien

"Identifying and exploiting problem structures using explanation-based constraint programming" , in: "Constraints", vol. 11, no. 4, pp. 295-313, Springer Verlag, 2006

abstract, article [pdf, 655 KB]

@Article{cambazard-structures-constraints,
 author         = {Hadrien Cambazard and Narendra Jussien},
 title          = {Identifying and exploiting problem structures using explanation-based constraint programming},
 journal        = {Constraints},
 publisher      = {Springer Verlag},
 year           = 2006,
 volume         = 11,
 number         = 4, 
 pages          = {295--313},
 kind           = {RIAS},
 url            = {http://www.emn.fr/jussien/publications/cambazard-CONSTRAINTS06.pdf},
 abstract       = {Identifying structures in a given combinatorial problem is often a
key step for designing efficient search heuristics or for
understanding the inherent complexity of the problem. Several
Operations Research approaches apply decomposition or relaxation
strategies upon such a structure identified within a given problem.
The next step is to design algorithms that adaptively integrate that
kind of information during search. We claim in this paper, inspired
by previous work on impact-based search strategies for constraint
programming, that using an explanation-based constraint solver may
lead to collect invaluable information on the intimate dynamically
revealed and static structures of a problem instance. Moreover, we
discuss how dedicated OR solving strategies (such as Benders
decomposition) could be adapted to constraint programming when
specific relationships between variables are
exhibited.}
}

Narendra Jussien

"Les couleurs du sudoku" , in: "Sudoku de la Fédération Française", no. 6, pp. 5, Keesing, 2006

, article [pdf, 1058 KB]

@Article{jussien-sudoku-novembre2006,
 author         = {Narendra Jussien},
 title          = {Les couleurs du sudoku},
 journal        = {Sudoku de la F{\'e}d{\'e}ration Fran\c{c}aise},
 publisher      = {Keesing},
 year           = 2006,
 number         = 6, 
 pages          = {5},
 kind           = {RSS},
 url            = {http://www.emn.fr/jussien/publications/jussien-SUDOKU06c.pdf},
}

Narendra Jussien

"Sudoku et programmation par contraintes" , in: "Sudoku de la Fédération Française", no. 3, pp. 5, Keesing, 2006

, article [pdf, 652 KB]

@Article{jussien-sudoku-aout2006,
 author         = {Narendra Jussien},
 title          = {Sudoku et programmation par contraintes},
 journal        = {Sudoku de la F{\'e}d{\'e}ration Fran\c{c}aise},
 publisher      = {Keesing},
 year           = 2006,
 number         = 3, 
 pages          = {5},
 kind           = {RSS},
 url            = {http://www.emn.fr/jussien/publications/jussien-SUDOKU06.pdf},
}

Narendra Jussien

"Évaluer la difficultŽ d'une grille de sudoku" , in: "Sudoku de la Fédération Française", no. 5, pp. 5, Keesing, 2006

, article [pdf, 675 KB]

@Article{jussien-sudoku-octobre2006,
 author         = {Narendra Jussien},
 title          = {\'Evaluer la difficultŽ d'une grille de sudoku},
 journal        = {Sudoku de la F{\'e}d{\'e}ration Fran\c{c}aise},
 publisher      = {Keesing},
 year           = 2006,
 number         = 5, 
 pages          = {5},
 kind           = {RSS},
 url            = {http://www.emn.fr/jussien/publications/jussien-SUDOKU06b.pdf},
}

Guillaume Richaud, Hadrien Cambazard, Barry O'Sullivan, Narendra Jussien

"Automata for Nogood recording in Constraint satisfaction Problems" , CP06 Workshop on the Integration of SAT and CP techniques, 2006

abstract, article [pdf, 254 KB]

@InProceedings{richaud-automata,
author         = {Guillaume Richaud and Hadrien Cambazard and Barry {O'Sullivan} and Narendra Jussien},
title          = {Automata for Nogood recording in Constraint satisfaction Problems},
booktitle      = {CP06 Workshop on the Integration of SAT and CP techniques},
year           = 2006,
address        = {Nantes, France},
month          = sep,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/richaud-WCP06.pdf},
abstract       = {Nogood recording is a well known technique for reducing the thrashing
 encountered by tree search algorithms.
One of the most significant disadvantages of nogood recording has been
 its prohibitive space complexity.
In this paper we attempt to mitigate this by using an automaton
 to compactly represent a set of nogoods.
We demonstrate how nogoods can be propagated using a known algorithm for
 achieving generalised arc consistency.
Our experimental results on a number of benchmark problems demonstrate
 the utility of our approach.},
}

Narendra Jussien

"Logique(s), langages formels et complexité pour l'informatique" , Hermes Science, 2006

abstract, article [asp?texte=2746213950&select=isbn&from=Hermes]

@Book{jussien-llc,
author         = {Narendra Jussien},
title          = {Logique(s), langages formels et complexit{\'e} pour l'informatique},
publisher      = {Hermes Science},
year           = 2006,
isbn           = {2746213958},
kind           = {LEDL},
url            = {http://www.lavoisier.fr/fr/livres/index.asp?texte=2746213950&select=isbn&from=Hermes},
abstract       = {Logique(s), langages formels et complexitŽ pour l'informatique analyse les bases thŽoriques sur la logique et les fondements de l'informatique. L'ouvrage s'intŽresse d'abord ˆ la logique formelle. Il s'agit d'explorer les outils permettant de manipuler les composants de bases des donnŽes d'un ordinateur, d'Žtudier les concepts nŽcessaires ˆ l'automatisation de raisonnements logiques avec une incursion vers d'autres logiques que les logiques classiques. Il traite ensuite des notions de langage formel et d'automate. Les principes de bases de ces outils mathŽmatiques ˆ l'origine de la thŽorie des langages de programmation sont exposŽs ainsi que leurs nombreuses applications directes.
Enfin, il met en Žvidence les limites de l'informatique et prŽsente les outils thŽoriques nŽcessaires ˆ la dŽlimitation entre ce que peut et ce que ne peut pas faire un ordinateur. Ce livre offre en complŽment des points de repre historiques, depuis Aristote jusqu'ˆ Turing ou Zadeh en passant par Boole, Gšdel, Chomsky ou Robinson. Il propose aussi cent soixante-dix exercices corrigŽs. },
}

Thierry Benoist, Antoine Jeanjean, Guillaume Rochart, Hadrien Cambazard, Emilie Grellier, Narendra Jussien

"Subcontractors scheduling on residential buildings construction sites" , ISS'06 International Scheduling Symposium, Technical Report JSME-06-203, pp. 32-37, Japan Society of Mechanical Engineers, 2006

, article [pdf, 108 KB]

@InProceedings{benoist-subcontractors,
author         = {Thierry Benoist and Antoine Jeanjean and Guillaume Rochart and Hadrien Cambazard and Emilie Grellier and Narendra Jussien},
title          = {Subcontractors scheduling on residential buildings construction sites},
booktitle      = {ISS'06 International Scheduling Symposium},
year           = 2006,
pages          = {32--37},
publisher      = {Japan Society of Mechanical Engineers},
address        = {Arcadia Ichigaya, Tokyo, Japan},
month          = jul,
series         = {Technical Report JSME-06-203},
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/benoist-ISS06.pdf},
}

Narendra Jussien, Vincent Barichard

"MultiObjective Optimization and Constraint Programming" , Seventh international Conference devoted to Multi-Objective Programming and Goal Programming (MOPGP'06), 2006

, article [pdf, 69 KB]

@InProceedings{jussien-mopgp,
author         = {Narendra Jussien and Vincent Barichard},
title          = {MultiObjective Optimization and Constraint Programming},
booktitle      = {Seventh international Conference devoted to Multi-Objective Programming and Goal Programming (MOPGP'06)},
year           = 2006,
address        = {Vall{\'e}e de la Loire, France},
month          = jun,
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/jussien-MOPGP06.pdf},
}

François Laburthe, Guillaume Rochart, Narendra Jussien

"Évaluer la difficulté d'une grille de Sudoku à l'aide d'un modèle contraintes" , Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC'06), pp. 239-248, 2006

abstract, article [pdf, 413 KB]

@InProceedings{laburthe-sudoku,
author         = {Fran\c{c}ois Laburthe and Guillaume Rochart and Narendra Jussien},
title          = {{\'E}valuer la difficult{\'e} d'une grille de Sudoku {\`a} l'aide d'un mod{\`e}le contraintes},
booktitle      = {Deuxi{\`e}mes Journ{\'e}es Francophones de Programmation par Contraintes (JFPC'06)},
year           = 2006,
address        = {N{\^\i}mes, France},
month          = jun,
pages          = {239--248},
url            = {http://www.emn.fr/jussien/publications/laburthe-JFPC06.pdf},
kind           = {MNSA},
taux           = {38/48},
abstract       = {Le sudoku est un jeu de logique qui est devenu en quelques mois un phŽnomne de sociŽtŽ en France. Il envahit les mŽtros, les trains, les bus, les salles de cours et mme le journal \emph{Le Monde}. Gr‰ce ˆ ce jeu, le grand public est devenu le M. Jourdain de la Programmation Par Contraintes. En effet, l'intŽrt de ce jeu pour montrer trs rapidement et trs simplement les principes premiers de la programmation par contraintes n'est plus ˆ dŽmontrer. De plus, la technologie contraintes est trs performante pour modŽliser ˆ l'aide de quelques contraintes globales ce problme et le rŽsoudre quasiment simplement par propagation. Par contre, la mesure de la difficultŽ d'une grille -- qui laisse ˆ dŽsirer pour de nombreuses instances publiŽes actuellement -- n'a pas encore ŽtŽ capturŽe de manire satisfaisante par un modle contraintes. Une raison est qu'une telle mesure est totalement subjective car elle dŽpend de la faon dont un joueur aborde son instance. Dans cet article, nous montrons qu'il est possible de dŽfinir des modles contraintes permettant de retrouver des combinaisons de rgles utilisŽes par les joueurs. Ces modles ouvrent la porte ˆ une Žvaluation de la difficultŽ d'une instance par une approche purement contraintes et mme de fournir des systmes d'aide eux-aussi basŽs sur un telle approche. }
}

Hadrien Cambazard, Narendra Jussien

"Techniques rétrospectives pour résoudre le Minimum Open Stacks Problem" , Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC'06), pp. 89-98, 2006

abstract, article [pdf, 215 KB]

@InProceedings{cambazard-mosp,
author         = {Hadrien Cambazard and Narendra Jussien},
title          = {Techniques r{\'e}trospectives pour r{\'e}soudre le Minimum Open Stacks Problem},
booktitle      = {Deuxi{\`e}mes Journ{\'e}es Francophones de Programmation par Contraintes (JFPC'06)},
year           = 2006,
address        = {N{\^\i}mes, France},
month          = jun,
pages          = {89--98},
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/cambazard-JFPC06.pdf},
taux           = {38/48},
abstract       = {Nous prŽsentons une Žtude de cas sur le MOSP (minimum number of open stacksproblem). Ce problme se rencontre dans des environnements de production o la
rŽalisation d'un ensemble de t‰ches nŽcessite une utilisation simultanŽe
de diffŽrentes ressources (les piles -- stacks). Ë travers ce
problme, nous cherchons comment des raisonnements rŽtrospectifs assez classiques
mais basŽs sur les explications peuvent tre utilisŽs pour Žlaguer
l'espace de recherche. Les explications ont, en effet, souvent ŽtŽ
utilisŽes pour mettre en place des mŽcanismes sophistiquŽs de retour
arrire dans le cadre de la programmation par contraintes mais trs peu dans des
schŽmas de type nogood recording. Ce n'est pas le cas dans la communautŽ
SAT o la notion de clause apprise joue un grand r™le aussi bien pour
l'Žlagage de l'espace de recherche que pour l'exploration elle-mme. Dans cet
article, nous introduisons un nogood gŽnŽralisŽ (basŽ sur les
explications) pour le MOSP qui nous permet d'introduire une nouvelle technique de rŽsolution. Des rŽsultats expŽrimentaux montrent l'intŽrt d'une
telle approche pour le MOSP et la capacitŽ des explications ˆ identifier et ˆ
exploiter dynamiquement la structure de ces problmes.}
}

Guillaume Richaud, Hadrien Cambazard, Narendra Jussien

"Suppression de symétries pour les méthodes rétro-prospectives" , Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC'06), pp. 295-304, 2006

abstract, article [pdf, 193 KB]

@InProceedings{richaud-symetries,
author         = {Guillaume Richaud and Hadrien Cambazard and Narendra Jussien},
title          = {Suppression de sym{\'e}tries pour les m{\'e}thodes r{\'e}tro-prospectives},
booktitle      = {Deuxi{\`e}mes Journ{\'e}es Francophones de Programmation par Contraintes (JFPC'06)},
year           = 2006,
address        = {N{\^\i}mes, France},
month          = jun,
pages          = {295--304},
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/richaud-JFPC06.pdf},
taux           = {38/48},
abstract       = {Les techniques de suppression de symŽtries dŽveloppŽes pour la
programmation par contraintes ont pour objectif d'amŽliorer
l'efficacitŽ des mŽthodes de rŽsolution en rŽduisant drastiquement la
taille de l'espace de recherche. Paralllement, les mŽthodes de
rŽsolution rŽcentes, telles que les mŽthodes rŽtro-prospectives,
permettent de s'attaquer ˆ des problmes de plus en plus grands, que ce
soit par la taille des domaines ou le nombre de variables considŽrŽes,
et dont l'espace de recherche augmente bien sžr lui aussi.  Il para”t
donc intŽressant de faire profiter les mŽthodes rŽtro-prospectives des
amŽliorations permises par les techniques de suppression de symŽtries
qui ont cependant ŽtŽ dŽveloppŽes pour un cadre plus classique
d'exploration.  Dans cet article, nous proposons donc un algorithme
hybridant une mŽthode rŽtro-prospective (\texttt{decision-repair}) et une
technique gŽnŽrique de suppression de symŽtries (SBDS). Nous prŽsentons
plusieurs approches pour exprimer et traiter efficacement dans ce
cadre les contraintes liŽes ˆ la suppression des symŽtries. De
premiers rŽsultats expŽrimentaux valident la dŽmarche.}
}

Narendra Jussien

"De l'information à la décision : approche prospective du décisionnel" , Soirée Atlanticiels - le rendez-vous TIC de la métropole Nantes-Atlantique, 2006

, article [atlanticiels.com]

@Misc{jussien-atlanticiels06,
author        = {Narendra Jussien},
title         = {De l'information {\`a} la d{\'e}cision~: approche prospective du d{\'e}cisionnel},
howpublished  = {Soir{\'e}e Atlanticiels -- le rendez-vous TIC de la m{\'e}tropole Nantes-Atlantique},
month         = mar,
year          = 2006,
kind          = {DIVERS},
url           = {http://www.atlanticiels.com},
}

Pierre-Emmanuel Hladik, Hadrien Cambazard, Anne-Marie Déplanche, Narendra Jussien

"Guiding Architectural Design Process of Hard Real-Time Systems with Constraint Programming" , Third Taiwanese-French Conference on Information Technology (TFIT 2006), pp. 317-331, 2006

, article [pdf, 353 KB]

@InProceedings{hladik-guiding,
author         = {Pierre-Emmanuel Hladik and Hadrien Cambazard and Anne-Marie D{\'e}planche and Narendra Jussien},
title          = {Guiding Architectural Design Process of Hard Real-Time Systems with Constraint Programming},
booktitle      = {Third Taiwanese-French Conference on Information Technology (TFIT 2006)},
year           = 2006,
address        = {Nancy, France},
month          = mar,
pages          = {317--331},
url            = {http://www.emn.fr/jussien/publications/hladik-TFIT06.pdf},
kind           = {MIADR},
}

Pierre-Emmanuel Hladik, Hadrien Cambazard, Anne-Marie Déplanche, Narendra Jussien

"Solving allocation problems of hard real-time systems with dynamic constraint programming" , 14th International Conference on Real-Time and Network Systems (RTNS06), 2006

, article [pdf, 276 KB]

@InProceedings{hladik-allocation-rtns,
author         = {Pierre-Emmanuel Hladik and Hadrien Cambazard and Anne-Marie D{\'e}planche and Narendra Jussien},
title          = {Solving allocation problems of hard real-time systems with dynamic constraint programming},
booktitle      = {14th International Conference on Real-Time and Network Systems (RTNS06)},
year           = 2006,
month          = may,
address        = {Poitiers, France},
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/hladik-RTNS06.pdf},
taux           = {70/100},
}

Émilie Grellier, Pierre Dejax, Narendra Jussien, Zhiqiang Lu

"A Column Generation Model and Constraint Programming Techniques for solving an Inventory Routing Problem in Mixed Flows" , Third international workshop on freight transportation and logistics (Odysseus 2006), 2006

, article [pdf, 97 KB]

@InProceedings{grellier-irp-odysseus,
author         = {{\'E}milie Grellier and Pierre Dejax and Narendra Jussien and Zhiqiang Lu},
title          = {A Column Generation Model and Constraint Programming Techniques for solving an Inventory Routing Problem in Mixed Flows},
booktitle      = {Third international workshop on freight transportation and logistics (Odysseus 2006)},
year           = 2006,
address        = {Altea, Spain},
month          = may,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/grellier-ODYSSEUS06.pdf},
}

Émilie Grellier, Pierre Dejax, Narendra Jussien, Zhiqiang Lu

"Vehicle routing problem in mixed flows for reverse logistics: a modeling framework" , International Conference on Information Systems, Logistics, and Supply Chain (ILS 2006), 2006

, article [pdf, 204 KB]

@InProceedings{grellier-vrp-ils,
author         = {{\'E}milie Grellier and Pierre Dejax and Narendra Jussien and Zhiqiang Lu},
title          = {Vehicle routing problem in mixed flows for reverse logistics: a modeling framework},
booktitle      = {International Conference on Information Systems, Logistics, and Supply Chain (ILS 2006)},
year           = 2006,
address        = {Lyon, France},
month          = may,
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/grellier-ILS06.pdf},
}

Émilie Grellier, Pierre Dejax, Narendra Jussien, Zhiqiang Lu

"Tournées de collectes et livraisons dans le cadre de la logistique inverse" , 7ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2006), 2006

@InProceedings{grellier-tournees,
author         = {{\'E}milie Grellier and Pierre Dejax and Narendra Jussien and Zhiqiang Lu},
title          = {Tourn{\'e}es de collectes et livraisons dans le cadre de la logistique inverse},
booktitle      = {7{\`e}me congr{\`e}s de la Soci{\'e}t{\'e} Fran\c{c}aise de Recherche Op{\'e}rationnelle et d'Aide {\`a} la D{\'e}cision (ROADEF 2006)},
year           = 2006,
address        = {Lille, France},
month          = feb,
url            = {http://www.emn.fr/jussien/publications/grellier-ROADEF06.pdf}, 
kind           = {MNSA},
}

Philippe Baptiste, Narendra Jussien, Pierre Lopez

"Special Issue Constraint Programming" , RAIRO Operations Research, EDP Science, Special issue from a selection of papers presented in the OR/CP research group, 2005

@Book{baptiste-jussien-lopez-rairo-ppcro,
editor         = {Philippe Baptiste and Narendra Jussien and Pierre Lopez},
title          = {Special Issue Constraint Programming},
publisher      = {EDP Science},
year           = 2005,
series         = {RAIRO Operations Research},
note           = {Special issue from a selection of papers presented in the OR/CP research group},
issn           = {0399 0559},
kind           = {LEDL},
}

Pierre-Emmanuel Hladik, Hadrien Cambazard, Anne-Marie Déplanche, Narendra Jussien

"Dynamic constraint programming for solving hard real-time allocation problems" , IRCCyN, technical report, no. 2005-7, 2005

, article [pdf, 354 KB]

@TechReport{hladik-dynamic-rr,
author         = {Pierre-Emmanuel Hladik and Hadrien Cambazard and Anne-Marie D{\'e}planche and Narendra Jussien},
title          = {Dynamic constraint programming for solving hard real-time allocation problems},
institution    = {IRCCyN},
year           = 2005,
number         = {2005-7},
kind           = {RR},
type           = {Research Report},
url            = {http://www.emn.fr/jussien/publications/hladik-RR-IRCCYN-2005-7.pdf},
}

Pierre-Emmanuel Hladik, Hadrien Cambazard, Anne-Marie Déplanche, Narendra Jussien

"How to solve allocation problems with constraint programming" , Work In Progress of the 17th Euromicro conference on real time systems (ECRTS'05), pp. 25-28, IRISA, Rennes, France, 2005

, article [pdf, 204 KB]

@InProceedings{hladik-allocation-euromicro,
author         = {Pierre-Emmanuel Hladik and Hadrien Cambazard and Anne-Marie D{\'e}planche and Narendra Jussien},
title          = {How to solve allocation problems with constraint programming},
booktitle      = {Work In Progress of the 17th Euromicro conference on real time systems (ECRTS'05)},
year           = 2005,
month          = jul,
address        = {Palma de Mallorca, Spain},
kind           = {MISA},
pages          = {25--28},
editor         = {Isabelle Puaut},
publisher      = {IRISA, Rennes, France},
url            = {http://www.emn.fr/jussien/publications/hladik-ECRTS05.pdf},
}

Narendra Jussien

"Explanation-based constraint programming" , Second Franco-Japanese workshop on Constraint Programming (FJCP 2005), 2005

abstract

@InProceedings{jussien-explanations-fjcp,
author = {Narendra Jussien},
title = {Explanation-based constraint programming},
booktitle = {Second Franco-Japanese workshop on Constraint Programming (FJCP 2005)},
year = 2005,
address = {Le Croisic, France},
month = nov,
kind = {MIADR},
abstract = {Constraint programming has proven its interest and efficiency in various domains: combinatorial optimization, finance, diagnostics, design, biology, geometrical problems, etc. Nevertheless, several limitations or strong points remain: designing generic and stable algoritms, handling dynamic problems, giving access to any engineer to concepts and tools of constraint programming, etc.

For a few years, we have claimed that the notion of explanation for constraint programming is valuable beacause it can, we showed it, efficiently answer to some those limitations. Explanations can be considered as a limited explicit trace of the constraints solver's behavior. Our work brought us not only to develop theoretical aspects of explanation and to study their computation and implementation aspects (especially through the PaLM system: an explanation-based constraint solver) but also to study their different possible use.

Indeed, explanations can be used in several situations. An obvious and direct usage consists in using them to inform the user about the current statge of computation. Such an information is useful when tackling dynamic problems leading to an incremental (both for constraint addition and removal) constraitn solver.

Other applications rely in modifiying the intimate behavior of classical search algorithms. Indeed, explanations may be used at every step of constraint solving: to guide search, to recover from a dead-end, etc. We believe that such a usage may represent a new evolution of constraint programming that we called e-constraints (explanation-based constraint programming).

In this talk, we will not only present our main results but also our current research topics.},
}

Hadrien Cambazard, Narendra Jussien

"Integrating Benders decomposition within Constraint Programming" , Principles and Practice of Constraint Programming (CP 2005), Lecture Notes in Computer Science, no. 3709, pp. 752-756, Springer-Verlag, Short paper, 2005

, article [pdf, 150 KB]

@InProceedings{cambazard-benders,
author         = {Hadrien Cambazard and Narendra Jussien},
title          = {Integrating Benders decomposition within Constraint Programming},
series         = {Lecture Notes in Computer Science},
booktitle      = {Principles and Practice of Constraint Programming (CP 2005)},
publisher      = {Springer-Verlag},
number         = 3709, 
pages          = {752--756},
  year         = 2005,
  month        = sep,
  address      = {Sitges, Spain},
  kind         = {MISA},
url            = {http://www.emn.fr/jussien/publications/cambazard-CP05.pdf},
note           = {Short paper},
}

Hadrien Cambazard, Fabien Demazeau, Narendra Jussien, Philippe David

"Interactively solving school timetabling problems using extensions of constraint programming" , Practice and Theory of Automated Timetabling V, Lecture Notes in Computer Science, no. 3616, pp. 190-207, Springer-Verlag, 2005

abstract, article [pdf, 347 KB]

@InProceedings{cambazard-timetabling-lncs,
author         = {Hadrien Cambazard and Fabien Demazeau and Narendra Jussien and Philippe David},
title          = {Interactively solving school timetabling problems using extensions of constraint programming},
editor         = {Edmund~K. Burke and Michael Trick},
year           = 2005,
number         = 3616,
booktitle      = {Practice and Theory of Automated Timetabling V},
publisher      = {Springer-Verlag},
kind           = {CDL},
pages          = {190--207},
isbn           = {3-540-30705-2},
url            = {http://www.emn.fr/jussien/publications/cambazard-LNCS05.pdf},
series         = {Lecture Notes in Computer Science},
abstract       = {Timetabling problems have been frequently studied due to their wide range of applications.
However, they are often solved manually because of the lack of
appropriate computer tools. Although many approaches mainly based on local search or
constraint programming seem to have been quite successful in recent years, they are often
highly dedicated to specific problems and encounter difficulties to take the dynamic
and over-constrained nature of such problems.  
We were confronted with such an over-constrained and dynamic problem in our institution. 
This paper deals with a timetabling system based on constraint programming with the use of explanations to offer a dynamic
behaviour and to allow automatic relaxations of constraints. Our tool has successfully answered
the needs of the current planner by providing solutions in a few minutes instead of a week of manual design.
We present in this paper the techniques used, the results obtained and a discussion on the effects
of the automation of the timetabling process.},
}

Narendra Jussien

"Programmation par contraintes avec explications : études et perspectives" , Séminaire 68NQRT de l'IRISA, 2005

@Misc{jussien-irisa05,
author        = {Narendra Jussien},
title         = {Programmation par contraintes avec explications~: {\'e}tudes et perspectives},
howpublished  = {S{\'e}minaire 68NQRT de l'IRISA},
month         = may,
year          = 2005,
kind          = {DIVERS},
}

Hadrien Cambazard, Narendra Jussien

"Benders decomposition in Constraint Programming" , CSCLP'05: Joint Annual Workshop of ERCIM/CoLogNet on Constraint Solving and Constraint Logic Programming, 2005

abstract, article [pdf, 214 KB]

@InProceedings{cambazard-benders-ercim,
author         = {Hadrien Cambazard and Narendra Jussien},
title          = {Benders decomposition in Constraint Programming},
booktitle      = {CSCLP'05: Joint Annual Workshop of ERCIM/CoLogNet on Constraint Solving and Constraint Logic Programming},
year           = 2005,
address        = {Uppsala, Sweden},
month          = jun,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/cambazard-CSCLP05.pdf},
abstract       = {Recent work have exhibited specific structure among combinatorial problem instances that could be used to speed up search or to help users understand the dynamic and static intimate structure of the problem being solved.
Several Operations Research approaches apply decomposition or relaxation strategies upon such a structure identified within a given problem. This paper presents how Benders decomposition could be adapted to constraint programming when specific relationships between variables are exhibited. It discusses the way a decomposition framework could be embedded in constraint solvers, taking advantage of structures for a non expert user in a generic way. To achieve the interaction between structures, it explores the possibility of deriving logic Benders cuts using an explanation based framework for Constraint Programming.},
}

Gérard Verfaillie, Narendra Jussien

"Constraint solving in uncertain and dynamic environments - a survey" , in: "Constraints", vol. 10, no. 3, pp. 253-281, Springer Verlag, 2005

abstract, article [pdf, 331 KB]

@Article{verfaillie-dynamic,
 author         = {G{\'e}rard Verfaillie and Narendra Jussien},
 title          = {Constraint solving in uncertain and dynamic environments -- a survey},
 journal        = {Constraints},
 publisher      = {Springer Verlag},
 year           = 2005,
 volume         = 10, 
 number         = 3, 
 pages          = {253--281},
 kind           = {RIAS},
 url            = {http://www.emn.fr/jussien/publications/verfaillie-CONSTRAINTS05.pdf},
 abstract       = { This article follows a tutorial, given by the authors on dynamic constraint solving at CP 2003 (Ninth International Conference on Principles and Practice of Constraint Programming) in Kinsale, Ireland.

It aims at offering an overview of the main approaches and techniques that have been proposed in the domain of constraint satisfaction to deal with uncertain and dynamic environments. }
}

Hadrien Cambazard, Narendra Jussien

"Des explications pour reconna\^\itre et exploiter les structures cachées" , Premières Journées Francophones de Programmation par Contraintes (JFPC'05), pp. 403-412, 2005

abstract, article [pdf, 733 KB]

@InProceedings{cambazard-structures-cachees,
author         = {Hadrien Cambazard and Narendra Jussien},
title          = {Des explications pour reconna{\^\i}tre et exploiter les structures cach{\'e}es},
booktitle      = {Premi{\`e}res Journ{\'e}es Francophones de Programmation par Contraintes (JFPC'05)},
year           = 2005,
address        = {Lens, France},
month          = jun,
pages          = {403--412},
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/cambazard-JFPC05.pdf},
abstract       = {L'identification de structures propres ˆ un problme
est souvent une Žtape clef pour la conception d'heuristiques
de recherche comme la comprŽhension de la complexitŽ du problme.
De nombreuses approches en Recherche OpŽrationnelle emploient des stratŽgies de
relaxations ou dŽcompositions ds lors que certaines structures idoines
ont ŽtŽ identifiŽes. L'Žtape suivante est la conception
d'algorithmes de rŽsolution qui puisse intŽgrer ˆ la volŽe, pendant la
rŽsolution, ce type d'information. Cet article propose d'utiliser un
solveur de contraintes ˆ base d'explications pour collecter
de l'information pertinente sur les structures dynamiques
et statiques inhŽrentes au problme. Par ailleurs,
la reconnaissance de relations spŽcifiques entre les variables
suggre l'adaptation d'algorithmes dŽdiŽs issus
du monde de la Recherche OpŽrationnelle au contexte de
la programmation par contraintes. Une telle adaptation
est discutŽe dans le cadre de la dŽcomposition de Benders.}
}

Guillaume Rochart, Narendra Jussien

"Implémenter des contraintes globales expliquées" , Premières Journées Francophones de Programmation par Contraintes (JFPC'05), pp. 393-402, 2005

abstract, article [pdf, 210 KB]

@InProceedings{rochart-globales-expliquees,
author         = {Guillaume Rochart and Narendra Jussien},
title          = {Impl{\'e}menter des contraintes globales expliqu{\'e}es},
booktitle      = {Premi{\`e}res Journ{\'e}es Francophones de Programmation par Contraintes (JFPC'05)},
year           = 2005,
address        = {Lens, France},
month          = jun,
pages          = {393--402},
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/rochart-JFPC05.pdf},
abstract       = {Modifier le comportement d'un solveur de contraintes pour lui ajouter de nouvelles capacitŽs est souvent une t‰che complexe : l'optimisation extrme, fruit d'une expŽrience de dŽveloppement de plusieurs annŽes, du c\oe{}ur de propagation et des algorithmes de filtrage rend cette opŽration particulirement dŽlicate si on souhaite maintenir le niveau de qualitŽ atteint par l'outil. Ds lors, cette difficultŽ constitue bien souvent un frein pour mettre en place au sein du solveur de nouvelles techniques ou outils (explications, trace prŽcise, etc.). 

 Nous montrons dans cet article les problmes posŽs par l'ajout d'explications dans des contraintes globales et proposons deux nouvelles mŽthodes pour ajouter des contraintes globales expliquŽes dans un solveur~: l'une basŽe sur l'utilisation d'un cadre gŽnŽrique de description des contraintes globale, l'autre utilisant les possibilitŽ de la programmation par aspects. }
}

Narendra Jussien

"Explanation-based constraint programming" , Cork Constraint Computation Center seminar, 2005

abstract

@Misc{jussien-4C05,
author = {Narendra Jussien},
title = {Explanation-based constraint programming},
howpublished = {Cork Constraint Computation Center seminar},
address = {Cork, Ireland},
month = apr,
year = 2005,
kind = {DIVERS},
abstract = {Constraint programming has proven its interest and efficiency in various domains: combinatorial optimization, finance, diagnostics, design, biology, geometrical problems, etc. Nevertheless, several limitations or strong points remain: designing generic and stable algoritms, handling dynamic problems, giving access to any engineer to concepts and tools of constraint programming, etc.

In this talk, we will not only present our main results but also our current research topics.}
}

Hadrien Cambazard, Narendra Jussien

"Identifying and exploiting problem structures using explanation-based constraint programming" , International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR'05), Lecture Notes in Computer Science, vol. 3524, pp. 94-109, Springer Verlag, 2005

abstract, article [pdf, 429 KB]

@InProceedings{cambazard-identifying,
 author         = {Hadrien Cambazard and Narendra Jussien},
 title          = {Identifying and exploiting problem structures using explanation-based constraint programming},
 booktitle      = {International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR'05)},
 year           = 2005,
 editor         = {Roman Bart{\'a}k and Michela Milano},
 series         = {Lecture Notes in Computer Science},
 volume         = {3524},
 pages          = {94--109},
 address        = {Prague, Czech Republic},
 month          = may,
 kind           = {MISA},
 publisher      = {Springer Verlag},
 url            = {http://www.emn.fr/jussien/publications/cambazard-CPAIOR05.pdf},
 taux           = {26/98},
 abstract       = {Recent work have exhibited specific structure among combinatorial problem
instances that could be used to speed up search or to help users understand
the dynamic and static intimate structure of the problem being solved.
Several Operations Research approaches apply decomposition or relaxation
strategies upon such a structure identified within a given problem. The
next step is to design algorithms that adaptatively integrate that kind of
information during search. We claim in this paper, inspired by previous work
on impact-based search strategies for constraint programming, that
using an explanation-based constraint solver may lead to collect invaluable
information on the intimate dynamic and static structure of a problem
instance. We define several impact graphs to be used to design generic
search guiding techniques and to identify hidden structures of instances.
Finally, we discuss how dedicated OR solving strategies (such as Benders
decomposition) could be adapted to constraint programming when specific
relationships between variables are exhibited.},
}

Narendra Jussien

"Constraint Programming for Software Engineering" , Fifth Congress of Logic applied to Technology (LAPTEC'05), 2005

abstract, article [pdf, 46 KB]

@InProceedings{jussien-software,
  author       = {Narendra Jussien},
  title        = {Constraint Programming for Software Engineering},
  booktitle    = {Fifth Congress of Logic applied to Technology (LAPTEC'05)},
  year         = 2005,
  address      = {Himeji, Japan},
  month        = apr,
  kind         = {MISA},
url            = {http://www.emn.fr/jussien/publications/jussien-LAPTEC05.pdf},
abstract       = {Constraint programming is a research topic at the crossroads of artificial intelligence, operations research and numerical analysis. This rather new research field as now proved useful for solving complex combinatorial problems in decision making processes. New applications arise now and particularly in software engineering. In this paper, we show the interest and the perspectives in using constraint programming in this technological field through several examples (including identification and correction of degraded design patterns in object oriented software, implementation of an application in an anytime context, design of hard real time systems).},
}

Mohammad Ghoniem, Hadrien Cambazard, Jean-Daniel Fekete, Narendra Jussien

"Peeking in Solver Strategies Using Explanations - Visualization of Dynamic Graphs for Constraint Programming" , ACM symposium on Software Visualization (SOFTVIS'05), 2005

, article [pdf, 2066 KB]

@InProceedings{ghoniem-peeking,
  author       = {Mohammad Ghoniem and Hadrien Cambazard and Jean-Daniel Fekete and Narendra Jussien},
  title        = {Peeking in Solver Strategies Using Explanations -- Visualization of Dynamic Graphs for Constraint Programming},
  booktitle    = {ACM symposium on Software Visualization (SOFTVIS'05)},
  year         = 2005,
  address      = {Saint-Louis, MO, USA},
  month        = may,
url            = {http://www.emn.fr/jussien/publications/ghoniem-SOFTVIS05.pdf},
  kind         = {MISA},
  taux         = {20/81},
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Ordonnancement dynamique de projet à contraintes de ressources" , Flexibilité et Robustesse en Ordonnancement, pp. 325-344, Hermès, 2005

, article []

@InCollection{gueret-robustesse,
author         = {Abdallah Elkhyari and Christelle Gu\'eret and Narendra Jussien},
title          = {Ordonnancement dynamique de projet {\`a} contraintes de ressources},
chapter        = {15},
pages          = {325--344},
editor         = {Jean-Charles Billaut and Aziz Moukrim and \'Eric Sanlaville},
booktitle      = {Flexibilit\'e et Robustesse en Ordonnancement},
year           = 2005,
publisher      = {Herm\`es},
month          = mar, 
isbn           = {2746210282}, 
kind           = {CDL},
url            = {http://www.amazon.fr/gp/product/2746210282?ie=UTF8&tag=pagespersonne-21&linkCode=as2&camp=1642&creative=6746&creativeASIN=2746210282},
}

Narendra Jussien

"Programmation par contraintes avec explications : études et perspectives" , Séminaire du Laboratoire d'Informatique et de Micro-électronique de Montpellier, 2005

@Misc{jussien-lirmm05,
author        = {Narendra Jussien},
title         = {Programmation par contraintes avec explications~: {\'e}tudes et perspectives},
howpublished  = {S{\'e}minaire du Laboratoire d'Informatique et de Micro-{\'e}lectronique de Montpellier},
month         = feb,
year          = 2005,
kind          = {DIVERS},
}

Narendra Jussien

"Dixièmes Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'04)" , Université d'Angers, 2004

abstract, article [zip]

@Proceedings{jnpc04,
editor         = {Narendra Jussien},
title      = {Dixi{\`e}mes Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'04)},
year           = 2004,
address        = {Angers, France},
month          = jun,
organization   = {Universit{\'e} d'Angers},
url            = {http://www.info.univ-angers.fr/jfplc2004/docs/jnpc2004-actes.zip},
kind           = {LEDL},
abstract       = {Ces actes comprennent les contributions s{\'e}lectionn{\'e}es pour les JNPC 2004, les
dixi{\`e}mes d'une s{\'e}rie commenc{\'e}e {\`a} Montpellier en 1994. Cette ann{\'e}e sur un total
de 33 soumissions effectives, 22 ont {\'e}t{\'e} s{\'e}lectionn{\'e}es pour pr{\'e}sentation longue
et 2 pour la session jeunes chercheurs. La qualit{\'e} g{\'e}n{\'e}rale des soumissions a {\'e}t{\'e}
appr{\'e}ci{\'e}e par chacun des relecteurs.
Le comit{\'e} de programme a particuli{\`e}rement veill{\'e} {\`a} {\'e}quilibrer les aspects
conf{\'e}rence s{\'e}lective et r{\'e}union de travail de la communaut{\'e} nationale des JNPC.
Le programme qui en r{\'e}sulte offre ainsi l'opportunit{\'e} de l'int{\'e}gration des jeunes
chercheurs dans notre communaut{\'e} et devrait donner lieu {\`a} des discussions fer-
tiles.
Le comit{\'e} de programme a saisi l'opportunit{\'e} de la pr{\'e}sence des JNPC {\`a}
Angers pour proposer un expos{\'e} invit{\'e} {\`a} une personnalit{\'e} de la communaut{\'e} Re-
cherche Op{\'e}rationnelle que nous avons peu l'habitude d'entendre : \'Eric Pinson,
professeur {\`a} l'Institut de Math{\'e}matiques Appliqu{\'e}es. Celui-ci a pr{\'e}vu de nous
offrir un panorama et des perspectives de rapprochement entre nos deux commu-
naut{\'e}s qui, longtemps, se sont observ{\'e}es de (trop) loin, avec parfois un peu de
circonspection.
Cette ann{\'e}e encore la frontiµere entre les JNPC et les JFPLC est apparue trµes
t{\'e}nue tant au moment des soumissions d'articles qu'{\`a} la planification des expos{\'e}s.
Le nombre de sessions communes en est la preuve. La question de la fusion ou
du rapprochement des deux conf{\'e}rences et communaut{\'e}s devrait conna{\^\i}tre cette
ann{\'e}e enfin une avanc{\'e}e significative. En effet, Fr{\'e}d{\'e}ric Benhamou et moi-m{\^e}me,
mandat{\'e}s respectivement par l'AFPLC et les sages des JNPC, avons travaill{\'e} {\`a}
la cr{\'e}ation d'une nouvelle association dont les statuts et le rµeglement int{\'e}rieur
seront pr{\'e}sent{\'e}s et discut{\'e}s lors des journ{\'e}es. Nous esp{\'e}rons ainsi que la fusion
longtemps remise sera effective et que les journ{\'e}es de notre communaut{\'e} auront
lieu l'ann{\'e}e prochaine sous leurs nouveaux atours.},
}

Étienne Gaudin, Narendra Jussien, Guillaume Rochart

"Implementing explained global constraints" , CP04 Workshop on Constraint Propagation and Implementation (CPAI'04), pp. 61-76, 2004

, article [pdf, 176 KB]

@InProceedings{rochart-implementing,
author         = {{\'E}tienne Gaudin and Narendra Jussien and Guillaume Rochart},
title          = {Implementing explained global constraints},
booktitle      = {CP04 Workshop on Constraint Propagation and Implementation (CPAI'04)},
year           = 2004,
address        = {Toronto, Canada},
month          = sep,
pages          = {61--76},
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/rochart-CPAI04.pdf},
}

Guillaume Rochart, Éric Monfroy, Narendra Jussien

"MINLP Problems and Explanation-based Constraint Programming" , CP04 Fourth Workshop on Cooperative Solvers in Constraint Programming (COSOLV'04), 2004

, article [pdf, 164 KB]

@InProceedings{rochart-minlp,
author         = {Guillaume Rochart and {\'E}ric Monfroy and Narendra Jussien},
title          = {MINLP Problems and Explanation-based Constraint Programming},
booktitle      = {CP04 Fourth Workshop on Cooperative Solvers in Constraint Programming (COSOLV'04)},
year           = 2004,
address        = {Toronto, Canada},
month          = sep,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/rochart-COSOLV04.pdf},
}

Narendra Jussien

"Dynamic constraint solving" , Séminaire du National Institute for Informatics (Tokyo, Japan), 2004

@Misc{jussien-nii04,
author        = {Narendra Jussien},
title         = {Dynamic constraint solving},
howpublished  = {S{\'e}minaire du National Institute for Informatics (Tokyo, Japan)},
month         = may,
year          = 2004,
kind          = {DIVERS},
}

Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie Déplanche, Narendra Jussien, Yvon Trinquet

"Decomposition and learning for a real time task allocation problem" , Principles and Practice of Constraint Programming (CP 2004), Lecture Notes in Computer Science, vol. 3258, pp. 153-167, Springer-Verlag, 2004

abstract, article [pdf, 268 KB]

@InProceedings{cambazard-decomposition,
author         = {Hadrien Cambazard and Pierre-Emmanuel Hladik and Anne-Marie D{\'e}planche and Narendra Jussien and Yvon Trinquet},
title          = {Decomposition and learning for a real time task allocation problem},
series         = {Lecture Notes in Computer Science},
booktitle      = {Principles and Practice of Constraint Programming (CP 2004)},
publisher      = {Springer-Verlag},
  year         = 2004,
  volume       = {3258},
  month        = sep,
pages          = {153--167},
url            = {http://www.emn.fr/jussien/publications/cambazard-CP04.pdf},
  address      = {Toronto, Canada},
  kind         = {MISA},
abstract       = {We present a cooperation technique using an accurate management of nogoods to solve a hard real-time problem which consists in assigning periodic tasks to processors in the context of fixed priorities preemptive scheduling. The problem is to be solved off-line and our solving strategy is related to the logic based Benders decomposition. A master problem is solved using constraint programming whereas subproblems are solved with schedulability analysis techniques coupled with an ad hoc nogood computation algorithm. Constraints and nogoods are learnt during the process and play a role close to Benders cuts.},
}

Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie Déplanche, Narendra Jussien, Yvon Trinquet

"Decomposition and learning for a hard real time task allocation problem" , École des Mines de Nantes, technical report, no. 04-04-INFO, 2004

abstract, article [pdf, 275 KB]

@TechReport{cambazard-decomposition-rr,
author         = {Hadrien Cambazard and Pierre-Emmanuel Hladik and Anne-Marie D{\'e}planche and Narendra Jussien and Yvon Trinquet},
title          = {Decomposition and learning for a hard real time task allocation problem},
institution    = {\'Ecole des Mines de Nantes},
year           = 2004,
number         = {04-04-INFO},
address        = {Nantes, France},
url            = {http://www.emn.fr/jussien/publications/cambazard-RR0404.pdf},
kind           = {RR},
type           = {Research Report},
abstract       = {We present an instance of logical Benders Decomposition to solve a  hard real-time system which consists in assigning periodic tasks in
 the context of fixed priorities preemptive scheduling. The master
 problem is solved using constraint programming whereas sub-problems
 are solved with schedulability analysis techniques coupled with an
 adhoc conflict computation algorithm: QuickXplain. Constraints and
 nogoods are learnt during the process and play a role close to Benders cuts.}
}

Laurent Breton, Narendra Jussien

"Un CSP comme comportement d'agent. Application à la résolution d'équations en physique des milieux granulaires" , in: "JEDAI: Journal Électronique d'Intelligence Artificielle", vol. 3, no. 26, 2004

abstract, article [pdf, 276 KB]

@Article{breton-agents-jedai,
author         = {Laurent Breton and Narendra Jussien},
title          = {Un {CSP} comme comportement d'agent. {A}pplication {\`a} la r{\'e}solution d'{\'e}quations en physique des milieux granulaires},
journal        = {JEDAI: Journal \'Electronique d'Intelligence Artificielle},
year           = 2004,
kind           = {RNAS},
volume         = 3,
number         = 26,
url            = {http://www.emn.fr/jussien/publications/breton-JEDAI04.pdf},
abstract       = {En physique des milieux granulaires, des m{\'e}thodes de simulations
num{\'e}riques sont utilis{\'e}es notamment pour tenter de comprendre la
connexion entre les grains et les structures m{\'e}caniques macroscopiques
dans le tas. Nous avons propos{\'e} une mod{\'e}lisation multi-agent originale
qui permet de r{\'e}soudre des tas de sable bidimensionnels {\`a} l'{\'e}quilibre
statique. Mais, le caract{\`e}re stochastique de la recherche locale de
solutions d'{\'e}quilibre pose le probl{\`e}me de la couverture de l'espace des
solutions par cet algorithme. La r{\'e}solution de ce probl{\`e}me par une
approche purement CSP se r{\'e}v{\`e}le difficile du fait de la taille
gigantesque du probl{\`e}me {\`a} traiter. Nous proposons donc de mettre en
oeuvre des techniques de CSP comme comportements de r{\'e}solution local de
l'{\'e}quilibre d'agents-grains.},
}

Hadrien Cambazard, Fabien Demazeau, Narendra Jussien, Philippe David

"Interactively solving school timetabling problems using extensions of constraint programming" , Practice and Theory of Automated Timetabling (PATAT 2004), pp. 107-124, 2004

abstract, article [pdf, 336 KB]

@InProceedings{cambazard-timetabling,
author         = {Hadrien Cambazard and Fabien Demazeau and Narendra Jussien and Philippe David},
title          = {Interactively solving school timetabling problems using extensions of constraint programming},
booktitle      = {Practice and Theory of Automated Timetabling (PATAT 2004)},
year           = 2004,
editor         = {M.~Trick and E.~K.~Burke},
address        = {Pittsburgh, PA USA},
month          = aug,
url            = {http://www.emn.fr/jussien/publications/cambazard-PATAT04.pdf},
pages          = {107--124},
kind           = {MISA},
abstract       = {Timetabling problems have been frequently studied
                  due to their wide range of applications. However,
                  they are often solved manually because of the lack
                  of appropriate computer tools. Although many
                  approaches mainly based on local search or
                  constraint programming seem to have been quite
                  successful in recent years, they are often highly
                  dedicated to specific problems and encounter
                  difficulties to take the dynamic and
                  over-constrained nature of such problems. We were
                  confronted with a such over-constrained and dynamic
                  problem in our institution. This paper deals with a
                  timetabling system based on constraint programming
                  with the use of explanations to offer a dynamic
                  behaviour and to allow an automatic relaxation of
                  constraints. Our tool has successfully answered the
                  needs of the planner by providing solutions in a few
                  minutes instead of a week of manual computation. We
                  will present in this paper the techniques used, the
                  results obtained and a discussion on the effect of
                  the automation of the timetabling process.},
}

Étienne Gaudin, Narendra Jussien, Guillaume Rochart

"Explained global constraints at work" , École des Mines de Nantes, technical report, no. 04-03-INFO, 2004

, article [pdf, 182 KB]

@TechReport{gaudin-explained-rr,
author         = {{\'E}tienne Gaudin and Narendra Jussien and Guillaume Rochart},
title          = {Explained global constraints at work},
institution    = {\'Ecole des Mines de Nantes},
year           = 2004,
number         = {04-03-INFO},
address        = {Nantes, France},
url            = {http://www.emn.fr/jussien/publications/gaudin-RR0403.pdf},
kind           = {RR},
type           = {Research Report},
abstract       = {}
}

Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie Déplanche, Narendra Jussien, Yvon Trinquet

"Décomposition et apprentissage pour un problème d'allocation de tâches temps-réel" , 10e Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'04), pp. 123-138, 2004

abstract, article [pdf, 310 KB]

@InProceedings{cambazard-temps-reel,
author         = {Hadrien Cambazard and Pierre-Emmanuel Hladik and Anne-Marie D{\'e}planche and Narendra Jussien and Yvon Trinquet},
title          = {D\'ecomposition et apprentissage pour un probl\`eme d'allocation de t{\^a}ches temps-r\'eel},
booktitle      = {10e Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'04)},
year           = 2004,
address        = {Angers, France},
month          = jun,
pages          = {123--138},
url            = {http://www.emn.fr/jussien/publications/cambazard-JNPC04.pdf},
kind           = {MNSA},
abstract       = {La d{\'e}composition de Benders a {\'e}t{\'e} utilis{\'e}e avec succ{\`e}s pour de nombreuses
probl{\'e}matiques en Recherche Op{\'e}rationnelle. Nous pr{\'e}sentons ici, la mise en
oeuvre d'une technique de coop{\'e}ration fond{\'e}e sur une g{\'e}n{\'e}ralisation du cadre
classique de la d{\'e}composition de Benders et appliqu{\'e}e {\`a} la r{\'e}solution d'un
probl{\`e}me d'allocation de t{\^a}ches temps r{\'e}el (ordonnancement pr{\'e}emptif {\`a}
priorit{\'e}es fixes pour des t{\^a}ches p{\'e}riodiques). Un probl{\`e}me ma{\^\i}tre, r{\'e}solu
par programmation par contraintes coop{\`e}re avec un sous-probl{\`e}me analytique.
Celui-ci est trait{\'e} par des techniques issues des travaux de la communaut{\'e}
temps-r{\'e}el et coupl{\'e}es avec un algorithme adhoc de d{\'e}tection de conflits :
QuickXplain. Les contraintes et nogoods appris au cours de la recherche
jouent un r{\^o}le similaire aux coupes de Benders.},
}

Guillaume Rochart, Narendra Jussien

"Contraintes de flot et explications" , 10e Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'04), pp. 369-372, 2004

abstract, article [pdf, 79 KB]

@InProceedings{rochart-flot,
author         = {Guillaume Rochart and Narendra Jussien},
title          = {Contraintes de flot et explications},
booktitle      = {10e Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'04)},
year           = 2004,
address        = {Angers, France},
month          = jun,
pages          = {369--372},
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/rochart-JNPC04.pdf},
abstract       = {Nous pr{\'e}sentons dans cet article comment fournir des explications pour des contraintes globales bas{\'e}es sur le flot.
Nous {\'e}tudions notamment une contrainte de maintien d'un flot dans un r{\'e}seau
et les explications en ce qui concerne le flot maximal, minimal ainsi
que l'existence d'un flot compatible.
Apr{\`e}s un parall{\`e}le avec les explications pour les contraintes all_diff
et gcc, nous proposons quelques r{\'e}sultats mettant en avant le gain en
retour arri{\`e}re de cette m{\'e}thode et tentons d'{\'e}valuer le gain en temps
que de telles explications peuvent apporter.},
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Constraint programming for dynamic scheduling problems" , ISS'04 International Scheduling Symposium, pp. 84-89, Japan Society of Mechanical Engineers, 2004

, article [pdf, 52 KB]

@InProceedings{elkhyari-programming-dynamic,
author         = {Abdallah Elkhyari and Christelle Gu\'eret and Narendra Jussien},
title          = {Constraint programming for dynamic scheduling problems},
booktitle      = {ISS'04 International Scheduling Symposium},
year           = 2004,
editor         = {Hiroshi Kise},
publisher      = {Japan Society of Mechanical Engineers},
address        = {Awaji, Hyogo, Japan},
month          = may,
pages          = {84--89},
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/elkhyari-ISS04.pdf},
}

Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie Déplanche, Narendra Jussien, Yvon Trinquet

"Decomposition and learning for a hard real-time task allocating problem" , CORS/INFORMS Joint International Meeting, 2004

abstract

@InProceedings{cambazard-placement-informs,
author         = {Hadrien Cambazard and Pierre-Emmanuel Hladik and Anne-Marie D{\'e}planche and Narendra Jussien and Yvon Trinquet},
title          = {Decomposition and learning for a hard real-time task allocating problem},
booktitle      = {CORS/INFORMS Joint International Meeting},
year           = 2004,
address        = {Banff, Alberta, Canada},
month          = {may},
kind           = {MISA},
abstract       = {We present an instance of logical Benders Decomposition to solve a  hard real-time system which consists in assigning periodic tasks in
 the context of fixed priorities preemptive scheduling. The master
 problem is solved using constraint programming whereas sub-problems
 are solved with schedulability analysis techniques coupled with an
 adhoc conflict computation algorithm: QuickXplain. Constraints and
 nogoods are learnt during the process and play a role close to Benders cuts.},
}

Guillaume Rochart, Narendra Jussien

"Une contrainte \textttstretch expliquée" , in: "JEDAI: Journal Électronique d'Intelligence Artificielle", vol. 3, no. 31, 2004

abstract, article [pdf, 218 KB]

@Article{rochart-stretch-jedai,
author         = {Guillaume Rochart and Narendra Jussien},
title          = {Une contrainte \texttt{stretch} expliqu{\'e}e},
journal        = {JEDAI: Journal \'Electronique d'Intelligence Artificielle},
year           = 2004,
kind           = {RNAS},
url            = {http://www.emn.fr/jussien/publications/rochart-JEDAI04.pdf},
volume         = 3,
number         = 31,
abstract       = {Nous montrons dans cet article comment {\'e}tendre une contrainte
globale, stretch, pour l'utiliser dans un contexte expliqu{\'e}. Ceci se traduit
notamment par la production d'explications pr{\'e}cises pour chacune des
d{\'e}cisions prises lors du filtrage. Les exp{\'e}rimentations montrent une
am{\'e}lioration notable de la r{\'e}solution de probl{\`e}mes mettant en oeuvre une
telle contrainte.},
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Stable solutions for dynamic project scheduling problems" , PMS'04 International Workshop on Project Management and Scheduling, pp. 380-384, 2004

, article [pdf, 121 KB]

@InProceedings{elkhyari-stable,
author         = {Abdallah Elkhyari and Christelle Gu\'eret and Narendra Jussien},
title          = {Stable solutions for dynamic project scheduling problems},
booktitle      = {PMS'04 International Workshop on Project Management and Scheduling},
year           = 2004,
address        = {Nancy, France},
month          = apr,
pages          = {380--384},
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/elkhyari-PMS04.pdf},
}

Narendra Jussien, François Laburthe

"Hybrid Optimization Techniques" , Annals of Operations Research, vol. 130, Kluwer, Special Issue following CP-AI-OR'02, 2004

@Book{jussien-laburthe-aor-cpaior,
editor         = {Narendra Jussien and Fran\c{c}ois Laburthe},
title          = {Hybrid Optimization Techniques},
publisher      = {Kluwer},
year           = 2004,
series         = {Annals of Operations Research},
volume         = 130,
month          = aug,
note           = {Special Issue following CP-AI-OR'02},
issn           = {0254 5330},
kind           = {LEDL},
}

Mohammad Ghoniem, Narendra Jussien, Jean-Daniel Fekete

"VISEXP: visualizing constraint solver dynamics using explanations" , FLAIRS'04: Seventeenth international Florida Artificial Intelligence Research Society conference, pp. 263-268, AAAI press, 2004

abstract, article [pdf, 444 KB]

@InProceedings{ghoniem-visexp,
author         = {Mohammad Ghoniem and Narendra Jussien and Jean-Daniel Fekete},
title          = {{VISEXP}: visualizing constraint solver dynamics using explanations},
booktitle      = {FLAIRS'04: Seventeenth international Florida Artificial Intelligence Research Society conference},
year           = 2004,
address        = {Miami, Florida, USA},
month          = may,
publisher      = {AAAI press},
kind           = {MISA},
taux           = {158/286},
pages          = {263--268},
url            = {http://www.emn.fr/jussien/publications/ghoniem-FLAIRS04.pdf},
abstract       = {In this paper, we introduce VISEXP: a new visualization tool designed to explore relations between constraints and variables in constraint problems. This tool uses the explanation network built throughout computation. We show that VISEXP is able to provide much more information about how search is performed than classical representations. Moreover, we illustrate the animation feature of VISEXP that provides invaluable tools for visualization and therefore analysis of the dynamics of constraint solvers. }
}

Narendra Jussien

"The versatility of using explanations within constraint programming" , Habilitation thesis of Université de Nantes, also available as RR-03-04 research report at École des Mines de Nantes, 2003

abstract

@Misc{jussien-hdr,
author         = {Narendra Jussien},
title          = {The versatility of using explanations within constraint programming},
howpublished   = {Habilitation thesis of Universit\'e de Nantes},
address        = {Nantes, France},
year           = 2003,
month          = {18 } # sep,
kind           = {HDR},
note           = {also available as RR-03-04 research report at \'Ecole des Mines de Nantes},
abstract = {La programmation par contraintes est un sujet de recherche qui tire profit de nombreuses autres disciplines~: math{\'e}matiques discr{\`e}tes, analyse num{\'e}rique, intelligence artificielle, recherche op{\'e}rationnelle et calcul formel. Elle a prouv{\'e} son int{\'e}r{\^e}t et son efficacit{\'e} dans de nombreux domaines~: optimisation combinatoire, ordonnancement, finance, simulation et synth{\`e}se de composants, diagnostic de panne, biologie mol{\'e}culaire, ou encore probl{\`e}mes g{\'e}om{\'e}triques. N{\'e}anmoins, un certain nombre de limitations et de difficult{\'e}s ont {\'e}t{\'e} identifi{\'e}es dans le domaine~: conception d'algorithmes g{\'e}n{\'e}riques et stables, traitement des probl{\`e}mes dynamiques, accessibilit{\'e} des concepts et des outils, ...

Dans ce document, nous plaidons pour l'utilisation de la notion d'explication au sein de la programmation par contraintes. Notre but est double~: non seulement pr{\'e}senter un tableau g{\'e}n{\'e}ral des explications (d{\'e}finition, g{\'e}n{\'e}ration et utilisations) mais aussi montrer comment leur utilisation permet de contribuer {\`a} lever certains des probl{\`e}mes ouverts en programmation par contraintes. Nous pr{\'e}sentons aussi une d{\'e}marche g{\'e}n{\'e}rale de r{\'e}solution de probl{\`e}me dans un environnement expliqu{\'e}. Enfin, nous montrons comment ce nouveau sujet semble promis {\`a} un bel avenir. }
}

Narendra Jussien

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

abstract, article [pdf, 608 KB]

@TechReport{jussien-versatility-rr,
author         = {Narendra Jussien},
title          = {The versatility of using explanations within constraint programming},
institution    = {\'Ecole des Mines de Nantes},
year           = 2003,
number         = {03-04-INFO},
address        = {Nantes, France},
url            = {http://www.emn.fr/jussien/publications/jussien-RR0304.pdf},
kind           = {RR},
type           = {Research Report},
abstract       = {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. However, some limitations and difficulties remain: designing stable and generic algorithms, handling dynamic problems, opening constraint programming to non-specialists, etc.

In this document, we advocate the use of explanations within constraint programming.  Our aim is two-fold: drawing the \emph{big picture} about explanations (definition, generation, management and use) and showing that they can help address several issues in constraint programming. We also introduce a new general explanation-based search technique that has been successfully used to design new efficient algorithms. Finally, current open issues and research topics in this field are presented.}
}

Guillaume Rochart, Narendra Jussien, François Laburthe

"Challenging explanations for global constraints" , CP03 Workshop on User-Interaction in Constraint Satisfaction (UICS'03), pp. 31-43, 2003

, article [pdf, 158 KB]

@InProceedings{rochart-challenging,
author         = {Guillaume Rochart and Narendra Jussien and Fran\c{c}ois Laburthe},
title          = {Challenging explanations for global constraints},
booktitle      = {CP03 Workshop on User-Interaction in Constraint Satisfaction (UICS'03)},
year           = 2003,
pages          = {31--43},
address        = {Kinsale, Ireland},
month          = sep,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/rochart-UICS03.pdf},
}

Mohammad Ghoniem, Narendra Jussien, Jean-Daniel Fekete

"Visualizing explanations to exhibit dynamic structure in constraint problems" , CP03 Workshop on User-Interaction in Constraint Satisfaction (UICS'03), pp. 1-15, 2003

, article [pdf, 1230 KB]

@InProceedings{ghoniem-visualizing,
author         = {Mohammad Ghoniem and Narendra Jussien and Jean-Daniel Fekete},
title          = {Visualizing explanations to exhibit dynamic structure in constraint problems},
booktitle      = {CP03 Workshop on User-Interaction in Constraint Satisfaction (UICS'03)},
year           = 2003,
pages          = {1--15},
address        = {Kinsale, Ireland},
month          = sep,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/ghoniem-UICS03.pdf},
}

Gérard Verfaillie, Narendra Jussien

"Dynamic constraint solving" , Principles and Practice of Constraint Programming (CP 2003), Tutorial - online notes available here, 2003

abstract, article []

@InProceedings{verfaillie-tutorial-cp2003,
author         = {G\'erard Verfaillie and Narendra Jussien},
title          = {Dynamic constraint solving},
booktitle      = {Principles and Practice of Constraint Programming (CP 2003)},
  year         = 2003,
  month        = oct,
  address      = {Kinsale, County Cork, Ireland},
  kind         = {MIADR},
url            = {http://www.emn.fr/jussien/CP03tutorial},
note           = {Tutorial - online notes available http://www.emn.fr/jussien/CP03tutorial},
abstract       = {The objective of this tutorial is to present, mainly for people who are new in the area of Constraint Programming and Constraint Solving, why it is often necessary to consider constraint solving in a dynamic context, what are the main requirements that appear in such a context, and what are the main techniques that have been proposed so far to meet these requirements.},
}

Narendra Jussien, Olivier Lhomme

"Combining Constraint Programming and Local Search to Design New Powerful Heuristics" , 5th Metaheuristics International Conference (MIC'2003), 2003

abstract, article [pdf, 132 KB]

@InProceedings{jussien-combining-heuristics,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {Combining Constraint Programming and Local Search to Design New Powerful Heuristics},
booktitle      = {5th Metaheuristics International Conference (MIC'2003)},
year           = 2003,
address        = {Kyoto, Japan},
month          = aug,
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/jussien-MIC03.pdf},
abstract       = {In this paper, we introduce the PLM algorithm which decomposes search into three components: a Propagation component (used to share information between variables), a Learning component (used to take benefit from dead-ends) and a Moving component (used to explore the search space in a guided way). We show that this generic algorithm is a useful basis for providing new powerful search algorithms that combine constraint programming and local search. },
}

Laurent Breton, Narendra Jussien

"Un CSP comme comportement d'agent. Application à la résolution d'équations en physique des milieux granulaires" , 9ièmes Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'03), pp. 99-113, 2003

abstract, article [pdf, 277 KB]

@InProceedings{breton-agents,
author         = {Laurent Breton and Narendra Jussien},
title          = {Un {CSP} comme comportement d'agent. {A}pplication {\`a} la r{\'e}solution d'{\'e}quations en physique des milieux granulaires},
booktitle      = {9i{\`e}mes Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'03)},
year           = 2003,
address        = {Amiens, France},
month          = jun,
pages          = {99--113},
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/breton-JNPC03.pdf},
abstract       = {En physique des milieux granulaires, des m{\'e}thodes de simulations
num{\'e}riques sont utilis{\'e}es notamment pour tenter de comprendre la
connexion entre les grains et les structures m{\'e}caniques macroscopiques
dans le tas. Nous avons propos{\'e} une mod{\'e}lisation multi-agent originale
qui permet de r{\'e}soudre des tas de sable bidimensionnels {\`a} l'{\'e}quilibre
statique. Mais, le caract{\`e}re stochastique de la recherche locale de
solutions d'{\'e}quilibre pose le probl{\`e}me de la couverture de l'espace des
solutions par cet algorithme. La r{\'e}solution de ce probl{\`e}me par une
approche purement CSP se r{\'e}v{\`e}le difficile du fait de la taille
gigantesque du probl{\`e}me {\`a} traiter. Nous proposons donc de mettre en
oeuvre des techniques de CSP comme comportements de r{\'e}solution local de
l'{\'e}quilibre d'agents-grains.},
}

Guillaume Rochart, Narendra Jussien

"Une contrainte \textttstretch expliquée" , 9ièmes Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'03), pp. 309-323, 2003

abstract, article [pdf, 316 KB]

@InProceedings{rochart-stretch-jnpc,
author         = {Guillaume Rochart and Narendra Jussien},
title          = {Une contrainte \texttt{stretch} expliqu{\'e}e},
booktitle      = {9i{\`e}mes Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'03)},
year           = 2003,
address        = {Amiens, France},
month          = jun,
pages          = {309--323},
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/rochart-JNPC03.pdf},
abstract       = {Nous montrons dans cet article comment {\'e}tendre une contrainte
globale, stretch, pour l'utiliser das un contexte expliqu{\'e}. Ceci se traduit
notamment par la production d'explications pr{\'e}cises pour chacune des
d{\'e}cisions prises lors du filtrage. Les exp{\'e}rimentations montrent une
am{\'e}lioration notable de la r{\'e}solution de probl{\`e}mes mettant en oeuvre une
telle contrainte.},
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Solving dynamic timetabling problems as dynamic resource constrained project scheduling problems using new constraint programming tools" , Practice and Theory of Automated Timetabling IV, Lecture Notes in Computer Science, no. 2740, pp. 39-59, Springer-Verlag, 2003

abstract, article [pdf, 286 KB]

@InProceedings{elkhyari-solving-lncs,
author         = {Abdallah Elkhyari and Christelle Gu\'eret and Narendra Jussien},
title          = {Solving dynamic timetabling problems as dynamic resource constrained project scheduling problems using new constraint programming tools},
editor         = {E.~K. Burke and P. De Causmaecker},
series         = {Lecture Notes in Computer Science},
number         = 2740,
  year         = 2003,
  pages        = {39--59},
booktitle      = {Practice and Theory of Automated Timetabling IV},
publisher      = {Springer-Verlag},
kind           = {CDL},
url            = {http://www.emn.fr/jussien/publications/elkhyari-LNCS03.pdf},
abstract       = {Timetabling problems have been studied a lot over the last decade. Due to the complexity and the variety of such problems, most work concern static problems in which activities to schedule and resources are known in advance, and constraints are fixed. However, every timetabling problem is subject to unexpected events (consider for example, for university timetabling problems, a missing teacher, or a slide projector breakdown). In such a situation, one has to quickly build a new solution which takes these events into account and which is preferably not too different from the current one. We introduce in this paper constraint-programming based tools for solving dynamic timetabling  problems modelled as RCPSP (Resource-Constrained Project Scheduling Problems). This approach uses explanation-based constraint programming and operational research techniques. },
}

Narendra Jussien

"L'enseignement de la programmation logique à l'École des Mines de Nantes" , Journées Francophones de Progammation en Logique et avec Contraintes (JFPLC'03), pp. 63-75, Hermès, 2003

abstract, article [pdf, 182 KB]

@InProceedings{jussien-prolog,
author         = {Narendra Jussien},
title          = {L'enseignement de la programmation logique {\`a} l'{\'E}cole des {M}ines de {N}antes},
booktitle      = {Journ\'ees Francophones de Progammation en Logique et avec Contraintes (JFPLC'03)},
year           = 2003,
address        = {Amiens, France},
month          = jun,
publisher      = {Herm\`es},
kind           = {MNSA},
pages          = {63--75},
url            = {http://www.emn.fr/jussien/publications/jussien-JFPLC03.pdf},
abstract       = {La programmation logique est enseign{\'e}e {\`a} l'\'Ecole des
Mines de Nantes depuis 1994. Apr{\`e}s une augmentation du volume
horaire en 1998 (de 15 {\`a} 30 heures), le contenu du cours a {\'e}volu{\'e}
pour proposer un cheminement plus complet depuis la logique
formelle jusqu'{\`a} la programmation en logique. Ce document pr{\'e}sente
l'organisation du cours tel qu'il est dispens{\'e} actuellement.},
}

Samir Ouis, Narendra Jussien, Patrice Boizumault

"Explications k-relevantes pour la programmation par contraintes" , Journées Francophones de Progammation en Logique et avec Contraintes (JFPLC'03), pp. 111-124, Hermès, 2003

abstract, article [pdf, 131 KB]

@InProceedings{ouis-k-pertinence,
author         = {Samir Ouis and Narendra Jussien and Patrice Boizumault},
title          = {Explications $k$-relevantes pour la programmation par contraintes},
booktitle      = {Journ\'ees Francophones de Progammation en Logique et avec Contraintes (JFPLC'03)},
year           = 2003,
address        = {Amiens, France},
month          = jun,
publisher      = {Herm\`es},
kind           = {MNSA},
pages          = {111--124},
url            = {http://www.emn.fr/jussien/publications/ouis-JFPLC03.pdf},
abstract       = {Cet article pr{\'e}sente des outils permettant
{\`a} un utilisateur de la programmation par contraintes de
d{\'e}velopper interactivement une application. L'implantation de ces outils repose
sur l'utilisation des explications dite $k$-pertinentes. Un exemple est donn{\'e} pour
illustrer les concepts et mettre en avant diff{\'e}rentes situations concr{\`e}tes d'utilisation
de nos outils. },
}

Guillaume Rochart, Narendra Jussien

"Explanations for global constraints: instrumenting the stretch constraint" , École des Mines de Nantes, technical report, no. 03-01-INFO, 2003

, article [pdf, 274 KB]

@TechReport{rochart-stretch-rr,
author         = {Guillaume Rochart and Narendra Jussien},
title          = {Explanations for global constraints: instrumenting the stretch constraint},
institution    = {\'Ecole des Mines de Nantes},
year           = 2003,
number         = {03-01-INFO},
address        = {Nantes, France},
url            = {http://www.emn.fr/jussien/publications/rochart-RR0301.pdf},
kind           = {RR},
type           = {Research Report},
}

Narendra Jussien, Romuald Debruyne

"Explanation-based repair techniques for constraint programming" , Projet OADymPPaC, technical report, no. D3.2.3, 2003

, article [pdf, 292 KB]

@TechReport{oadymppac-323,
author         = {Narendra Jussien and Romuald Debruyne},
title          = {Explanation-based repair techniques for constraint programming},
institution    = {Projet OADymPPaC},
year           = 2003,
type           = {D{\'e}livrable},
number         = {D3.2.3},
address        = {http://contraintes.inria.fr/OADymPPaC},
kind           = {RR},
url            = {http://www.emn.fr/jussien/publications/oadymppac-323.pdf},
}

Narendra Jussien

"Programmation par contraintes pour les technologies logicielles" , Colloque GEMSTIC'03 : l'industrie du logiciel - outils et méthodologies, Groupe des Écoles des Mines, 2003

abstract, article [pdf, 124 KB]

@InProceedings{jussien-gemstic,
author         = {Narendra Jussien},
title          = {Programmation par contraintes pour les technologies logicielles},
booktitle      = {Colloque GEMSTIC'03~: l'industrie du logiciel -- outils et m{\'e}thodologies},
year           = 2003,
address        = {Paris, France},
month          = apr,
organization   = {Groupe des \'Ecoles des Mines},
kind           = {MNADR},
url            = {http://www.emn.fr/jussien/publications/jussien-GEMSTIC03.pdf},
abstract       = {La programmation par contraintes, discipline au carrefour de
l'intelligence artificielle, de la recherche op{\'e}rationnelle et de
l'analyse num{\'e}rique a fait ses preuves pour la r{\'e}solution de
probl{\`e}mes combinatoires complexes dans le domaine de l'aide {\`a} la
d{\'e}cision. De nouveaux champs d'applications apparaissent, en
particulier dans le domaine du g{\'e}nie logiciel. Au travers de
quelques exemples (notamment l'identification et la correction de
motifs de conception approch{\'e}s et la r{\'e}alisation d'applications
dans un contexte anytime), nous montrons les apports et les
perspectives de l'utilisation de la programmation par contraintes
dans le domaine du g{\'e}nie logiciel.},
}

Christelle Guéret, Narendra Jussien, Olivier Lhomme, Claire Pavageau, Christian Prins

"Loading aircraft for military operations" , in: "Journal of the Operational Resarch Society", vol. 54, no. 5, pp. 458-465, 2003

abstract, article [pdf, 149 KB]

@Article{gueret-loading,
author         = {Christelle Gu{\'e}ret and Narendra Jussien and Olivier Lhomme and Claire Pavageau and Christian Prins},
title          = {Loading aircraft for military operations},
journal        = {Journal of the Operational Resarch Society},
volume         = 54,
number         = 5,
pages          = {458--465},
year           = 2003,
kind           = {RIAS},
url            = {http://www.emn.fr/jussien/publications/gueret-JORS03.pdf},
abstract       = {In this paper, we present an aircraft loading problem brought to us by the French military agency (DGA). We present our two phases
methods (computation of an initial heuristic solution before the
application of local search heuristics) and results obtained on
real data sets.}
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Utilisation de la programmation par contraintes pour résoudre le RCPSP dynamique et quelques extensions" , 5ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2003), pp. 97-98, 2003

@InProceedings{elkhyari-utilisation,
author         = {Abdallah Elkhyari and Christelle Gu{\'e}ret and Narendra Jussien},
title          = {Utilisation de la programmation par contraintes pour r{\'e}soudre le {RCPSP} dynamique et quelques extensions},
booktitle      = {5{\`e}me congr{\`e}s de la Soci{\'e}t{\'e} Fran\c{c}aise de Recherche Op{\'e}rationnelle et d'Aide {\`a} la D{\'e}cision (ROADEF 2003)},
year           = 2003,
pages          = {97--98},
address        = {Avignon, France},
month          = feb,
kind           = {MNSA},
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Solving dynamic RCPSP using explanations-based constraint programming" , MAPSP'03: Sixth workshop on Models and Algorithms for Planning and Scheduling Problems, pp. 119-120, 2003

, article [pdf, 91 KB]

@InProceedings{ elkhyari-solving,
author         = {Abdallah Elkhyari and Christelle Gu{\'e}ret and Narendra Jussien},
title          = {Solving dynamic {RCPSP} using explanations-based constraint programming},
booktitle      = {MAPSP'03: Sixth workshop on Models and Algorithms for Planning and Scheduling Problems},
year           = 2003,
address        = {Aussois, France},
month          = mar,
pages          = {119--120},
url            = {http://www.emn.fr/jussien/publications/elkhyari-MAPSP03.pdf},
kind           = {MISA}
}

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

abstract, article [pdf, 134 KB]

@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},
year           = 2003,
address        = {St. Augustine, Florida, USA},
month          = may,
pages          = {172--176},
publisher      = {AAAI press},
url            = {http://www.emn.fr/jussien/publications/debruyne-FLAIRS03.pdf},
kind           = {MISA},
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.}
}

Samir Ouis, Narendra Jussien, Patrice Boizumault

"k-relevant explanations for constraint programming" , FLAIRS'03: Sixteenth international Florida Artificial Intelligence Research Society conference, pp. 192-196, AAAI press, 2003

abstract, article [pdf, 116 KB]

@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},
year           = 2003,
address        = {St. Augustine, Florida, USA},
month          = may,
pages          = {192--196},
publisher      = {AAAI press},
url            = {http://www.emn.fr/jussien/publications/ouis-FLAIRS03.pdf},
kind           = {MISA},
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.}
}

Narendra Jussien, François Laburthe

"Fourth international workshop on integration of AI and OR techniques in Constraint Programming for combinatorial optimisation problems (CP-AI-OR)" , École des Mines de Nantes, 2002

abstract, article []

@Proceedings{cpaior02,
title = {Fourth international workshop on integration of {AI} and {OR} techniques in {C}onstraint {P}rogramming for combinatorial optimisation problems (CP-AI-OR)},
year = 2002,
editor = {Narendra Jussien and Fran\c{c}ois Laburthe},
address = {Le Croisic, France},
month = mar # {, 25--27},
organization = {\'Ecole des Mines de Nantes},
kind = {LEDL},
url = {http://www.emn.fr/x-info/cpaior/},
abstract = {The integration of techniques from AI and OR has given birth to a new
family of algorithms for tackling complex and large scale
combinatorial problems. The value of this integration has been shown
in applications such as hoist scheduling, rostering, dynamic
scheduling, vehicle routing, network design, ...

At the programming/modelling level, most constraint languages embed OR
techniques to reason about collections of constraints, so-called
global constraints. A few also provide support for hybridization
allowing the programmer to build new integrated algorithms. The
resulting multi-paradigm programming framework combines the
flexibility and modelling facilities of constraint programming with
the special purpose and efficient methods from Operations Research.

The purpose of the CP-AI-OR workshop is to bring researchers from the
communities of the various optimization techniques to learn about new
progress in hybrid optimization techniques and to exchange ideas and
methodologies.

This year's edition is the fourth one, and the we are very happy to
see that the interest in CP-AI-OR is still growing. For CPAIOR'02, 27
papers were selected out of 35 submissions, more than 80 participants
are attending the workshop coming from 17 countries.

We are honoured to welcome three renowned invited speakers this year,
namely, Robert Bixby, Edward Tsang and Jean Charles R{\'e}gin. Their work
span across different areas of combinatorial optimization techniques,
linear and integer programming, local search and constraint
satisfaction, and constrained optimization with global constraints.
The three of them are representative of those researchers who build
bridges between different approaches and improve the state of the art.
We warmfully thank them for taking the time to come to the workshop
and sharing with us their vision of the cross interest of optimization
methods.

One major innovation of this year's edition is the organization of a
School on Optimization by Michela Milano just before the workshop. The
school is a two day Advanced Course on Integration of AI
and OR techniques for combinatorial Optimization. Leading experts in
the field give invited lectures on different aspects of the
integration.

We wish to record a special thank to Catherine de Charette from Ecole
des Mines de Nantes for all her effort in handling the local
organization of this workshop. The success of this CPAIOR edition,
with all its innovations should be credited to her great dedication.}
}

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

"Correctness of Constraint Retraction Algorithms" , École des Mines de Nantes, technical report, no. 02-6-INFO, 2002

abstract, article [pdf, 268 KB]

@TechReport{debruyne-correction-rr-emn,
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},
institution    = {\'Ecole des Mines de Nantes},
year           = 2002,
number         = {02-6-INFO},
address        = {Nantes, France},
url            = {http://www.emn.fr/jussien/publications/debruyne-RR0206.pdf},
kind           = {RR},
type           = {Research Report},
abstract       = {Using a filtering technique is crucial to reduce the search space.
Most of the solvers (eg. CHIP, gnuPROLOG, Ilog SOLVER, CHOCO) use reduction
operators and a propagation mechanism to enforce a local consistency.
This scheme is quite universally used on static CSPs.
But we do not have such an unanimity when relaxing constraints.
Several techniques have been proposed to deal with dynamicity.
The problem we address here is two-fold.
First, we highlight that it is possible to generalize the proposed techniques to relax constraints.
Second, we show a sufficient work to do in order to incrementally relax a constraint.}
}

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

"Correctness of Constraint Retraction Algorithms" , Laboratoire d'Informatique Fondamentale d'Orléans, technical report, no. 2002-09, 2002

abstract, article [ps, 430 KB]

@TechReport{debruyne-correction-rr-lifo,
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},
institution    = {Laboratoire d'Informatique Fondamentale d'Orl{\'e}ans},
year           = 2002,
number         = {2002-09},
address        = {4, rue L{\'e}onard de Vinci, BP 6759, F-44067 Orl{\'e}ans Cedex 2, France},
url            = {http://www.emn.fr/jussien/publications/debruyne-LIFO2002-09.ps},
kind           = {RR},
type           = {Research Report},
abstract       = {Using a filtering technique is crucial to reduce the search space.
Most of the solvers (eg. CHIP, gnuPROLOG, Ilog SOLVER, CHOCO) use reduction
operators and a propagation mechanism to enforce a local consistency.
This scheme is quite universally used on static CSPs.
But we do not have such an unanimity when relaxing constraints.
Several techniques have been proposed to deal with dynamicity.
The problem we address here is two-fold.
First, we highlight that it is possible to generalize the proposed techniques to relax constraints.
Second, we show a sufficient work to do in order to incrementally relax a constraint.}
}

Rémi Douence, Narendra Jussien

"Non-intrusive constraint solver enhancements" , First AOSD workshop on Aspects, Components, and Patterns for Infrastructure Software (ACP4IS), University of Twente, 2002

abstract, article [pdf, 114 KB]

@InProceedings{douence-non-intrusive,
author         = {R{\'e}mi Douence and Narendra Jussien},
title          = {Non-intrusive constraint solver enhancements},
booktitle      = {First AOSD workshop on Aspects, Components, and Patterns for Infrastructure Software (ACP4IS)},
year           = 2002,
address        = {Enschede, The Netherlands},
month          = {23} # apr,
organization   = {University of Twente},
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/douence-WAOSD02.pdf},
abstract       = {Constraint solvers are useful tools that provide solutions to very
complex problems. These infrastructure software rely on simple
mechanisms, however their actual implementation can be quite
complex. A good knowledge of their inner mechanisms is required to
introduce enhancements which crosscut basic algorithms and
structures. In this paper, we advocate non-intrusive constraint
solver enhancements. First, a minimal solver is introduced.
Second, different enhancements are implemented with the help of
aspect oriented programming.}
}

Rémi Douence, Narendra Jussien

"Non-intrusive constraint solver enhancements" , Colloquium on Implementation of Constraint and LOgic Programming Systems (CICLOPS'02), CW Reports, vol. 344, pp. 26-36, 2002

abstract, article [pdf, 349 KB]

@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          = jul,
kind           = {MIADR},
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.}
}

Rémi Douence, Narendra Jussien

"Non-intrusive constraint solver enhancements" , École des Mines de Nantes, technical report, no. 02-2-INFO, 2002

, article [pdf, 210 KB]

@TechReport{douence-non-intrusive-rr,
author         = {R{\'e}mi Douence and Narendra Jussien},
title          = {Non-intrusive constraint solver enhancements},
institution    = {\'Ecole des Mines de Nantes},
year           = 2002,
number         = {02-2-INFO},
address        = {Nantes, France},
url            = {http://www.emn.fr/jussien/publications/douence-RR0202.pdf},
kind           = {RR},
type           = {Research Report},
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Conflict-based repair techniques for solving dynamic scheduling problems" , Principles and Practice of Constraint Programming (CP 2002), Lecture Notes in Computer Science, no. 2470, pp. 702-707, Springer-Verlag, Short paper, 2002

, article [pdf, 157 KB]

@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},
  kind         = {MISA},
  note         = {Short paper}
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Conflict-based repair techniques for solving dynamic scheduling problems" , École des Mines de Nantes, technical report, no. 02-5-INFO, also available as EMN RR 02-3-AUTO, 2002

abstract, article [pdf, 262 KB]

@TechReport{elkhyari-conflict-dynamic-scheduling-rr,
author         = {Abdallah Elkhyari and Christelle Gu{\'e}ret and Narendra Jussien},
title          = {Conflict-based repair techniques for solving dynamic scheduling problems},
institution    = {\'Ecole des Mines de Nantes},
year           = 2002,
type           = {Research Report},
number         = {02-5-INFO},
note           = {also available as EMN RR 02-3-AUTO},
url            = {http://www.emn.fr/jussien/publications/elkhyari-RR0205.pdf},
kind           = {RR},
abstract       = {Scheduling problems considered in the literature are often static
(activities are known in advance and constraints are fixed).
However, every schedule is subject to unexpected events. In these
cases, a new solution is needed in a preferably short time and as
close as possible to the current solution.

In this paper, we present an exact approach for solving dynamic
Resource-Constrained Project Scheduling Problems or RCPSP. This
approach combines explanation-based constraint programming and
operational research techniques.}
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"Explanation-based repair techniques for solving dynamic scheduling problems" , AIPS'02 Workshop on On-line Planning and Scheduling, 2002

, article [pdf, 55 KB]

@InProceedings{elkhyari-dynamic-scheduling,
author         = {Abdallah Elkhyari and Christelle Gu{\'e}ret and Narendra Jussien},
title          = {Explanation-based repair techniques for solving dynamic scheduling problems},
booktitle      = {AIPS'02 Workshop on On-line Planning and Scheduling},
year           = 2002,
address        = {Toulouse, France},
month          = {24 } # apr,
url            = {http://www.emn.fr/jussien/publications/elkhyari-WAIPS02.pdf},
kind           = {MIADR}
}

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

"New tools for solving dynamic timetabling problems" , Proceedings of the fourth international conference on the Practice And Theory of Automated Timetabling (PATAT'02), pp. 112-114, Short paper, 2002

@InProceedings{elkhyari-dynamic-timetabling,
author         = {Abdallah Elkhyari and Christelle Gu\'eret and Narendra Jussien},
title          = {New tools for solving dynamic timetabling problems},
booktitle      = {Proceedings of the fourth international conference on the Practice And Theory of Automated Timetabling (PATAT'02)},
year           = 2002,
pages          = {112--114},
address        = {Gent, Belgium},
kind           = {MISA},
month          = aug,
  note         = {Short paper}
}

Yann-Gaël Guéhéneuc, Rémi Douence, Narendra Jussien

"No Java without Caffeine - A tool for dynamic analysis of Java programs" , 17th IEEE conference on Automated Software Engineering (ASE'02), pp. 117-126, IEEE Computer Society Press, 2002

, article [pdf, 319 KB]

@InProceedings{gueheneuc-dynamic-analysis,
author          = {Yann-Ga{\"e}l Gu{\'e}h{\'e}neuc and R{\'e}mi Douence and Narendra Jussien},
title           = {No {Java} without {Caffeine} -- A tool for dynamic analysis of {Java} programs},
booktitle       = {17th IEEE conference on Automated Software Engineering (ASE'02)},
pages           = {117--126},
year            = 2002,
address         = {Edinburgh, UK},
month           = sep,
publisher       = {IEEE Computer Society Press},
url             = {http://www.emn.fr/jussien/publications/gueheneuc-ASE02.pdf},
kind            = {MISA},
}

Yann-Gaël Guéhéneuc, Rémi Douence, Narendra Jussien

"No Java without Caffeine - A tool for dynamic analysis of Java programs" , École des Mines de Nantes, technical report, no. 02-7-INFO, 2002

, article [pdf, 249 KB]

@TechReport{gueheneuc-java-caffeine-rr,
author         = {Yann-Ga{\"e}l Gu\'eh\'eneuc and R\'emi Douence and Narendra Jussien},
title          = {No {J}ava without {C}affeine -- A tool for dynamic analysis of {J}ava programs},
institution    = {\'Ecole des Mines de Nantes},
year           = 2002,
number         = {02-7-INFO},
address        = {Nantes, France},
kind           = {RR},
url            = {http://www.emn.fr/jussien/publications/gueheneuc-RR0207.pdf},
type           = {Research Report},
}

Narendra Jussien, Olivier Lhomme

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

abstract, article [pdf, 170 KB]

@Article{jussien-local-aijournal,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {Local search with constraint propagation and conflict-based heuristics},
journal        = {Artificial Intelligence},
publisher      = {Elsevier},
year           = 2002,
month          = jul,
volume         = 139,
number         = 1,
pages          = {21--45},
kind           = {RIAS},
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.}
}

Narendra Jussien, Olivier Lhomme

"Vers une unification des algorithmes de résolution de CSP" , 8ièmes Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'02), pp. 155-168, 2002

abstract, article [pdf, 232 KB]

@InProceedings{jussien-unification,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {Vers une unification des algorithmes de r{\'e}solution de {CSP}},
booktitle      = {8i{\`e}mes Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'02)},
pages          = {155--168},
year           = 2002,
address        = {Nice, France},
month          = may,
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/jussien-JNPC02.pdf},
abstract       = {Ginsberg et McAllester ont montr{\'e} que les
algorithmes de recherche de solution syst{\'e}matiques et non
syst{\'e}matiques pouvaient {\^e}tre tr{\`e}s proches. Dans cet article, nous
souhaitons aller plus loin vers la compr{\'e}hension des relations
entre les approches syst{\'e}matiques et non-syst{\'e}matiques en
introduisant le mod{\`e}le \textbf{PLM}. Nous pr{\'e}sentons un algorithme
g{\'e}n{\'e}rique de recherche pour r{\'e}soudre des \csp\ et nous montrons
que de nombreux algorithmes de r{\'e}solution peuvent se d{\'e}composer en
utilisant un ensemble restreint de primitives.
La connaissance de ces primitives permet non seulement de
comparer plus ais{\'e}ment les algorithmes de recherche mais aussi de
d{\'e}finir de nouveaux algorithmes.}
}

Narendra Jussien, Olivier Lhomme

"Unifying search algorithms for CSP" , École des Mines de Nantes, technical report, no. 02-3-INFO, 2002

, article [pdf, 215 KB]

@TechReport{jussien-unifying-rr,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {Unifying search algorithms for {CSP}},
institution    = {\'Ecole des Mines de Nantes},
year           = 2002,
type           = {Research Report},
number         = {02-3-INFO},
url            = {http://www.emn.fr/jussien/publications/jussien-RR0203.pdf},
address        = {Nantes, France},
kind           = {RR},
}

Pierre Deransart, François Fages, Narendra Jussien, Ludovic Langevine, Raphaël Martin

"Débogage dynamique de programmes avec contraintes sur les domaines finis: état et perspectives" , Projet OADymPPaC, technical report, no. D2.1.1.1, 2002

, article [zip, 3563 KB]

@TechReport{oadymppac-2111,
author         = {Pierre Deransart and Fran\c{c}ois Fages and Narendra Jussien and Ludovic Langevine and Rapha\"{e}l Martin},
title          = {D{\'e}bogage dynamique de programmes avec contraintes sur les domaines finis: \'{e}tat et perspectives},
institution    = {Projet OADymPPaC},
year           = 2002,
type           = {D{\'e}livrable},
number         = {D2.1.1.1},
address        = {http://contraintes.inria.fr/OADymPPaC},
kind           = {RR},
url            = {http://www.emn.fr/jussien/publications/oadymppac-2111.zip},
}

Samir Ouis, Narendra Jussien, Patrice Boizumault

"COINS: a constraint-based interactive solving system" , ICLP'02 12th Workshop on Logic Programming Environments (WLPE'02), pp. 31 - 46, 2002

abstract, article [pdf, 249 KB]

@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,
kind           = {MIADR},
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.}
}

Samir Ouis, Narendra Jussien, Patrice Boizumault

"k-relevant explanations for constraint programming" , CP02 Workshop on User-Interaction in Constraint Satisfaction (UICS'02), pp. 109-123, 2002

abstract, article [pdf, 203 KB]

@InProceedings{ouis-k-relevant,
author         = {Samir Ouis and Narendra Jussien and Patrice Boizumault},
title          = {$k$-relevant explanations for constraint programming},
booktitle      = {CP02 Workshop on User-Interaction in Constraint Satisfaction (UICS'02)},
year           = 2002,
pages          = {109--123},
address        = {Ithaca, NY, USA},
month          = sep,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/ouis-WCP02.pdf},
abstract       = {This paper presents a set of tools based on explanations for
constraint programming. These tools exploit k-relevant
explanations which enable us to use several explanations, which
can sometimes leads to better diagnosis. k-relevant explanations
are introduced and used to provide: diagnosis tools (state
analysis, contradiction analysis, constraint impact analysis),
interaction tools (dynamic constraint addition/retraction
simulation), as well as improved search techniques.}
}

Samir Ouis, Narendra Jussien, Olivier Lhomme

"Explications conviviales pour la programmation par contraintes" , Journées Francophones de Progammation en Logique et avec Contraintes (JFPLC'02), pp. 105-118, Hermès, 2002

abstract, article [pdf, 174 KB]

@InProceedings{ouis-explications,
author         = {Samir Ouis and Narendra Jussien and Olivier Lhomme},
title          = {Explications conviviales pour la programmation par contraintes},
booktitle      = {Journ\'ees Francophones de Progammation en Logique et avec Contraintes (JFPLC'02)},
pages          = {105--118},
year           = 2002,
address        = {Nice, France},
month          = may,
publisher      = {Herm\`es},
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/ouis-JFPLC02.pdf},
abstract       = {Dans ce papier, nous pr{\'e}sentons un ensemble
                 d'outils pour fournir des explications conviviales
                 dans un syst{\`e}me de programmation par contraintes
                 avec explications. L'id{\'e}e est de repr{\'e}senter
                 les contraintes d'un probl{\`e}me sous forme
                 hi{\'e}rarchique (un arbre). Les utilisateurs sont
                 alors repr{\'e}sent{\'e}s comme un ensemble de noeuds
                 compr{\'e}hensibles dans cet arbre (une coupe). Les
                 explications classiques (les ensembles de contraintes
                 du syst{\`e}me) doivent juste {\^e}tre projet{\'e}es
                 sur cette repr{\'e}sentation pour {\^e}tre
                 compr{\'e}hensibles par n'importe quel
                 utilisateur. Nous pr{\'e}sentons ici les
                 int{\'e}r{\^e}ts principaux de cette id{\'e}e.},
}

Hervé Albin-Amiot, Pierre Cointe, Yann-Gaël Guéhéneuc, Narendra Jussien

"Instantiating and Detecting Design Patterns: Putting Bits and Pieces Together" , 16th IEEE conference on Automated Software Engineering (ASE'01), pp. 166-173, IEEE Computer Society Press, 2001

abstract, article [pdf, 269 KB]

@InProceedings{albin-amiot-identifying,
author         = {Herv\'e Albin-Amiot and Pierre Cointe and Yann-Ga{\"e}l Gu{\'e}h{\'e}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)},
pages          = {166--173},
publisher      = {IEEE Computer Society Press},
year           = 2001,
address        = {San Diego, USA},
month          = nov,
url            = {http://www.emn.fr/jussien/publications/albin-amiot-ASE01.pdf},
kind           = {MISA},
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. }
}

Yann-Gaël Guéhéneuc, Narendra Jussien

"Quelques explications pour les patrons ou une utilisation de la PPC avec explications pour l'identification de patrons de conception" , 7ièmes Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'01), pp. 111-122, 2001

abstract, article [pdf , 339 KB]

@InProceedings{gueheneuc-explications,
author         = {Yann-Ga{\"e}l Gu{\'e}h{\'e}neuc and Narendra Jussien},
title          = {Quelques explications pour les patrons ou une utilisation de la {PPC} avec explications pour l'identification de patrons de conception},
booktitle      = {7i{\`e}mes Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'01)},
year           = 2001,
address        = {Toulouse, France},
month          = jun,
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/gueheneuc-JNPC01.pdf },
pages          = {111-122},
abstract       = {Les patrons de conception d{\'e}crivent des micro-architectures
qui r{\'e}solvent des probl{\`e}mes architecturaux
r{\'e}currents. Il est important d'identifier ces
micro-architectures lors de la maintenance des programmes
orient{\'e}s objets. Mais ces micro-architectures apparaissent
souvent sous des formes d{\'e}grad{\'e}es dans le code source.
Nous pr{\'e}sentons une application de la programmation par
contraintes avec explications pour l'identification de ces
micro-architectures d{\'e}grad{\'e}es.}
}

Yann-Gaël Guéhéneuc, Narendra Jussien

"Using explanations for design-patterns identification" , IJCAI'01 Workshop on Modelling and Solving problems with constraints, pp. 57-64, 2001

abstract, article [pdf, 222 KB]

@InProceedings{gueheneuc-ptidej,
author         = {Yann-Ga{\"e}l Gu{\'e}h{\'e}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,
kind           = {MIADR},
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. },
}

Christelle Guéret, Narendra Jussien, Olivier Lhomme, Claire Pavageau, Christian Prins

"Loading aircrafts for military operations" , École des Mines de Nantes, technical report, no. 01-2-INFO, 2001

, article [pdf, 169 KB]

@TechReport{gueret-loading-rr,
author         = {Christelle Gu{\'e}ret and Narendra Jussien and Olivier Lhomme and Claire Pavageau and Christian Prins},
title          = {Loading aircrafts for military operations},
institution    = {\'Ecole des Mines de Nantes},
year           = 2001,
number         = {01-2-INFO},
address        = {Nantes, France},
url            = {http://www.emn.fr/jussien/publications/gueret-RR0102.pdf},
kind           = {RR},
type           = {Research Report},
}

Narendra Jussien

"Programmation par Contraintes avec Explications" , Journée Contraintes et Règles de l'Association Française pour la Programmation Logique et la programmation par Contraintes. Invité par Arnaud Lallouet et Gérard Ferrand, 2001

abstract, article [pdf, 62 KB]

@Misc{jussien-afplc01,
author        = {Narendra Jussien},
title         = {Programmation par Contraintes avec Explications},
howpublished  = {Journ\'ee \emph{Contraintes et R{\`e}gles } de l'Association Fran\c{c}aise pour la Programmation Logique et la programmation par Contraintes. Invit\'e par Arnaud Lallouet et G{\'e}rard Ferrand},
month         = jan,
year          = 2001,
kind          = {DIVERS},
url           = {http://www.emn.fr/jussien/publications/jussien-AFPLC01.pdf},
abstract      = {La programmation par contraintes a maintenant d{\'e}montr{\'e} son int{\'e}r{\^e}t et
ses capacit{\'e}s {\`a} la r{\'e}solution de probl{\`e}mes tr{\`e}s complexes. Du fait de
ces r{\'e}sultats, de nouvelles fontionnalit{\'e}s sont maintenant demand{\'e}es aux
syst{\`e}mes de r{\'e}solution : l'int{\'e}ractivit{\'e}, la capacit{\'e} d'explication du
raisonnement, le d{\'e}bogage adapt{\'e}

Les syst{\`e}mes commerciaux actuels n'apportent pas encore de r{\'e}ponse {\`a}
cette probl{\'e}matique. Le projet europ{\'e}en DiSCiPl a n{\'e}anmoins propos{\'e} de
nouveaux outils de d{\'e}bogage pour les applications contraintes et plus
r{\'e}cemment, le projet RNTL OADYMPPAC s'attaque de front {\`a} ces sujets.

Lors de nos travaux sur les syst{\`e}mes automatiques de relaxation de
contraintes, un concept cl{\'e} est apparu : la notion d'explication. Ces
explications semblent {\^e}tre un outil particuli{\`e}rement efficace dans ce
contexte d'int{\'e}ractivit{\'e} avec l'utilisateur.

Nous pr{\'e}senterons, dans cet expos{\'e}, la notion d'explication (sous
ensemble incoh{\'e}rent des contraintes du probl{\`e}me), le calcul de telles
explications et surtout les diff{\'e}rentes utilisations de cette notion.}
}

Narendra Jussien

"e-constraints: explanation-based Constraint Programming" , CP01 Workshop on User-Interaction in Constraint Satisfaction, 2001

abstract, article [pdf, 227 KB]

@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},
month          = {1 } # dec,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/jussien-WCP01.pdf},
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.}
}

Narendra Jussien

"e-constraints: explanation-based Constraint Programming" , École des Mines de Nantes, technical report, no. 01-5-INFO, 2001

@TechReport{jussien-e-constraints-rr,
author         = {Narendra Jussien},
title          = {e-constraints: explanation-based Constraint Programming},
institution    = {\'Ecole des Mines de Nantes},
year           = 2001,
type           = {Research Report},
number         = {01-5-INFO},
address        = {Nantes, France},
kind           = {RR},
}

Narendra Jussien

"Programmation par contraintes avec explications" , 7ièmes Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'01), pp. 147-158, 2001

abstract, article [pdf, 263 KB]

@InProceedings{jussien-explications,
  author       = {Narendra Jussien},
  title        = {Programmation par contraintes avec explications},
  booktitle    = {7i{\`e}mes Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'01)},
  year         = 2001,
  pages        = {147--158},
  month        = jun,
  kind         = {MNSA},
  url          = {http://www.emn.fr/jussien/publications/jussien-JNPC01.pdf},
  abstract     = {Nous pr\'esentons dans cet article notre exp\'erience dans le domaine de
  l'utilisation des explications dans le cadre de la programmation par
  contraintes. Nous pr\'esentons aussi bien l'impl\'ementation d'un
  syst\`eme d'explications que les diverses utilisations que l'on peut
  en faire.  Nous pr\'esentons en particulier, outre des utilisations
  classiques pour le d\'ebogage ou la prise en compte de la dynamicit\'e,
  une utilisation plus enfouie qui nous conduit \`a proposer une
  nouvelle forme de programmation~: la programmation par contraintes
  avec explications. }
}

Narendra Jussien

"Recherche locale et propagation de contraintes pour résoudre les problèmes d'Open-Shop" , Troisièmes journées francophones de Recherche Opérationnelle (FRANCORO III), 2001

, article [pdf, 79 KB]

@InProceedings{jussien-locale,
  author       = {Narendra Jussien},
  title        = {Recherche locale et propagation de contraintes pour r{\'e}soudre les probl{\`e}mes d'Open-Shop},
  booktitle    = {Troisi{\`e}mes journ{\'e}es francophones de Recherche Op{\'e}rationnelle (FRANCORO III)},
  year         = 2001,
  address      = {Qu{\'e}bec, Canada},
  month        = may,
  kind         = {MNSA},
  url          = {http://www.emn.fr/jussien/publications/jussien-FRANCORO01.pdf},
}

Narendra Jussien, Samir Ouis

"User-friendly explanations for constraint programming" , ICLP'01 11th Workshop on Logic Programming Environments (WLPE'01), 2001

abstract, article [pdf, 285 KB]

@InProceedings{jussien-user-friendly,
author         = {Narendra Jussien and Samir Ouis},
title          = {User-friendly explanations for constraint programming},
booktitle      = {ICLP'01 11th Workshop on Logic Programming Environments (WLPE'01)},
year           = 2001,
address        = {Paphos, Cyprus},
month          = {1 } # dec,
kind           = {MIADR},
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.}
}

Narendra Jussien, Samir Ouis

"User-friendly explanations for constraint programming" , École des Mines de Nantes, technical report, no. 01-6-INFO, 2001

@TechReport{jussien-user-friendly-rr,
author         = {Narendra Jussien and Samir Ouis},
title          = {User-friendly explanations for constraint programming},
institution    = {\'Ecole des Mines de Nantes},
year           = 2001,
type           = {Research Report},
number         = {01-6-INFO},
address        = {Nantes, France},
kind           = {RR},
}

Romuald Debruyne, Jean-Daniel Fekete, Narendra Jussien, Mohammad Ghoniem, others

"Proposition de format concret pour les traces générées par les solveurs de contraintes" , Projet OADymPPaC, technical report, no. D2.2.2.1, 2001

, article [pdf, 146 KB]

@TechReport{oadymppac-2221,
author         = {Romuald Debruyne and Jean-Daniel Fekete and Narendra Jussien and Mohammad Ghoniem and others},
title          = {Proposition de format concret pour les traces g{\'e}n{\'e}r{\'e}es par les solveurs de contraintes},
institution    = {Projet OADymPPaC},
year           = 2001,
type           = {D{\'e}livrable},
number         = {D2.2.2.1},
address        = {http://contraintes.inria.fr/OADymPPaC},
kind           = {RR},
url            = {http://www.emn.fr/jussien/publications/oadymppac-2221.pdf},
}

Christelle Guéret, Narendra Jussien, Olivier Lhomme, Claire Pavageau, Christian Prins

"Chargement d'avions dans le cadre d'une projection de forces" , 3ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2000), 2000

abstract, article [pdf, 16 KB]

@InProceedings{gueret-chargement,
author         = {Christelle Gu{\'e}ret and Narendra Jussien and Olivier Lhomme and Claire Pavageau and Christian Prins},
title          = {Chargement d'avions dans le cadre d'une projection de forces},
booktitle      = {3{\`e}me congr{\`e}s de la Soci{\'e}t{\'e} Fran\c{c}aise de Recherche Op{\'e}rationnelle et d'Aide {\`a} la D{\'e}cision (ROADEF 2000)},
address        = {Nantes, France},
year           = 2000,
month          = jan,
url            = {http://www.emn.fr/jussien/publications/gueret-ROADEF00.pdf},
kind           = {MNSA},
abstract       = {Dans le domaine militaire, la projection de forces consiste {\`a} envoyer le plus rapidement possible, en utilisant les moyens mis {\`a} disposition, des mat{\'e}riels en diff{\'e}rents th{\'e}{\^a}tres d'op{\'e}rations tout en respectant un certain nombre de contraintes. Un tel d{\'e}ploiement n{\'e}cessite une {\'e}tape consistant {\`a} charger les moyens de transport (des avions dans notre cas) avec le mat{\'e}riel concern{\'e}. L'objectif du travail pr{\'e}sent{\'e} ici est de r{\'e}aliser un outil automatis{\'e} qui r{\'e}alise cette op{\'e}ration en cherchant {\`a} minimiser le nombre total de trajets pour acheminer tout le mat{\'e}riel. },
}

Christelle Guéret, Narendra Jussien, Olivier Lhomme, Claire Pavageau, Christian Prins

"Loading aircrafts for military operations" , First International Workshop on Freight Transportation and Logistics (Odysseus 2000), 2000

, article [pdf, 81 KB]

@InProceedings{gueret-military,
author         = {Christelle Gu{\'e}ret and Narendra Jussien and Olivier Lhomme and Claire Pavageau and Christian Prins},
title          = {Loading aircrafts for military operations},
booktitle      = {First International Workshop on Freight Transportation and Logistics (Odysseus 2000)},
year           = 2000,
address        = {Chania, Crete},
month          = may,
url            = {http://www.emn.fr/jussien/publications/gueret-ODYSSEUS00.pdf},
kind           = {MIADR},

}

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

abstract, article [pdf, 146 KB]

@Article{gueret-using-ejor,
author         = {Christelle Gu{\'e}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},
url            = {http://www.emn.fr/jussien/publications/gueret-EJOR00.pdf},
kind           = {RIAS},
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.},
}

Narendra Jussien, Olivier Lhomme

"Local search with constraint propagation and conflict-based heuristics" , Seventh National Conference on Artificial Intelligence - AAAI'2000, pp. 169-174, 2000

abstract, article [pdf, 94 KB]

@InProceedings{jussien-local,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {Local search with constraint propagation and conflict-based heuristics},
booktitle      = {Seventh National Conference on Artificial Intelligence -- AAAI'2000},
pages          = {169--174},
year           = 2000,
address        = {Austin, TX, USA},
month          = aug,
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/jussien-AAAI00.pdf},
abstract       = {In this paper, we introduce a new solving algorithm for Constraint
    Satisfaction Problems (CSP). It performs an overall local search
    together with a domain filtering technique to prune the search
    space.  Conflicts detected during filtering are used to guide the
    search.  First experiments with a tabu version of the algorithm
    have shown good results on hard instances of open shop scheduling
    problems.  It competes well with the best highly specialized
    algorithms. },
}

Narendra Jussien, Romuald Debruyne, Patrice Boizumault

"Maintien de la consistance d'arc dans Dynamic Backtracking" , 6ièmes Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'00), pp. 135-149, 2000

abstract, article [pdf, 275 KB]

@InProceedings{jussien-macdbt,
  author       = {Narendra Jussien and Romuald Debruyne and Patrice Boizumault},
  title        = {Maintien de la consistance d'arc dans Dynamic Backtracking},
  booktitle    = {6i{\`e}mes Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'00)},
  year         = 2000,
  pages        = {135--149},
  month        = jun,
  kind         = {MNSA},
  url          = {http://www.emn.fr/jussien/publications/jussien-JNPC00.pdf},
  abstract     = { La plupart des algorithmes de recherche complets pour les Probl\`emes de Satisfaction de Contraintes (csp) sont bas\'es sur l'algorithme \emph{Backtrack Standard}. Deux am\'eliorations majeures de cet algorithme de base ont \'et\'e propos\'ees~: premi\`erement, int\'egrer un m\'ecanisme de propagation des contraintes comme dans l'algorithme \emph{mac} qui maintient la consistance d'arc durant la recherche ; deuxi\`emement, proc\'eder \`a des retours arri\`eres intelligents afin d'\'eviter de tomber plusieurs fois dans les m\^emes impasses en m\'emorisant des nogoods comme dans
\emph{Conflict-directed BackJumping} (\emph{cbj})
ou dans \emph{Dynamic Backtracking} (\emph{dbt}).
Des int\'egrations de m\'ecanismes de propagation des contraintes dans des algorithmes de retours arri\`eres intelligents ont d\'ej\`a \'et\'e propos\'ees comme \emph{mac-cbj} qui maintient la consistance d'arc dans \emph{cbj}.
Cependant, Bessi{\`e}re et R{\'e}gin ont montr\'e que \emph{mac-cbj} \'etait tr\`es rarement meilleur que \emph{mac}.
Mais nous pensons que les mauvais r\'esultats de \emph{mac-cbj} sont plus li\'es au fait que  \emph{cbj} ne parvient pas \`a \'eviter le thrashing\footnote{On dit qu'il y a thrashing quand on refait \`a de nombreuses reprises le m\^eme travail d'instanciation \`a cause du principe du backtrack qui ne revient pas n\'ecessairement sur les causes de l'\'echec.} qu'au co\^ut de la gestion des nogoods.

Cet article d\'ecrit et \'etudie \emph{mac-dbt} qui maintient la consistance d'arc dans \emph{dbt}. Des exp\'erimentations montrent que \emph{mac-dbt} est capable de r\'esoudre de tr\`es grands probl\`emes et qu'il demeure tr\`es stable quand la taille des probl\`emes augmente. De plus,  \emph{mac-dbt} a de meilleurs r\'esultats que \emph{mac} sur les probl\`emes al\'eatoires structur\'es que nous avons g\'en\'er\'es. },
}

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

abstract, article [pdf, 171 KB]

@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},
  kind         = {MISA},
  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{\`e}re and R{\'e}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. },
}

Narendra Jussien, Vincent Barichard

"The PaLM system: explanation-based constraint programming" , Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems, a post-conference workshop of CP 2000, pp. 118-133, 2000

abstract, article [pdf, 216 KB]

@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,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/jussien-WCP00.pdf},
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.},
}

Narendra Jussien, Olivier Lhomme

"The path-repair algorithm" , CP99 Post-conference workshop on Large scale combinatorial optimisation and constraints, Electronic Notes in Discrete Mathematics, vol. 4, Elsevier Science, 2000

abstract, article [pdf, 213 KB]

@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},
kind           = {RIAS},
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. },
}

Christelle Guéret, Narendra Jussien

"Combining AI/OR techniques for solving Open Shop problems" , Conference on Integration of Operations Research and Artificial Intelligence techniques in Constraint Programming (CP-AI-OR), 1999

, article [pdf, 104 KB]

@InProceedings{gueret-combining,
author         = {Christelle Gu\'eret and Narendra Jussien},
title          = {Combining {AI}/{OR} techniques for solving Open Shop problems},
booktitle      = {Conference on Integration of Operations Research and Artificial Intelligence techniques in Constraint Programming (CP-AI-OR)},
year           = 1999,
address        = {Ferrara, Italy},
month          = {25--26 } # feb,
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/gueret-CPAIOR99.pdf},
}

Narendra Jussien

"Explanations for constraint solvers" , Séminaire prospectif sur le débogage de contraintes. Invité par Pierre Deransart., 1999

, article [pdf, 85 KB]

@Misc{jussien-discipl99,
author        = {Narendra Jussien},
title         = {Explanations for constraint solvers},
howpublished  = {S{\'e}minaire prospectif sur le d{\'e}bogage de contraintes. Invit\'e par Pierre Deransart.},
month         = apr,
year          = 1999,
url           = {http://www.emn.fr/jussien/publications/jussien-INRIA99.pdf},
kind          = {DIVERS},
}

Narendra Jussien, Christelle Guéret

"Improving branch and bound algorithms for Open Shop problems" , Conference of the International Federation of Operational Research Societies (IFORS'99), 1999

abstract, article [pdf, 172 KB]

@InProceedings{jussien-improving,
  author       = {Narendra Jussien and Christelle Gu{\'e}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,
  kind         = {MISA},
  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.},
}

Narendra Jussien

"Explications et Programmation par contraintes" , Séminaire de l'Equipe LANDE, IRISA (Rennes). Invité par Erwan Jahier, 1999

, article [pdf, 144 KB]

@Misc{jussien-irisa99,
  author       = {Narendra Jussien},
  title        = {Explications et Programmation par contraintes},
  howpublished = {S{\'e}minaire de l'Equipe LANDE, IRISA (Rennes). Invit\'e par Erwan Jahier},
  month        = jun,
  year         = 1999,
  kind         = {DIVERS},
  url          = {http://www.emn.fr/jussien/publications/jussien-IRISA99.pdf}
}

Narendra Jussien, Olivier Lhomme

"L'algorithme Path-Repair" , 5ièmes Journées nationales sur la résolution pratique de problèmes NP-complets (JNPC'99), 1999

, article [pdf, 177 KB]

@InProceedings{jussien-pathrepair,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {L'algorithme Path-Repair},
booktitle      = {5i{\`e}mes Journ{\'e}es nationales sur la r{\'e}solution pratique de probl{\`e}mes NP-complets (JNPC'99)},
year           = 1999,
address        = {Lyon, France},
month          = jun,
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/jussien-JNPC99.pdf},
}

Narendra Jussien, Olivier Lhomme

"The path-repair algorithm" , CP99 Post-conference workshop on Large scale combinatorial optimisation and constraints, 1999

abstract, article [pdf, 213 KB]

@InProceedings{jussien-pathrepair-cp,
author         = {Narendra Jussien and Olivier Lhomme},
title          = {The path-repair algorithm},
booktitle      = {CP99 Post-conference workshop on Large scale combinatorial optimisation and constraints},
year           = 1999,
address        = {Alexandria, VA, USA},
month          = oct,
kind           = {MIADR},
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. }
}

Christelle Guéret, Narendra Jussien, Christian Prins

"Using intelligent backtracking to improve branch and bound methods: an application to Open-Shop problems" , PMS'98 International Workshop on Project Management and Scheduling, 1998

abstract, article [pdf, 408 KB]

@InProceedings{gueret-using,
author         = {Christelle Gu\'eret and Narendra Jussien and Christian Prins},
title          = {Using intelligent backtracking to improve branch and bound methods: an application to Open-Shop problems},
booktitle      = {PMS'98 International Workshop on Project Management and Scheduling},
year           = 1998,
address        = {Istanbul, Turkey},
month          = jul,
url            = {http://www.emn.fr/jussien/publications/gueret-PMS98.pdf},
kind           = {MISA},
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.}
}

Narendra Jussien

"Systèmes dynamiques et Relaxation" , Journée Contraintes dynamiques, réactivité, interactivité de l'Association Française pour la Programmation Logique et la programmation par Contraintes. Invité par Philippe Codognet et Patrice Boizumault, 1998

, article [pdf, 337 KB]

@Misc{jussien-afplc98,
author        = {Narendra Jussien},
title         = {Syst\`emes dynamiques et Relaxation},
howpublished  = {Journ\'ee \emph{Contraintes dynamiques, r\'eactivit\'e, interactivit\'e } de l'Association Fran\c{c}aise pour la Programmation Logique et la programmation par Contraintes. Invit\'e par Philippe Codognet et Patrice Boizumault},
month         = jun,
year          = 1998,
url           = {http://www.emn.fr/jussien/publications/jussien-AFPLC98.pdf},
kind          = {DIVERS},
}

Narendra Jussien, Christelle Guéret

"Procédures de Séparation-Évaluation - Une alternative au retour-arrière - Application au problème d'Open-Shop" , Journées Francophones de Progammation en Logique et avec Contraintes (JFPLC'98), pp. 231-250, Hermès, 1998

abstract, article [pdf, 358 KB]

@InProceedings{jussien-alternative,
author         = {Narendra Jussien and Christelle Gu\'eret},
title          = {Proc\'edures de S\'eparation-\'Evaluation -- Une alternative au retour-arri\`ere -- Application au probl\`eme d'Open-Shop},
booktitle      = {Journ\'ees Francophones de Progammation en Logique et avec Contraintes (JFPLC'98)},
year           = 1998,
address        = {Nantes, France},
month          = may,
publisher      = {Herm\`es},
pages          = {231--250},
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/jussien-JFPLC98.pdf},
abstract       = {La plupart des recherches arborescentes utilis\'ees
en recherche op\'erationnelle pour r\'esoudre les probl\`emes
d'atelier sont des proc\'edures de s\'eparation-\'evaluation en
profondeur d'abord qui utilisent un backtrack chronologique
qui pr\'esente quelques inconv\'enients comme le thrashing. Ces
recherches arborescentes \'enum\`erent non pas sur des variables,
comme il est courant dans la communaut\'e Programmation par
contraintes, mais sur des contraintes et dans le cadre d'une minimisation.
Nous proposons dans cet article une technique de backtrack intelligent
adapt\'e \`a ces recherches arborescentes. Les r\'esultats obtenu sur
des probl\`emes d'Open-Shop montrent que notre technique est efficace
puisqu'elle a permis de r\'esoudre un Open-Shop ouvert \`a 10 jobs et 10 machines.}
}

Narendra Jussien, Olivier Lhomme

"About avoidable computations in Interval methods" , SCAN - IMACS/GAMM international symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, 1998

abstract, article [pdf, 49 KB]

@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},
kind           = {MISA},
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).}
}

Narendra Jussien, Olivier Lhomme

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

abstract, article [pdf, 165 KB]

@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},
kind           = {MISA},
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.}
}

Narendra Jussien

"A constraint relaxation system: DECorum" , Groupe de travail Programmation en Logique de l'AFCET (ALP France). Invité par les acteurs du projet ESPRIT (LTR) DiSCiPl (Debugging systems for Constraint Programming), 1997

abstract

@misc{jussien-afplc97,
author        = {Narendra Jussien},
title         = {A constraint relaxation system: {DECorum}},
howpublished  = {Groupe de travail \emph{Programmation en Logique} de l'AFCET (ALP France). Invit\'e par les acteurs du projet ESPRIT (LTR) DiSCiPl (\emph{Debugging systems for Constraint Programming})},
month         = jan,
year          = 1997,
kind           = {DIVERS},
abstract      = { Dans le cadre des probl\`emes dynamiques, il peut arriver que le
syst\`eme de contraintes devienne sur-contraint. Lorsqu'il est
imp\'eratif de fournir une solution, il faut accepter que certaines
contraintes ne soient pas respect\'ees. On parle alors de relaxation
de contraintes.

Le choix des contraintes \`a relaxer n'est pas chose ais\'ee. Il faut
tenir compte des pr\'ef\'erences de l'utilisateur et relaxer les
\emph{bonnes} contraintes.

Dans cet expos{\'e} nous pr\'esenterons le syst\`eme DECorum~:
l'int\'egration d'une m\'ethode de recherche particuli\`ere et d'un
syst\`eme de maintien de d\'eduction notre outil de d\'etermination
des contraintes \`a relaxer. Nous montrerons en particulier la
g\'en\'eralit\'e de notre approche et une impl\'ementation efficace
sur l'utilisation de l'arc-consistance sur les domaines finis. }
}

Narendra Jussien, Patrice Boizumault

"A Best First approach for solving over-constrained dynamic problems" , IJCAI'97, Poster - also available as RR 97-6-INFO, École des Mines de Nantes, 1997

abstract, article [pdf, 219 KB]

@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 -- also available as RR 97-6-INFO, \'Ecole des Mines de Nantes},
kind           = {MISA},
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.}
}

Narendra Jussien, Patrice Boizumault

"A Best First approach for solving over-constrained dynamic problems" , École des Mines de Nantes, technical report, no. 97-6-INFO, 1997

, article [pdf, 219 KB]

@TechReport{jussien-bestfirst-rr,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {A Best First approach for solving over-constrained dynamic problems},
institution    = {\'Ecole des Mines de Nantes},
year           = 1997,
type           = {Research Report},
number         = {97-6-INFO},
url            = {http://www.emn.fr/jussien/publications/RR97-6-INFO.pdf},
address        = {Nantes, France},
kind           = {RR},
}

Narendra Jussien, Olivier Lhomme, Patrice Boizumault

"Dynamic Backtracking with Constraint Propagation" , Journée du Pôle Contraintes et Programmation Logique, GDR Programmation du CNRS, 1997

abstract, article [pdf, 175 KB]

@InProceedings{jussien-dynamic,
author         = {Narendra Jussien and Olivier Lhomme and Patrice Boizumault},
title          = {Dynamic Backtracking with Constraint Propagation},
booktitle      = {Journ\'ee du P\^ole Contraintes et Programmation Logique},
organization   = {GDR Programmation du CNRS},
year           = 1997,
kind           = {DIVERS},
url            = {http://www.emn.fr/jussien/publications/jussien-GDR97.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
  behavior that consists in local modifications of the choices made up
  to the current situation. Thus the whole constraint programming
  community may derive benefits from its integration with a
  constraint propagation algorithm.},
}

Narendra Jussien, Patrice Boizumault

"Dynamic Backtracking with Constraint Propagation - Application to static and dynamic CSPs" , CP97 Workshop on The Theory and Practice of Dynamic Constraint Satisfaction, 1997

abstract, article [pdf, 283 KB]

@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,
kind           = {MIADR},
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.}
}

Narendra Jussien, Olivier Lhomme

"Dynamic Backtracking with Constraint Propagation - Application to numeric CSPs" , CP97 Workshop on The Theory and Practice of Dynamic Constraint Satisfaction, 1997

abstract, article [pdf, 202 KB]

@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,
kind           = {MIADR},
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}.}
}

Narendra Jussien

"Contribution à l'étude des systèmes dynamiques de contraintes - résolution de problèmes sur-contraints" , Séminaire du CREAM (Laboratoire de Recherche de l'Institut de Mathématiques Appliquées). Invité par Éric Pinson, 1997

@Misc{jussien-ima97,
author        = {Narendra Jussien},
title         = {Contribution {\`a} l'\'etude des syst\`emes dynamiques de contraintes -- r\'esolution de probl\`emes sur-contraints},
howpublished  = {S\'eminaire du CREAM (Laboratoire de Recherche de l'Institut de Math\'ematiques Appliqu\'ees). Invit\'e par \'Eric Pinson},
month         = mar,
year          = 1997,
kind          = {DIVERS},
}

Narendra Jussien, Patrice Boizumault

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

abstract, article [pdf, 320 KB]

@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,
kind           = {MISA},
url            = {http://www.emn.fr/jussien/publications/jussien-ILPS97.pdf},
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. }
}

Narendra Jussien, Patrice Boizumault

"Stratégies en Meilleur d'abord pour la relaxation de contraintes" , Journées Francophones de Progammation en Logique et avec Contraintes (JFPLC'97), pp. 149-165, Hermès, 1997

abstract, article [pdf, 335 KB]

@InProceedings{jussien-strategies,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {Strat\'egies en Meilleur d'abord pour la relaxation de contraintes},
booktitle      = {Journ\'ees Francophones de Progammation en Logique et avec Contraintes (JFPLC'97)},
year           = 1997,
pages          = {149--165},
address        = {Orl\'eans, France},
publisher      = {Herm\`es},
month          = may,
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/jussien-JFPLC97.pdf},
abstract       = {De nombreux probl\`emes r\'eels peuvent \^etre mod\'elis\'es \`a
  l'aide de la programmation par contraintes. Dans de nombreuses
  applications, l'environnement externe peut conduire \`a des
  \'evolutions sensibles du probl\`eme trait\'e au cours de la
  r\'esolution. Pour ces probl\`emes dynamiques, le syst\`eme de
  contraintes peut devenir inconsistant. Dans un tel cas, il est
  souhaitable de relaxer certaines contraintes du probl\`eme
  (d\'efinissant alors un sous-probl\`eme) afin de trouver une
  solution tout en satisfaisant au mieux l'utilisateur.  Pour cela,
  celui-ci doit sp\'ecifier ses pr\'ef\'erences sur les contraintes.

  Dans des travaux pr\'ec\'edents, nous avons propos\'e un outil pour
  \`a la fois identifier les contraintes \`a relaxer et efficacement
  en effacer leurs effets pass\'es. Dans cet article, nous proposons
  une m\'ethode de recherche de type \emph{meilleur d'abord} pour la
  relaxation de contraintes utilisant cet outil dont nous montrons la
  r\'ealisabilit\'e.  Nous pr\'esentons une s\'emantique
  op\'erationnelle de cette approche ainsi qu'une impl\'ementation
  dans le cadre des domaines finis.}
}

Narendra Jussien, Patrice Boizumault

"Stratégies en Meilleur d'abord pour la relaxation de contraintes" , École des Mines de Nantes, technical report, no. 97-5-INFO, 1997

@TechReport{jussien-strategies-rr,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {Strat\'egies en Meilleur d'abord pour la relaxation de contraintes},
institution    = {\'Ecole des Mines de Nantes},
year           = 1997,
type           = {Research Report},
number         = {97-5-INFO},
address        = {Nantes, France},
kind           = {RR},
}

Narendra Jussien

"Relaxation de Contraintes pour les problèmes dynamiques" , Université de Rennes I, PhD thesis, 1997

abstract, article [pdf, 1579 KB]

@PhdThesis{jussien-these,
author         = {Narendra Jussien},
title          = {Relaxation de Contraintes pour les probl\`emes dynamiques},
school         = {Universit\'e de Rennes I},
address        = {Rennes, France},
year           = 1997,
month          = {24 } # oct,
kind           = {THESE},
url            = {http://www.emn.fr/jussien/publications/jussien-THESIS.pdf},
abstract = {  La programmation par contraintes, carrefour de diverses disciplines,
  a montr\'e son int\'er\^et dans de nombreux domaines d'application.
  De nombreux probl\`emes r\'eels sont dynamiques~: le syst\`eme de
  contraintes les d\'efinissant n'est donc pas fig\'e. Pour r\'esoudre
  un probl\`eme dynamique, il faut assurer une certaine
  incr\'ementalit\'e et \^etre capable de traiter les syst\`emes 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\`ese, nous nous sommes int\'eress\'es \`a la
  d\'efinition d'un syst\`eme de relaxation de contraintes permettant
  de maintenir une propri\'et\'e donn\'ee dans un environnement
  dynamique.  Nous avons men\'e ces travaux depuis une pr\'esentation
  abstraite d'un tel syst\`eme jusqu'\`a son impl\'ementation.

   Nous pr\'esentons un sch\'ema algorithmique g\'en\'eral abstrait de
  la recherche d'une solution \`a un probl\`eme sur-contraint bas\'ee
  sur l'exploration en meilleur d'abord d'un espace de configurations.
  Nous en donnons trois instances pour traiter les contraintes
  lin\'eaires sur les rationnels, les {\em Constraint Satisfaction Problems} et
  les CSP num\'eriques. Les deux derni\`eres sont
  d\'efinies \`a l'aide d'un syst\`eme de maintien de d\'eduction dont
  la ma\^{\i}trise raisonn\'ee nous a permis de donner une
  impl\'ementation de ces instances ayant une \emph{bonne}
  complexit\'e~: le syst\`eme DECorum.

  Nous montrons, par le biais d'un certain nombre
  d'exp\'erimentations, que l'utilisation de DECorum permet de
  retrouver les r\'esultats classiques sur la transition de phase, de
  r\'esoudre raisonnablement des probl\`emes de grande taille et
  d'utiliser la structure du probl\`eme r\'esolu pour am\'eliorer la
  recherche.

  Enfin, nous proposons la contrainte one-of permettant de
  mod\'eliser et de r\'esoudre une disjonction de contraintes en
  tirant profit du m\'ecanisme d'exploration de DECorum. Nous
  validons l'int\'er\^et de la contrainte one-of sur des
  probl\`emes d'ordonnancement : les Open-Shop.}
}

Christelle Guéret, Narendra Jussien, Patrice Boizumault, Christian Prins

"Building University timetables using Constraint Logic Programming" , The Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, vol. 1153, pp. 130-145, Springer-Verlag, 1996

abstract, article [pdf, 399 KB]

@InProceedings{gueret-building-lncs,
author         = {Christelle Gu\'eret and Narendra Jussien and Patrice Boizumault and Christian Prins},
title          = {Building University timetables using {Constraint Logic Programming}},
editor         = {Edmund Burke and Peter Ross},
volume         = 1153,
series         = {Lecture Notes in Computer Science},
pages          = {130--145},
booktitle      = {The Practice and Theory of Automated Timetabling},
year           = 1996,
publisher      = {Springer-Verlag},
kind           = {CDL},
url            = {http://www.emn.fr/jussien/publications/gueret-LNCS96.pdf},
abstract       = {A timetabling problem can be defined as the scheduling of a
certain number of lectures, which are to be attended by a specific
group of students and given by a teacher, over a definite period of
time. Each lecture requires certain resources (rooms, overheads,\dots)
in limited number and must fulfill certain specific requirements. In
particular, automatic building of timetables is extremely difficult
because of the diversity of the constraints that must be taken into
account.

The most usual methods to solve this problem are inherited from
Operations Research such as graph coloring and mathematical
programming, from local search procedures such as simulated annealing
and Tabu search or from Genetic Algorithms. These well-known and widely
used methods have given good results. But, OR inherited methods generally lack
flexibility (i.e modifying the data may lead to the necessity of
reconsidering the initial model); moreover it is difficult to find a
model which includes all the constraints.  For local search methods
(where most of the constraints are put in the objective function) or
for Genetic Algorithms (where the constraints are active in the
fitness function), the user frequently obtains solutions by tuning
rather than by defining his own search strategy dedicated to the
problem.

The aim of this paper is to show how CLP is well suited
for solving Timetabling Problems. Particularly, the declarativity of
the CSP formalism improves the flexibility (heterogeneous constraints
can be directly handled).  Moreover, the CLP paradigm
gives the ability to rapidly design efficient search procedures.}
}

Narendra Jussien, Patrice Boizumault

"CSP dynamiques et Relaxation de Contraintes" , CNPC'96: deuxième Conférence Nationale sur la résolution pratique de Problèmes NP-Complets, CRID - Université de Bourgogne, Dijon, pp. 135-149, Teknea, 1996

abstract, article [pdf, 285 KB]

@InProceedings{jussien-csp,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {{CSP} dynamiques et {R}elaxation de {C}ontraintes},
publisher      = {Teknea},
booktitle      = {CNPC'96: deuxi\`eme Conf\'erence Nationale sur la r\'esolution pratique de Probl\`emes NP-Complets},
year           = 1996,
organization   = {CRID -- Universit\'e de Bourgogne, Dijon},
address        = {Dijon, France},
pages          = {135--149},
month          = mar,
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/jussien-CNPC96.pdf},
abstract       = {Nous pr\'esentons dans cet article un syst\`eme de
  relaxation de
  contraintes sur les CSP sur-contraints. Ce syst\`eme utilise un
  m\'ecanisme de maintien de d\'eductions bas\'e sur l'enregistrement
  de justifications pour chaque action (retrait de valeur, retrait de
  contrainte, identification de contradiction). Notre syst\`eme  de
  relaxation de contraintes peut alors non seulement \'eviter de
  recommencer la recherche \`a z\'ero apr\`es chaque modification du
  syst\`eme de contraintes mais aussi identifier de mani\`ere
  pr\'ecise un ensemble de contraintes \`a relaxer.}
}

Narendra Jussien, Patrice Boizumault

"CSP dynamiques et Relaxation de Contraintes" , École des Mines de Nantes, technical report, no. 96-3-INFO, 1996

@TechReport{jussien-csp-rr,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {{CSP} dynamiques et {R}elaxation de {C}ontraintes},
institution    = {\'Ecole des Mines de Nantes},
year           = 1996,
type           = {Research Report},
number         = {96-3-INFO},
address        = {Nantes, France},
kind           = {RR},
}

Narendra Jussien

"Relaxation de Contraintes en PLC" , Séminaire du CREAM (Laboratoire de Recherche de l'Institut de Mathématiques Appliquées). Invité par Éric Pinson, 1996

@Misc{jussien-ima96,
author        = {Narendra Jussien},
title         = {Relaxation de Contraintes en {PLC}},
howpublished  = {S\'eminaire du CREAM (Laboratoire de Recherche de l'Institut de Math\'ematiques Appliqu\'ees). Invit\'e par \'Eric Pinson},
month         = jan,
year          = 1996,
kind          = {DIVERS},
}

Narendra Jussien, Patrice Boizumault

"Implementing Constraint Relaxation over Finite Domains using ATMS" , Over-Constrained Systems, Lecture Notes in Computer Science, no. 1106, pp. 265-280, Springer-Verlag, 1996

abstract, article [pdf, 201 KB]

@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},
kind           = {CDL},
url            = {http://www.emn.fr/jussien/publications/jussien-OCSCP95.pdf},
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\`ere's DnAC4).}
}

Narendra Jussien, Patrice Boizumault

"Maintien de Déduction pour la Relaxation de Contraintes" , Journées Francophones de Progammation en Logique et avec Contraintes (JFPLC'96), pp. 239-253, Hermès, 1996

abstract, article [pdf, 263 KB]

@InProceedings{jussien-maintien,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {Maintien de D\'eduction pour la Relaxation de Contraintes},
booktitle      = {Journ\'ees Francophones de Progammation en Logique et avec Contraintes (JFPLC'96)},
year           = 1996,
address        = {Clermont-Ferrand, France},
publisher      = {Herm\`es},
pages          = {239--253},
month          = jun,
kind           = {MNSA},
url            = {http://www.emn.fr/jussien/publications/jussien-JFPLC96.pdf},
abstract       = {Nous pr\'esentons dans ce papier un Syst\`eme de Maintien de
  D\'eduction afin de r\'ealiser un syst\`eme de Relaxation de
  Contraintes pour les CSPs sur-contraints. Notre proposition n'est
  pas li\'ee \`a une m\'ethode donn\'e de r\'esolution de CSP et
  peut \^etre adapt\'ee \`a tout type de solveur sur les domaines
  finis.  Nous donnons des r\'esultats exp\'erimentaux obtenus gr\^ace
  au syst\`eme DECorum (Deduction-based Constraint Relaxation
  Management), une impl\'ementation de notre DMS coupl\'e \`a
  l'algorithme AC5.}
}

Narendra Jussien, Patrice Boizumault

"Maintien de Déduction pour la Relaxation de Contraintes" , École des Mines de Nantes, technical report, no. 96-4-INFO, 1996

@TechReport{jussien-maintien-rr,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {Maintien de D\'eduction pour la Relaxation de Contraintes},
institution    = {\'Ecole des Mines de Nantes},
year           = 1996,
type           = {Research Report},
number         = {96-4-INFO},
address        = {Nantes, France},
kind           = {RR},
}

Narendra Jussien, Patrice Boizumault

"Une sémantique opérationnelle pour la relaxation de contraintes" , Journée du Pôle Contraintes et Programmation Logique, GDR Programmation du CNRS, 1996

, article [pdf, 170 KB]

@InProceedings{jussien-semantique,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {Une s\'emantique op\'erationnelle pour la relaxation de contraintes},
booktitle      = {Journ\'ee du P\^ole Contraintes et Programmation Logique},
organization   = {GDR Programmation du CNRS},
address        = {Orl\'eans, France},
year           = 1996,
month          = nov,
kind           = {DIVERS},
url            = {http://www.emn.fr/jussien/publications/jussien-GDR96.pdf},
}

Christelle Guéret, Narendra Jussien, Patrice Boizumault, Christian Prins

"Building University timetables using Constraint Logic Programming" , ICPTAT'95: First international Conference on the Practice and Theory of Automated Time Tabling, pp. 393-408, 1995

abstract, article [pdf, 399 KB]

@inproceedings{gueret-building,
author          = {Christelle Gu\'eret and Narendra Jussien and Patrice Boizumault and Christian Prins},
title           = {Building University timetables using {Constraint Logic
          Programming}},
booktitle       = {{ICPTAT'95}: First international Conference on the Practice and Theory of Automated Time Tabling},
year            = 1995,
month           = aug,
address         = {Edinburgh, United Kingdom},
pages           = {393--408},
kind            = {MISA},
url             = {http://www.emn.fr/jussien/publications/gueret-ICPTAT95.pdf},
abstract        = {A timetabling problem can be defined as the scheduling of a
certain number of lectures, which are to be attended by a specific
group of students and given by a teacher, over a definite period of
time. Each lecture requires certain resources (rooms, overheads,\dots)
in limited number and must fulfill certain specific requirements. In
particular, automatic building of timetables is extremely difficult
because of the diversity of the constraints that must be taken into
account.

The most usual methods to solve this problem are inherited from
Operations Research such as graph coloring and mathematical
programming, from local search procedures such as simulated annealing
and Tabu search or from Genetic Algorithms. These well-known and widely
used methods have given good results. But, OR inherited methods generally lack
flexibility (i.e modifying the data may lead to the necessity of
reconsidering the initial model); moreover it is difficult to find a
model which includes all the constraints.  For local search methods
(where most of the constraints are put in the objective function) or
for Genetic Algorithms (where the constraints are active in the
fitness function), the user frequently obtains solutions by tuning
rather than by defining his own search strategy dedicated to the
problem.

The aim of this paper is to show how CLP is well suited
for solving Timetabling Problems. Particularly, the declarativity of
the CSP formalism improves the flexibility (heterogeneous constraints
can be directly handled).  Moreover, the CLP paradigm
gives the ability to rapidly design efficient search procedures.}
}

Narendra Jussien, Patrice Boizumault

"Implementing Constraint Relaxation over Finite Domains using ATMS" , OCS'95: Workshop on Over-Constrained Systems at CP'95, 1995

abstract, article [pdf, 201 KB]

@inproceedings{jussien-implementing,
author         = {Narendra Jussien and Patrice Boizumault},
title          = {Implementing Constraint Relaxation over Finite Domains using {ATMS}},
booktitle      = {OCS'95: Workshop on Over-Constrained Systems at CP'95},
address        = {Cassis, France},
month          = {18 } # sep,
year           = 1995,
kind           = {MIADR},
url            = {http://www.emn.fr/jussien/publications/jussien-OCSCP95.pdf},
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\`ere's DnAC4).}
}

Patrice Boizumault, Christelle Guéret, Narendra Jussien

"Efficient labeling and Constraint Relaxation for Solving Time Tabling Problems" , Proceedings of the 1994 ILPS post-conference workshop on Constraint Languages/Systems and their use in Problem Modeling : Volume 1 (Applications and Modelling), Technical Report ECRC-94-38, 1994

, article [pdf, 107 KB]

@inproceedings{boizumault-efficient,
author          = {Patrice Boizumault and Christelle Gu\'eret and Narendra Jussien},
title           = {Efficient labeling and Constraint Relaxation for Solving Time Tabling Problems},
booktitle       = {Proceedings of the 1994 ILPS post-conference workshop on Constraint Languages/Systems and their use in Problem Modeling : Volume 1 (Applications and Modelling)},
editor          = {Pierre Lim and Jean Jourdan},
series          = {Technical Report ECRC-94-38},
address         = {ECRC, Munich, Germany},
month           = nov,
year            = 1994,
kind            = {MIADR},
url             = {http://www.emn.fr/jussien/publications/boizumault-WILPS94.pdf}
}

Patrice Boizumault, Christelle Guéret, Narendra Jussien

"Énumération et relaxation en Programmation Logique avec Contraintes" , Rencontres sur la résolution pratique des problèmes NP-complets, 1994

@inproceedings{boizumault-enumeration,
author          = {Patrice Boizumault and Christelle Gu\'eret and Narendra Jussien},
title           = {{\'E}num\'eration et relaxation en Programmation Logique avec Contraintes},
booktitle       = {Rencontres sur la r\'esolution pratique des probl\`emes NP-complets},
year            = 1994,
month           = sep,
kind            = {MNSA},
address         = {Montpellier, France}
}

Narendra Jussien

"Relaxation de Contraintes - Études et perspectives" , Institut de Mathématiques Appliquées, master's thesis, 1994

abstract

@MastersThesis{jussien-dess,
author         = {Narendra Jussien},
title          = {Relaxation de Contraintes -- \'Etudes et perspectives},
school         = {Institut de Math{\'e}matiques Appliqu{\'e}es},
address        = {Angers, France},
year           = {1994},
month          = jun,
kind           = {THESE},
abstract       = {Nous pr{\'e}sentons une {\'e}tude sur les m{\'e}thodes de
                  relaxation de contraintes. Ce probl{\`e}me qui consiste
                  {\`a} extraire un sous-probl{\`e}me r{\'e}alisable d'un probl{\`e}me
                  de satisfaction de contraintes n'ayant pas de
                  solution, n'a toujours pas re\c{c}u de proposition de
                  r{\'e}solution satisfaisante. C'est pourquoi, apr{\`e}s
                  avoir pr{\'e}sent{\'e} un {\'e}tat de l'art dans le domaine, {\`a}
                  travers une pr{\'e}sentation des principes fondamentaux
                  et des principales m{\'e}thodes propos{\'e}es, nous ferons
                  une proposition qui tend {\`a} r{\'e}unifier deux domaines
                  fondamentaux~: la recherche de responsables lors
                  d'un {\'e}chec Prolog et la r{\'e}alisation d'un solveur de
                  contraintes incr{\'e}mental permettant le retrait et
                  l'ajotu de contraintes en cours de r{\'e}solution. Nous
                  baliserson notre travail {\`a} l'aide d'impl{\'e}mentations
                  d'une grande partie des m{\'e}thodes propos{\'e}es et seront
                  guid{\'e}s par un fil rouge~: le probl{\`e}me de la
                  conf{\'e}rence. Ce probl{\`e}me nous servira {\`a} illustrer et
                  commenter les m{\'e}thodes propos{\'e}es. Ce travail est une
                  porte ouverte sur des d{\'e}veloppements futurs dans ce
                  domaine. Il se veut aussi un point de jonction entre
                  la Recherche Op{\'e}rationnelle et la Programmation
                  Logique sous Contraintes.},
}

Narendra Jussien, Vincent Verger, Yvon L'Hospitalier, Bernard Augereau, Patrick Gillet

"Le système expert NEREIS des annélides polychètes de France (ordre des Phyllodocida, Amphinomida, Spintherida et Eunicida)" , in: "Canadian Journal of Zoology - Revue Canadienne de Zoologie", vol. 72, no. 12, pp. 2255-2260, 1994

abstract, article [tar.gz, 688 KB]

@Article{jussien-nereis,
author         = {Narendra Jussien and Vincent Verger and Yvon L'Hospitalier and Bernard Augereau and Patrick Gillet},
title          = {Le syst\`eme expert {NEREIS} des ann\'elides polych\`etes de {F}rance (ordre des {P}hyllodocida, {A}mphinomida, {S}pintherida et {E}unicida)},
journal        = {Canadian Journal of Zoology -- Revue Canadienne de Zoologie},
year           = 1994,
volume         = 72,
number         = 12,
pages          = {2255--2260},
month          = dec,
kind           = {RIAS},
url            = {http://www.emn.fr/jussien/publications/jussien-RCZ.tar.gz},
abstract       = {La \emph{Faune de France} des ann\'elides polych\`etes
 errantes de Fauvel (1923) ne comporte que 15 familles
(Histribdellidae et Ichthyotomidae exclues). Actuellement, on compte
37 familles pr\'esentes sur les c\^otes de France; il a donc \'et\'e
n\'ecessaire de r\'eviser la cl\'e de d\'etermination des familles pour
r\'ealiser un logiciel permettant un diagnostic rapide des taxa. Le
g\'en\'erateur utilis\'e, Xi Plus, est \'edit\'e par Syspertec.}
}

Narendra Jussien

"Programmation Logique sous Contraintes et Problèmes d'ordonnancements" , Petit séminaire de l'IRISA (Rennes). Invité par Yves Bekkers, 1993

@Misc{jussien-irisa93,
author        = {Narendra Jussien},
title         = {Programmation Logique sous Contraintes et Probl{\`e}mes d'ordonnancements},
howpublished  = {Petit s\'eminaire de l'IRISA (Rennes). Invit\'e par Yves Bekkers},
month         = jul,
year          = 1993,
kind          = {DIVERS},
}

Narendra Jussien

"Variations en Programmation Logique sous Contraintes" , 1993

@Misc{jussien-maitrise,
author        = {Narendra Jussien},
title         = {Variations en {P}rogrammation {L}ogique sous {C}ontraintes},
school        = {Institut de Math{\'e}matiques Appliqu{\'e}es},
year          = {1993},
type          = {M{\'e}moire de Ma{\^\i}trise},
address       = {Angers, France},
kind          = {RDS},
}

Narendra Jussien, Vincent Verger

"NEREIS : Système expert de reconnaissance d'Annélides Polychètes" , 1992

@Misc{jussien-licence,
author        = {Narendra Jussien and Vincent Verger},
title         = {{NEREIS}~: Syst{\`e}me expert de reconnaissance d'{A}nn{\'e}lides {P}olych{\`e}tes},
school        = {Institut de Math{\'e}matiques Appliqu{\'e}es},
year          = {1992},
type          = {M{\'e}moire de Licence},
address       = {Angers, France},
kind          = {RDS},
}

Narendra Jussien, Vincent Verger, Patrick Gillet, Yvon L'Hospitalier, Bernard Augereau

"NEREIS : un système expert de reconnaissance d'Annélides Polychètes" , 4ème Conférence Internationale sur les Annélides Polychètes, (Poster), 1992

@InProceedings{jussien-nereis-poster,
author         = {Narendra Jussien and Vincent Verger and Patrick Gillet and Yvon L'Hospitalier and Bernard Augereau},
title          = {NEREIS~: un syst\`eme expert de reconnaissance d'Ann\'elides Polych\`etes},
booktitle      = {4\`eme Conf\'erence Internationale sur les Ann\'elides Polych\`etes},
year           = 1992,
address        = {Angers, France},
month          = jul,
note           = {(Poster)},
kind           = {MIADR},
}