Programme de Recherche


Mon but est de rendre la programmation par contraintes (PPC) plus efficace, plus simple à utiliser et plus populaire.

  • Pour la rendre plus efficace, il faudrait continuer à développer de nombreuses contraintes globales ainsi que les algorithmes de filtrage associés. Ces algorithmes, basés sur la théorie des graphes ou la recherche opérationnelle, identifient le plus rapidement possible des valeurs qui n'appartiennent pas à une solution d'un problème. Cette approche permet de développer un nouveau thème de recherche car cette question a rarement été abordée en dehors de la PPC. Il faudrait aussi essayer de traiter plus efficace la suppression de symétries lors de la résolution.
  • Pour la rendre plus simple à utiliser, il serait intéressant de travailler sur l'intégration de coûts à l'intérieur de contraintes afin de traiter plus facilement les problèmes d'optimisation. Il faudrait aussi trouver une représentation simple de notions complexes comme la répartition homogène des violations de contraintes pour les problèmes sur-contraints.
  • Pour la rendre plus populaire, il faudrait rendre son utilisation plus transparente et résoudre des problème majeurs bien connus afin de la promouvoir dans les autres communautés. Autrement dit continuer le travail que j'ai commencé avec le problème de la recherche de la taille de la plus grande clique dans un graphe. Par exemple, je pense qu'il faudrait s'attaquer aux problèmes suivants : le problème du coloriage minimum, le problème du recouvrement minimum par des ensembles (set-cover), le problème du sac-à-dos multidimentionnel et enfin le problème du voyageur de commerce.

De façon plus précises dans le domaine de la PPC, je pense qu'il serait intéressant d'étudier les problèmes suivants :

  • le calcul de l'ensemble des solutions d'un problème afin de pouvoir engendrer des contraintes dont les combinaisons autorisées sont données en extension.
  • la combinaison de certaines contraintes globales avec d'autres contraintes simples afin d'obtenir de nouvelles contraintes globales plus fortes encore.
  • l'exploitation plus fine de certains algorithmes de RO ou de théorie des graphes ou la définition de nouveaux algorithmes pour réduire la complexité de certains algorithmes de filtrage comme celui établissant la consistance d'arc pour la contrainte symmetric alldiff, ou pour généraliser d'autres algorithmes de filtrage comme celui de la contrainte globale de cardinalité avec ou sans coûts.
  • la prise en compte de disjonctions à la place de la notion de distance dans la contrainte globale de distance minimum afin de pouvoir s'attaquer aux problèmes d'ordonnancement avec la granularité des valeurs des domaines et non pas seulement des bornes.
  • la définition de contraintes basée sur des problèmes NP-Complets et l'utilisation d'algorithmes d'approximation pour estimer la consistance de ces contraintes et proposer des algorithmes de filtrage associés.
  • l'étude de nouvelles contraintes globales molles et la définition de nouveaux coûts de violation généraux.


Last revised: 04/05/05