10h00Boris Bontoux, Dominique Feillet, Christian Artigues (LIA, Université d'Avignon)

Une méthode dynamique de parcours d'arbre de recherche: Dynamic Cooperative Search (.pdf)

10h40Nicolas Levasseur, Patrice Boizumault, Samir Loudni (GREYC, Université de Caen)

Une heuristique de sélection de valeurs dirigée par l'impact pour les WCSP (.pdf)

11h20Samba Ndojh Ndiaye, Philippe Jégou, Cyril Terrioux (LSIS, Université d'Aix-Marseille III)

Heuristiques dynamiques pour l'exploitation de décompositions arborescentes de (W)CSP (.pdf)

12h00Déjeuner (libre)

14h00Laurent Simon (LRI, Paris-Sud)

Exposé invité : Recherche locale pour UNSAT

15h00Pause

15h15Abir Ben Hmida, Wafa Karoui, Marie-José Huguet, Pierre Lopez, Christian Artigues (LAAS, Toulouse)

Méthode de recherche à divergences limitées (Limited Discrepancy Search) : Extensions, applications et relations avec les méthodes de (grand) voisinage.

16h00Table ronde

17h00Fin de la journée.

La journée s'est déroulée le 19 janvier 2007 sur le site de Jussieu :

Amphi Ernest Chouard, Tour 53, Université Paris 6, 4 place Jussieu, 75005 Paris, Métro Jussieu (ligne 7).

Accès au site de Jussieu (lien UPMC) et à l'amphi Ernest Chouard (plan)

Les méthodes privilégiées de résolution des problèmes combinatoires reposent sur le principe de 'divide-and-conquer' : l'exploration complète (recherches arborescentes) ou incomplète (recherches locales) de l'espace de recherche s'effectue par séparations et évaluations successives des sous-espaces. Les décisions à prendre portent alors sur la stratégie de séparation (définition du branchement ou du voisinage) et sur l'ordre selon lequel les sous-espaces sont évalués.

Bien qu'ayant une influence fondamentale sur la rapidité de convergence de ces procédures, la stratégie de séparation et d'exploration est souvent négligée: en pratique, les efforts portent plus souvent sur l'évaluation des sous-problèmes (calcul de bornes, propagation et maintien de cohérence,...).

Les recherches arborescentes sont emblématiques de ce fait. De nombreuses applications en programmation par contraintes, par exemple, reposent sur la stratégie d'exploration par défaut du solveur, ou sur le triplet de base: séparation du domaine des variables / heuristique min-domain / profondeur d'abord.

Pourtant, des stratégies d'exploration alternatives apparaissent, régulièrement et de manière indépendante, dans la littérature de la programmation par contraintes, de la programmation mathématique, ou encore de la logique propositionnelle (les travaux sur les solveurs SAT, par exemple, ont été relancés suite à l'introduction des techniques de backjumping et de randomization). Parmi ces techniques anciennes ou récentes, on peut citer, à titre d'exemples :

• Strong branching, Pseudo-costs (PL) et Forward checking (PPC) ;
• GUB/SOS Branching (PL) ;
• Local branching ;
• Backjumping, Dynamic Backtracking, Decision Repair ;
• Limited Discrependancy Search ;
• Symmetry breaking ;...

Tout comme la recherche arborescente est, par exemple, commune à la programmation mathématique (branch-and-bound), la programmation par contraintes (backtracking) et la logique propositionnelle (DPLL), ce type d'alternatives pourraient potentiellement s'appliquer aux différents contextes.

L'objectif d'une rencontre du groupe PPC+RO sur ce thème est de confronter les différentes techniques communément employées ou récemment apparues dans les différentes communautés RO, PPC et SAT, afin d'identifier leurs caractéristiques respectives, leurs degrés de généricité, ou encore leurs éventuelles similarités. L'adaptation de ces techniques, dans l'un ou l'autre de ces contextes, relève d'une forme d'hybridation, basée sur l'exploration et non sur l'évaluation, encore peu répandue à ce jour. Au-delà de l'hybridation PPC/RO, la généralisation et la combinaison de ces techniques révèlent d'autres formes d'hybridations: optimisation/satisfaction, discret/continu, méthode approchée/méthode exacte.