– CANAR

Le projet Constraint Acquisition aNd Automatic Reformulation a pour objectif d'étudier, de développer et d'implanter deux techniques d'automatisation de la modélisation en Programmation par Contraintes : l'acquisition de contraintes et de réseaux de contraintes, et leur reformulation. Avec le succès grandissant des solveurs de contraintes, l'étape de modélisation, longtemps considérée comme élémentaire, est devenue un problème majeur. En effet, la construction d'un modèle à base de contraintes nécessite deux types de connaissances « expertes » : * Connaissance d'un catalogue étendu de centaines de contraintes globales, mais aussi pour un utilisateur novice, la connaissance de ce qu'est une contrainte et comment elles peuvent être combinées ; * Connaissance du modèle d'exécution du solveur, car de nombreux problème demandent une formulation particulière pour pouvoir être résolus en un temps raisonnable. Par exemple, l'ajout d'une contrainte globale redondante à un modèle peut accélérer le temps de la résolution de plusieurs ordres de grandeur car la propagation adéquate a été effectuée au bon moment. Demander à tous les utilisateurs potentiels de la Programmation par Contrainte (PPC) de connaître ces aspects est impossible. Une automatisation est donc nécessaire pour permettre à des utilisateurs débutants et intermédiaires d'utiliser la PPC plus largement dans leurs applications. Par exemple, certains solveurs SAT ou de Programmation Linéaire demandent beaucoup moins d'investissement pour être utilisés et de nombreux utilisateurs préfèrent coder leur modèle dans ces formalismes non parce qu'ils sont mieux appropriés mais parce qu'ils savent qu'ils n'auront pas à se soucier de la logique interne du solveur. Pour attaquer ce problème, nous proposons les directions de recherche suivantes : * L'acquisition d'un modèle. Elle sera faite en demandant à l'utilisateur une spécification de ses besoins. Celle-ci peut-être donnée soit par des exemples de ce qui est et de ce qui n'est pas une solution, soit par une description plus précise, par exemple en logique. * La reformulation d'un modèle. Elle consiste à appliquer plusieurs transformations préservant la sémantique du problème, dans le but d'obtenir un modèle équivalent mais résolu plus efficacement. Les actions concrètes que nous allons explorer sont les suivantes : * Acquisition d'une relation comme un réseau de contraintes. En donnant des exemples positifs et négatifs, l'objectif est que le système puisse construire un réseau de contraintes dont les solutions sont compatibles avec l'entrée. En d'autres termes, il s'agit d'utiliser les contraintes comme technique de représentation pour l'Apprentissage. La variété et la potentiellement grande arité des contraintes rend le problème difficile du point de vue Apprentissage. * Acquisition d'une relation en tant que contrainte globale. De la même façon, ceci peut être fait en fournissant des exemples et des contre-exemples. Ici, la structure de donnée sera plus classique du point de vue Apprentissage, par exemple un réseau de neurones ou un arbre de décisions. Ainsi, le problème n'est pas d'acquérir la relation, ce qui est bien connu, mais plutôt de lui construire un propagateur permettant de l'utiliser activement dans la résolution d'un problème. * Construction d'une contrainte à partir d'une spécification. Dans certains cas, l'utilisateur est capable de produire une spécification plus détaillée, par exemple dans un langage logique ou impératif. Ici aussi, le problème est de lui associer un algorithme de filtrage. * Reformulation de modèle. Afin d'améliorer un modèle construit par l'utilisateur ou généré automatiquement, il est utile de transférer de la connaissance experte que l'on trouve par exemple dans certains modèles subtils construits à la main. Nous allons nous intéresser à des transformations de graphes qui préservent la sémantique du problème tout en le rendant plus rapide à résoudre. * Apprentissage de contraintes globa