narendra jussien
narendra jussien | | professeur, équipe contraintesécole des mines de nantes - lina |
» accueil » recherche » publications » par année » résumés
"Problème SAT : Progrès et défis"
, Collection Programmation par Contraintes dirig{\'e}e par Narendra Jussien, Hermès Science, 2008 référence, 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.
"Décomposition combinatoires et applications industrielles"
, Collection Programmation par Contraintes dirig{\'e}e par Narendra Jussien, Hermès Science, 2007 référence, 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.
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 référence, 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), 2008 référence, 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 référence, article
[pdf, 111 KB] 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.
"Learning from the past to dynamically improve search"
, Learning and Intelligent OptimizatioN, 2007 référence, article
[pdf, 204 KB] 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 référence, 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 référence, article
[pdf, 111 KB] 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.
É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 référence, 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.
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", Elsevier, 2007 référence, 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.
Frédéric Benhamou, Narendra Jussien, Barry O'Sullivan "Trends in Constraint Programming"
, ISTE, 2007 référence, 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.
"A to Z of sudoku"
, ISTE, 2007 référence, 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 référence, 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 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.
"PrŽcis de Sudoku"
, Hermes Science, 2006 référence, 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 référence, 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 référence, 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.
"Logique(s), langages formels et complexité pour l'informatique"
, Hermes Science, 2006 référence, 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 référence, 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 référence, 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 référence, 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.
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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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.
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 référence, 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.
"Constraint Programming for Software Engineering"
, Fifth Congress of Logic applied to Technology (LAPTEC'05), 2005 référence, 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).
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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 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 référence, 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 référence, 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.
"The versatility of using explanations within constraint programming"
, École des Mines de Nantes, technical report, no. 03-04-INFO, 2003 référence, 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 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 référence, 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 référence, article
[pdf, 277 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.
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 référence, 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 référence, 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.
"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 référence, 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 référence, 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.
"Programmation par contraintes pour les technologies logicielles"
, Colloque GEMSTIC'03 : l'industrie du logiciel - outils et méthodologies, Groupe des Écoles des Mines, 2003 référence, 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 référence, 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 référence, 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 référence, 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 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 référence, 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 référence, article
[ps, 430 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.
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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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.
"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 référence, 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.
"e-constraints: explanation-based Constraint Programming"
, CP01 Workshop on User-Interaction in Constraint Satisfaction, 2001 référence, 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.
"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 référence, 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.
"User-friendly explanations for constraint programming"
, ICLP'01 11th Workshop on Logic Programming Environments (WLPE'01), 2001 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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 référence, 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.
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 référence, article
[pdf, 408 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, 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 référence, 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 référence, 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 référence, 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, 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 référence, article
[pdf, 219 KB] 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, Olivier Lhomme, Patrice Boizumault "Dynamic Backtracking with Constraint Propagation"
, Journée du Pôle Contraintes et Programmation Logique, GDR Programmation du CNRS, 1997 référence, article
[pdf, 175 KB] Recent works on constraint relaxation
provided the DECorum system
(Deduction-based Constraint Relaxation Management). In this paper,
we show how the ideas developed in that system can be used in order
to integrate Constraint Propagation within the Dynamic Backtracking
algorithm (Ginsberg, 1993). Dynamic Backtracking
replaces the backtracking process by a much less blind
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 référence, article
[pdf, 283 KB] Recent works on constraint relaxation provided the
DECorum system (Ded