Sujet de la thèse: Acquisition de prémodèles à contraintes
ENCADRANTS: Christian Bessiere, Joël Quinqueton
Un des thèmes forts de l'équipe est la programmation par contraintes et son utilisation pour résoudre des problèmes dans d'autres domaines ou son intégration dans des produits innovants dans des start up.
Le principe est d'exprimer un problème combinatoire (style emploi du temps) dans le formalisme appelé "réseaux de contraintes" et d'appeler un solveur qui se chargera de générer une solution. Les solveurs sont maintenant nombreux, entre les commerciaux et les libres.
L'équipe a beaucoup travaillé sur les algorithmes efficaces pour résoudre les réseaux de contraintes. Mais un de nos axes récents est l'aide à un utilisateur qui ne connait pas la prog. par contraintes, à exprimer son problème comme il faut, c'est à dire tel que le solveur puisse faire son boulot. En effet, il s'avère que pour un novice, il n'est pas trivial de formuler en termes de variables, valeurs possibles, et contraintes (cad réseau de contraintes).
Les travaux récents de l'équipe coconut ont conduit à un algorithme efficace (linéaire) pour acquérir un réseau de contraintes à partir d’exemples de solutions et de contre-exemples. Cet algorithme est utilisé dans la plateforme logicielle Conacq, qui permet de fournir une aide significative à la modélisation d'un problème. Cependant, cet algorithme se base sur une connaissance des variables du problème. Or, cette connaissance peut faire défaut à un utilisateur néophyte en contraintes. Nous proposons de prendre en compte le savoir faire de l'utilisateur au travers des solutions passées obtenues pour des problèmes similaires. De ces données, nous comptons tirer de façon automatique les variables du problème ainsi que des contraintes implicites liant ces variables. Cette information de base, appelée 'prémodèle', facilitera le travail de Conacq lors de l'acquisition des contraintes.