narendra jussien

professeur, équipe contraintes

école des mines de nantes - lina

» home » research » publications » by year » references

Lakhdar Sa"is

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

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

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

Thierry Benoist

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

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

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

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

abstract

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

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

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

abstract, article [pdf, 430 KB]

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

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

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

abstract, article [pdf, 584 KB]

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

Narendra Jussien, Guillaume Rochart, Xavier Lorca  

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

abstract, article [pdf, 861 KB]

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

Émilie Grellier, Pierre Dejax, Narendra Jussien

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

, article [pdf, 93 KB]

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

Charlotte Truchet, Damien Noguès, Narendra Jussien  

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

abstract, article [pdf, 233 KB]

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

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

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

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

Christelle Guéret, Narendra Jussien

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

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

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

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

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

, article [pdf, 386 KB]

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

Hadrien Cambazard, Narendra Jussien

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

abstract, article [pdf, 111 KB]

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

Narendra Jussien

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

abstract, article [pdf, 204 KB]

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

Guillaume Richaud, Xavier Lorca, Narendra Jussien

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

abstract, article [pdf, 105 KB]

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

Narendra Jussien

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

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

Hadrien Cambazard, Narendra Jussien

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

abstract, article [pdf, 111 KB]

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

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

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

, article [pdf, 366 KB]

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

Émilie Grellier, Pierre Dejax, Narendra Jussien

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

abstract, article [pdf, 21 KB]

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

Émilie Grellier, Pierre Dejax, Narendra Jussien

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

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

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

"Trends in Constraint Programming" , ISTE, 2007

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

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

Narendra Jussien

"A to Z of sudoku" , ISTE, 2007

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

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

Émilie Grellier, Pierre Dejax, Narendra Jussien

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

, article [pdf, 163 KB]

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

Hadrien Cambazard, Narendra Jussien

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

abstract, article [pdf, 1372 KB]

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

François Fages, Narendra Jussien, Christine Solnon

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

, article [pdf, 29 KB]

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

Narendra Jussien

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

, article [pdf, 400 KB]

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

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

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

abstract

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

Narendra Jussien

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

, article [pdf, 974 KB]

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

Narendra Jussien

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

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

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

Hadrien Cambazard, Narendra Jussien

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

abstract, article [pdf, 655 KB]

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

Narendra Jussien

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

, article [pdf, 1058 KB]

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

Narendra Jussien

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

, article [pdf, 652 KB]

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

Narendra Jussien

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

, article [pdf, 675 KB]

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

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

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

abstract, article [pdf, 254 KB]

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

Narendra Jussien

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

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

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

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

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

, article [pdf, 108 KB]

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

Narendra Jussien, Vincent Barichard

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

, article [pdf, 69 KB]

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

François Laburthe, Guillaume Rochart, Narendra Jussien

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

abstract, article [pdf, 413 KB]

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

Hadrien Cambazard, Narendra Jussien

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

abstract, article [pdf, 215 KB]

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

Guillaume Richaud, Hadrien Cambazard, Narendra Jussien

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

abstract, article [pdf, 193 KB]

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

Narendra Jussien

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

, article [atlanticiels.com]

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

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

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

, article [pdf, 353 KB]

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

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

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

, article [pdf, 276 KB]

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

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

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

, article [pdf, 97 KB]

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

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

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

, article [pdf, 204 KB]

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

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

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

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

Philippe Baptiste, Narendra Jussien, Pierre Lopez

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

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

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

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

, article [pdf, 354 KB]

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

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

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

, article [pdf, 204 KB]

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

Narendra Jussien

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

abstract

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

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

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

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

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

Hadrien Cambazard, Narendra Jussien

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

, article [pdf, 150 KB]

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

Hadrien Cambazard, Fabien Demazeau, Narendra Jussien, Philippe David

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

abstract, article [pdf, 347 KB]

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

Narendra Jussien

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

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

Hadrien Cambazard, Narendra Jussien

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

abstract, article [pdf, 214 KB]

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

Gérard Verfaillie, Narendra Jussien

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

abstract, article [pdf, 331 KB]

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

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

Hadrien Cambazard, Narendra Jussien

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

abstract, article [pdf, 733 KB]

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

Guillaume Rochart, Narendra Jussien

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

abstract, article [pdf, 210 KB]

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

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

Narendra Jussien

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

abstract

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

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

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

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

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

Hadrien Cambazard, Narendra Jussien

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

abstract, article [pdf, 429 KB]

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

Narendra Jussien

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

abstract, article [pdf, 46 KB]

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

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

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

, article [pdf, 2066 KB]

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

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

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

, article []

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

Narendra Jussien

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

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

Narendra Jussien

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

abstract, article [zip]

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

Étienne Gaudin, Narendra Jussien, Guillaume Rochart

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

, article [pdf, 176 KB]

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

Guillaume Rochart, Éric Monfroy, Narendra Jussien

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

, article [pdf, 164 KB]

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

Narendra Jussien

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

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

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

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

abstract, article [pdf, 268 KB]

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

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

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

abstract, article [pdf, 275 KB]

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

Laurent Breton, Narendra Jussien

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

abstract, article [pdf, 276 KB]

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

Hadrien Cambazard, Fabien Demazeau, Narendra Jussien, Philippe David

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

abstract, article [pdf, 336 KB]

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

Étienne Gaudin, Narendra Jussien, Guillaume Rochart

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

, article [pdf, 182 KB]

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

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

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

abstract, article [pdf, 310 KB]

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

Guillaume Rochart, Narendra Jussien

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

abstract, article [pdf, 79 KB]

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

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

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

, article [pdf, 52 KB]

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

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

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

abstract

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

Guillaume Rochart, Narendra Jussien

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

abstract, article [pdf, 218 KB]

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

Abdallah Elkhyari, Christelle Guéret, Narendra Jussien

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

, article [pdf, 121 KB]

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

Narendra Jussien, François Laburthe

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

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

Mohammad Ghoniem, Narendra Jussien, Jean-Daniel Fekete

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

abstract, article [pdf, 444 KB]

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

Narendra Jussien

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

abstract

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

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

Narendra Jussien

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

abstract, article [pdf, 608 KB]

@TechReport{jussien-versatility-rr,
author         = {Narendra Jussien},
title          = {The versatility of using explanations within constraint programming},
institution    = {\'Ecole des Mines de Nantes},
year           = 2003,
number         = {03-04-INFO},
address        = {Nantes, France},
url            = {http://www.emn.fr/jussien/publications/jussien-RR0304.pdf},
kind           = {RR},
type           = {Research Report},
abstract       = {Constraint programming is a research topic benefiting from many other areas: discrete mathematics, numerical analysis, artificial intelligence, operations research, and formal calculus. It has proven its interest and its efficiency in various domains: combinatorial optimization, scheduling, finance, simulation and synthesis, diagnosis, molecular biology, or geometrical problems. However, some limitations and difficulties remain: designing stable and generic algorithms, handling dynamic problems, opening constraint programming to non-specialists, etc.

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

Guillaume Rochart, Narendra Jussien, François Laburthe

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

, article [pdf, 158 KB]

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

Mohammad Ghoniem, Narendra Jussien, Jean-Daniel Fekete

"Visualizing explanations to exhibit dynamic structure in constraint problems" , CP03 Workshop on