narendra jussien

professeur, équipe contraintes

école des mines de nantes - lina

» home » research » publications » by year » abstracts

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

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

Cet ouvrage analyse les techniques actuelles du problème de satisfiabilité propositionnelle (SAT) et étudie ses défis majeurs. Ce problème fondamental se trouve au coe ur de la théorie de la complexité et intervient dans de nombreux domaines tels que la logique mathématique, la déduction automatique et la programmation par contraintes. Les avancées spectaculaires obtenues sur la résolution pratique de ce problme NP-Complet de référence font aujourd'hui de SAT un formalisme puissant de modélisation et de résolution de nombreux problèmes importants incluant la vérification de matériel et de logiciels. Ces résultats ont bénéficié d'une synergie forte entre la théorie, les développements algorithmiques et les applications industrielles. Problème SAT, progrès et défis couvre divers aspects qui vont de la théorie aux applications industrielles en passant par les techniques modernes de résolution de SAT. Il constitue une référence idéale pour l'étudiant, le chercheur ou l'ingénieur. Ce large public y trouvera donc un exposé clair et détaillé des différentes facettes d'un formalisme générique de résolution de problèmes difficiles.

Thierry Benoist

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

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

Décompositions combinatoires et applications industrielles propose des schémas de décomposition originaux applicables à la résolution de problmes combinatoires de grande taille. Prenant appui sur les outils classiques de la recherche opérationnelle comme l'optimisation linéaire, la programmation par contraintes ou les méta-heuristiques, cet ouvrage développe des techniques de décomposition génériques souvent hybrides. Ces algorithmes sont appliqués sur des cas réels, issus de plusieurs années de pratique de la recherche opérationnelle au sein d'un grand groupe industriel diversifié. Neuf applications concrètes sont ainsi prŽsentées, dans les domaines de la construction, de la téléphonie et de la télévision.

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, Springer-Verlag, 2008

reference

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

reference, article [pdf, 430 KB]

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

reference, article [pdf, 584 KB]

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

reference, article [pdf, 861 KB]

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.

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

reference, article [pdf, 233 KB]

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

Hadrien Cambazard, Narendra Jussien

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

reference, article [pdf, 111 KB]

Narendra Jussien

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

reference, article [pdf, 204 KB]

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

reference, article [pdf, 105 KB]

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.

Hadrien Cambazard, Narendra Jussien

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

reference, article [pdf, 111 KB]

É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

reference, article [pdf, 21 KB]

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.

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

"Trends in Constraint Programming" , ISTE, 2007

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

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

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

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 öne 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 ëxpert" 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.

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

reference, article [pdf, 1372 KB]

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.

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

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

reference

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

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

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

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

reference, article [pdf, 655 KB]

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.

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

reference, article [pdf, 254 KB]

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

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

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.

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

reference, article [pdf, 413 KB]

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

reference, article [pdf, 215 KB]

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

reference, article [pdf, 193 KB]

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 (\textttdecision-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

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

reference

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

reference, article [pdf, 347 KB]

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.

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

reference, article [pdf, 214 KB]

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

reference, article [pdf, 331 KB]

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

reference, article [pdf, 733 KB]

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

reference, article [pdf, 210 KB]

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

reference

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

reference, article [pdf, 429 KB]

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

reference, article [pdf, 46 KB]

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

Narendra Jussien

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

reference, article [zip]

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

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

reference, article [pdf, 268 KB]

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

reference, article [pdf, 275 KB]

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

reference, article [pdf, 276 KB]

En physique des milieux granulaires, des méthodes de simulations numériques sont utilisées notamment pour tenter de comprendre la connexion entre les grains et les structures mécaniques macroscopiques dans le tas. Nous avons proposé une modélisation multi-agent originale qui permet de résoudre des tas de sable bidimensionnels à l'équilibre statique. Mais, le caractère stochastique de la recherche locale de solutions d'équilibre pose le problème de la couverture de l'espace des solutions par cet algorithme. La résolution de ce problème par une approche purement CSP se révèle difficile du fait de la taille gigantesque du problème à traiter. Nous proposons donc de mettre en oeuvre des techniques de CSP comme comportements de résolution local de l'é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

reference, article [pdf, 336 KB]

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.

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

reference, article [pdf, 310 KB]

La décomposition de Benders a été utilisée avec succès pour de nombreuses problématiques en Recherche Opérationnelle. Nous présentons ici, la mise en oeuvre d'une technique de coopération fondée sur une généralisation du cadre classique de la décomposition de Benders et appliquée à la résolution d'un problème d'allocation de tâches temps réel (ordonnancement préemptif à prioritées fixes pour des tâches périodiques). Un problème ma\^\itre, résolu par programmation par contraintes coopère avec un sous-problème analytique. Celui-ci est traité par des techniques issues des travaux de la communauté temps-réel et couplées avec un algorithme adhoc de détection de conflits : QuickXplain. Les contraintes et nogoods appris au cours de la recherche jouent un rô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

reference, article [pdf, 79 KB]

Nous présentons dans cet article comment fournir des explications pour des contraintes globales basées sur le flot. Nous étudions notamment une contrainte de maintien d'un flot dans un réseau et les explications en ce qui concerne le flot maximal, minimal ainsi que l'existence d'un flot compatible. Après un parallèle avec les explications pour les contraintes all_diff et gcc, nous proposons quelques résultats mettant en avant le gain en retour arrière de cette méthode et tentons d'évaluer le gain en temps que de telles explications peuvent apporter.

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

reference

Guillaume Rochart, Narendra Jussien

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

reference, article [pdf, 218 KB]

Nous montrons dans cet article comment étendre une contrainte globale, stretch, pour l'utiliser dans un contexte expliqué. Ceci se traduit notamment par la production d'explications précises pour chacune des décisions prises lors du filtrage. Les expérimentations montrent une amélioration notable de la résolution de problèmes mettant en oeuvre une telle contrainte.

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

reference, article [pdf, 444 KB]

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

reference

La programmation par contraintes est un sujet de recherche qui tire profit de nombreuses autres disciplines : mathématiques discrètes, analyse numérique, intelligence artificielle, recherche opérationnelle et calcul formel. Elle a prouvé son intérêt et son efficacité dans de nombreux domaines : optimisation combinatoire, ordonnancement, finance, simulation et synthèse de composants, diagnostic de panne, biologie moléculaire, ou encore problèmes géométriques. Néanmoins, un certain nombre de limitations et de difficultés ont été identifiées dans le domaine : conception d'algorithmes génériques et stables, traitement des problèmes dynamiques, accessibilité 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ésenter un tableau général des explications (définition, génération et utilisations) mais aussi montrer comment leur utilisation permet de contribuer à lever certains des problèmes ouverts en programmation par contraintes. Nous présentons aussi une démarche générale de résolution de problème dans un environnement expliqué. Enfin, nous montrons comment ce nouveau sujet semble promis à 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

reference, article [pdf, 608 KB]

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

Gérard Verfaillie, Narendra Jussien

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

reference, article []

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

reference, article [pdf, 132 KB]

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

reference, article [pdf, 277 KB]

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

reference, article [pdf, 316 KB]

Nous montrons dans cet article comment étendre une contrainte globale, stretch, pour l'utiliser das un contexte expliqué. Ceci se traduit notamment par la production d'explications précises pour chacune des décisions prises lors du filtrage. Les expérimentations montrent une amélioration notable de la résolution de problè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

reference, article [pdf, 286 KB]

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

reference, article [pdf, 182 KB]

La programmation logique est enseignée à l'École des Mines de Nantes depuis 1994. Après une augmentation du volume horaire en 1998 (de 15 à 30 heures), le contenu du cours a évolué pour proposer un cheminement plus complet depuis la logique formelle jusqu'à la programmation en logique. Ce document présente l'organisation du cours tel qu'il est dispensé 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

reference, article [pdf, 131 KB]

Cet article présente des outils permettant à un utilisateur de la programmation par contraintes de développer interactivement une application. L'implantation de ces outils repose sur l'utilisation des explications dite k-pertinentes. Un exemple est donné pour illustrer les concepts et mettre en avant différentes situations concrètes d'utilisation de nos outils.

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

reference, article [pdf, 124 KB]

La programmation par contraintes, discipline au carrefour de l'intelligence artificielle, de la recherche opérationnelle et de l'analyse numérique a fait ses preuves pour la résolution de problèmes combinatoires complexes dans le domaine de l'aide à la décision. De nouveaux champs d'applications apparaissent, en particulier dans le domaine du génie logiciel. Au travers de quelques exemples (notamment l'identification et la correction de motifs de conception approchés et la ré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é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

reference, article [pdf, 149 KB]

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.

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

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

reference, article [pdf, 134 KB]

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

reference, article [pdf, 116 KB]

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

reference, article []

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

reference, article [pdf, 268 KB]

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

reference, article [ps, 430 KB]

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

reference, article [pdf, 114 KB]

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

reference, article [pdf, 349 KB]

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.

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

reference, article [pdf, 262 KB]

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.

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

reference, article [pdf, 170 KB]

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

reference, article [pdf, 232 KB]

Ginsberg et McAllester ont montré que les algorithmes de recherche de solution systématiques et non systématiques pouvaient être très proches. Dans cet article, nous souhaitons aller plus loin vers la compréhension des relations entre les approches systématiques et non-systématiques en introduisant le modèle \textbfPLM. Nous présentons un algorithme générique de recherche pour résoudre des \csp\ et nous montrons que de nombreux algorithmes de résolution peuvent se décomposer en utilisant un ensemble restreint de primitives. La connaissance de ces primitives permet non seulement de comparer plus aisément les algorithmes de recherche mais aussi de définir de nouveaux algorithmes.

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

reference, article [pdf, 249 KB]

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

reference, article [pdf, 203 KB]

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

reference, article [pdf, 174 KB]

Dans ce papier, nous présentons un ensemble d'outils pour fournir des explications conviviales dans un système de programmation par contraintes avec explications. L'idée est de représenter les contraintes d'un problème sous forme hiérarchique (un arbre). Les utilisateurs sont alors représentés comme un ensemble de noeuds compréhensibles dans cet arbre (une coupe). Les explications classiques (les ensembles de contraintes du système) doivent juste être projetées sur cette représentation pour être compréhensibles par n'importe quel utilisateur. Nous présentons ici les intérêts principaux de cette idé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

reference, article [pdf, 269 KB]

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

reference, article [pdf , 339 KB]

Les patrons de conception décrivent des micro-architectures qui résolvent des problèmes architecturaux récurrents. Il est important d'identifier ces micro-architectures lors de la maintenance des programmes orientés objets. Mais ces micro-architectures apparaissent souvent sous des formes dégradées dans le code source. Nous présentons une application de la programmation par contraintes avec explications pour l'identification de ces micro-architectures dégradé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

reference, article [pdf, 222 KB]

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.

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

reference, article [pdf, 62 KB]

La programmation par contraintes a maintenant démontré son intérêt et ses capacités à la résolution de problèmes très complexes. Du fait de ces résultats, de nouvelles fontionnalités sont maintenant demandées aux systèmes de résolution : l'intéractivité, la capacité d'explication du raisonnement, le débogage adapté

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

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

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

Narendra Jussien

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

reference, article [pdf, 227 KB]

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

"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

reference, article [pdf, 263 KB]

Nous présentons dans cet article notre expérience dans le domaine de l'utilisation des explications dans le cadre de la programmation par contraintes. Nous présentons aussi bien l'implémentation d'un système d'explications que les diverses utilisations que l'on peut en faire. Nous présentons en particulier, outre des utilisations classiques pour le débogage ou la prise en compte de la dynamicité, une utilisation plus enfouie qui nous conduit à proposer une nouvelle forme de programmation : la programmation par contraintes avec explications.

Narendra Jussien, Samir Ouis

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

reference, article [pdf, 285 KB]

In this paper, we introduce a set of tools for providing user-friendly explanations in an explanation-based constraint programming system. The idea is to represent the constraints of a problem as an hierarchy (a tree). Users are then represented as a cut in that tree. Classical explanations (sets of constraints) just need to get projected on that representation in order to be understandable by any user. We present here the main interests of this idea.

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

reference, article [pdf, 16 KB]

Dans le domaine militaire, la projection de forces consiste à envoyer le plus rapidement possible, en utilisant les moyens mis à disposition, des matériels en différents théâtres d'opérations tout en respectant un certain nombre de contraintes. Un tel déploiement nécessite une étape consistant à charger les moyens de transport (des avions dans notre cas) avec le matériel concerné. L'objectif du travail présenté ici est de réaliser un outil automatisé qui réalise cette opération en cherchant à minimiser le nombre total de trajets pour acheminer tout le matériel.

Christelle Guéret, Narendra Jussien, Christian Prins

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

reference, article [pdf, 146 KB]

Only two branch-and-bound methods have been published so far for the Open-Shop problem. The best one has been proposed by Brucker et al. But some square problems from size 7 are still unsolved by it.

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

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

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

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

reference, article [pdf, 94 KB]

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

reference, article [pdf, 275 KB]

La plupart des algorithmes de recherche complets pour les Problèmes de Satisfaction de Contraintes (csp) sont basés sur l'algorithme Backtrack Standard. Deux améliorations majeures de cet algorithme de base ont été proposées : premièrement, intégrer un mécanisme de propagation des contraintes comme dans l'algorithme mac qui maintient la consistance d'arc durant la recherche ; deuxièmement, procéder à des retours arrières intelligents afin d'éviter de tomber plusieurs fois dans les mêmes impasses en mémorisant des nogoods comme dans Conflict-directed BackJumping (cbj) ou dans Dynamic Backtracking (dbt). Des intégrations de mécanismes de propagation des contraintes dans des algorithmes de retours arrières intelligents ont déjà été proposées comme mac-cbj qui maintient la consistance d'arc dans cbj. Cependant, Bessière et Régin ont montré que mac-cbj était très rarement meilleur que mac. Mais nous pensons que les mauvais résultats de mac-cbj sont plus liés au fait que cbj ne parvient pas à éviter le thrashing\footnoteOn dit qu'il y a thrashing quand on refait à de nombreuses reprises le même travail d'instanciation à cause du principe du backtrack qui ne revient pas nécessairement sur les causes de l'échec. qu'au coût de la gestion des nogoods.

Cet article décrit et étudie mac-dbt qui maintient la consistance d'arc dans dbt. Des expérimentations montrent que mac-dbt est capable de résoudre de très grands problèmes et qu'il demeure très stable quand la taille des problèmes augmente. De plus, mac-dbt a de meilleurs résultats que mac sur les problèmes aléatoires structurés que nous avons générés.

Narendra Jussien, Romuald Debruyne, Patrice Boizumault

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

reference, article [pdf, 171 KB]

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

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

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

reference, article [pdf, 216 KB]

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

reference, article [pdf, 213 KB]

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.

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

reference, article [pdf, 172 KB]

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, Olivier Lhomme

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

reference, article [pdf, 213 KB]

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

reference, article [pdf, 408 KB]

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

reference, article [pdf, 358 KB]

La plupart des recherches arborescentes utilisées en recherche opérationnelle pour résoudre les problèmes d'atelier sont des procédures de séparation-évaluation en profondeur d'abord qui utilisent un backtrack chronologique qui présente quelques inconvénients comme le thrashing. Ces recherches arborescentes énumèrent non pas sur des variables, comme il est courant dans la communauté 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é à ces recherches arborescentes. Les résultats obtenu sur des problèmes d'Open-Shop montrent que notre technique est efficace puisqu'elle a permis de résoudre un Open-Shop ouvert à 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

reference, article [pdf, 49 KB]

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

reference, article [pdf, 165 KB]

In this paper, a new search technique over numeric CSPs is presented: dynamic domain splitting. The usual search technique over numeric CSPs is a dichotomic search interleaved with a consistency filtering, which is called domain splitting. This paper proposes to replace chronological backtracking at the core of domain splitting by a non destructive backtracking technique.

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

reference

Dans le cadre des problèmes dynamiques, il peut arriver que le système de contraintes devienne sur-contraint. Lorsqu'il est impératif de fournir une solution, il faut accepter que certaines contraintes ne soient pas respectées. On parle alors de relaxation de contraintes.

Le choix des contraintes à relaxer n'est pas chose aisée. Il faut tenir compte des préférences de l'utilisateur et relaxer les bonnes contraintes.

Dans cet exposé nous présenterons le système DECorum : l'intégration d'une méthode de recherche particulière et d'un système de maintien de déduction notre outil de détermination des contraintes à relaxer. Nous montrerons en particulier la généralité de notre approche et une implémentation 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