Résultats


Résumé

La synthèse de mon HDR [pdf] décrit l'ensemble de mes travaux. Elle présente aussi la programmation par contraintes (PPC) et la problématique de la modélisation en PPC.

Depuis que je travaille dans le domaine de la programmation par contraintes (PPC) j'ai proposé :
  • l'un des premiers algorithmes de filtrage établissant efficacement la consistance d'arc pour une contrainte globale : la contrainte alldiff [pdf] L'article associé est un des articles les plus cités en programmation par contraintes et son audience dépasse largement cette communauté.
  • de nombreuses contraintes globales fondamentales associées à des algorithmes de filtrage originaux ou intégrant des algorithmes de Recherche Opérationnelle.
  • des algorithmes généraux de filtrage pour les contraintes binaires ou non, comprenant notamment un algorithme unifiant tous les algorithmes existants d'arc consistance pour les contraintes binaires.
  • un nouveau point de vue et un nouveau modèle pour la résolution des problèmes sur-contraints, accompagnés de plusieurs algorithmes de filtrage améliorant l'existant. J'ai aussi introduit de nouveaux thèmes de recherche pour les problèmes sur-contraints comme la définition générale du coût de violation d'une contrainte ou les contraintes globales molles
  • divers principes généraux de modélisation et plusieurs modèles de PPC pour résoudre certaines applications particulièrement difficiles comme la recherche de la plus grande clique dans un graphe ou le dimensionnement de réseau de télécommunications
  • différents autres travaux

Contraintes globales

Je suis l'auteur des contraintes globales bien connues suivantes :

Algorithmes généraux de filtrage par consistance d'arc

J'ai proposé plusieurs algorithmes généraux établissant la consistance d'arc (AC) :
  • Pour les contraintes binaires :
    Je suis un des auteurs d'AC-7, [ps] d'AC-Inference [ps], d'AC-2000 et AC-2001 [aij pdf], [ijcai ps]. Récemment j'ai introduit un nouvel algorithme AC-* qui est capable de représenter n'importe quel algorithme de consistance d'arc. Dans ce papier [english pdf], [pdf en français] tous les algorithmes existants de consistance d'arc sont décrits et les concepts sur lesquels ils sont basés sont identifiés. Une nouvelle nomenclature des algorithmes de consistance d'arc est proposée. Ce nouvel algorithme a tout d'abord été appelé CAC, mais plusieurs personnes m'ont dit que le nom était mal choisi, et Gilles Pesant m'a suggéré AC-*. J'aime bien ce nom, aussi je remercie Gilles. Plusieurs articles présentent des résultats impliquant la version "MAC" des algorithmes de consistance d'arc (MAC signifie maintient de la consistance d'arc). MAC-4, MAC-6, MAC-7, et MAC-Inférence sont entièrement détaillé dans ma thèse de Doctorat. Malheureusement, lorsque j'ai quitté l'Université de Montpellier, j'ai perdu les fichiers de ma thèse. Néanmoins, vous pourrez trouver dans cet article [pdf] une description détaillée des algorithmes MAC-6 et MAC-7. De plus, cet article montre que l'on peut implémenter ces algorithmes avec les mêmes complexités en temps et en espace que AC-6 et AC-7.
  • Pour les contraintes non binaires :
    GAC-Schema [ps] est un cadre général pour les contraintes qui sont définies explicitement par la liste des combinaisons de valeurs autorisées, par la liste des combinaisons de valeurs interdites ou par un prédicat. Ce schéma est capable d'éviter de traverser plusieurs fois la même partie de l'espace de recherche même si on parcours cet espace de recherche à partir de noeuds différents. Cet algorithme a aussi été amélioré [ps].

Problèmes sur-contraints

Avec Thierry Petit, dont j'étais un des directeurs de thèse (l'autre étant Christian Bessière), nous avons étudié les problèmes sur-contraints à partir d'un point de vue réel. Cela signifie que nous avons étudié des applications du monde réel et qu'à partir de cette étude nous avons proposé des modèles et des algorithmes originaux pour aider à la résolution de ces applications :

  • Un nouveau modèle basé sur les méta-contraintes est décrit dans cet article [ps]. Cet article formalise et étend une idée communément utilisée par tous les résolveurs industriels basés sur la PPC pour résoudre des applications réelles sur-contraintes. Il compare aussi ce modèle avec le modèle bien connu des CSP valués (Valued CSP).
  • Nous avons généralisé l'algorithme PFC-MRDAC (Partial Forward Checking Maintaining Reversible Directed Arc Consistency) afin de prendre en compte les contraintes non binaires. Nous avons également proposé un nouvel algorithme basé sur la notion d'ensemble de conflits (c'est-à-dire un ensemble de contraintes que le mécanisme de propagation peut détecter comme étant inconsistante) [english pdf], [ps en français]. Cet article montre également certains inconvénients de l'algorithme PFC-MRDAC, notamment en identifiant les contraintes qui sont ignorés par PFC-MRDAC. Notre algorithme peut être utilisé indépendemment de, ou en conjonction avec, PFC-MRDAC. Tous les algorithmes que nous avons écrits pour les problèmes sur-contraints essaient d'utiliser les algorithmes de filtrage associées aux contraintes même si ces contraintes sont molles (i.e. elles peuvent être violées). L'article suivant donne plus de détail sur ce principe [ps]. Par ailleurs, nous avons également proposé plusieurs raffinements pour la recherche d'ensembles de conflits [english pdf], [ps en français].
  • Range-PFC-MRDAC est une version de l'algorithme PFC-MRDAC basé uniquement sur les bornes des variables, ce qui est nécessaire pour certaines applications d'ordonnancement où les domaines des variables contiennent énormément de valeurs. [ps].
  • Le concept de contrainte globale molle a été introduit pour la première fois dans l'article suivant [ps], qui présente la contrainte alldiff molle.

Modélisation et Résolution de problèmes réels

J'ai travaillé sur la modélisation et la résolution de problèmes réels :

  • Une définition des caractéristiques d'un bon modèle se trouve [ici]. Cet article didactique considère un problème difficile (i.e. la minimisation du nombre de "break" des tournois sportifs) et montre étape par étape comment un modèle efficace peut être décrit.
  • Le problème de l'intérêt d'un algorithme de filtrage dédié par rapport à un algorithme de filtrage général est discuté dans ce papier [ps].
  • Un modèle de PPC pour les problèmes sur-contraints est décrit dans cet article [ps].
  • Le problème des tournois sportifs et le modèle de PPC que j'ai proposé sont souvent utilisé par des chercheurs en PPC pour introduire la programmation par contraintes dans les autres communautés, comme la recherche opérationnelle. La syntaxe OPL de ce modèle est décrite dans cet article [ps].
  • Comme exemple de PPC appliqué à la biologie, il y a un problème spécifique de repliement d'ARN [ps].
  • La PPC est aussi une technique efficace pour résoudre des problèmes de combinatoire pure, comme cela est montré dans cet article [pdf] qui traite de la recherche de la taille de la plus grande clique dans un graphe.
  • Le problème du dimensionnement d'un réseau de télécommunication est très difficile. Il apparaît que la PPC est une des meilleures méthodes et la plus robuste pour le résoudre [ps] [pdf en français]. Le premier article introduit également l'idée intéressante des variables de graphe. C'est-à-dire des variables dont le domaine est un sous-graphe d'un autre graphe.
  • Certaines instances difficiles du problème de la complétion d'un quasi groupe sont efficacement résolues avec la contrainte matricielle de cardinalité. [pdf].
  • Certaines instances du problèmes d'ordonnancement de véhicules sur une chaîne de montage (car sequencing en anglais) sont efficacement résolues avec la contrainte de séquences [ps].

Divers

Je suis l'un des auteurs d'un article [ps] qui suscita un grand nombre de discussions dans la communauté de programmation par contraintes, car il affirme, tests à l'appui, que les techniques de filtrages sont meilleures que les techniques de retour-arrière intelligent.

Enfin, je suis un des coauteurs de Lazy AC [ps], qui est un joli algorithme à mon avis. Au lieu de considérer toutes les valeurs dans les domaines et de supprimer celles qui ne sont pas consistantes avec la contrainte, Lazy AC propose de commencer à partir de domaines vides et d'ajouter des valeurs dans ces domaines jusqu'à ce que la consistance d'arc soit établie. De nombreux travaux effectués dans le domaine de la configuration sont proches de cette idée.


Last revised: 04/05/05