Apprentissage de Contraintes Globales Implicites

http://www710.univ-lyon1.fr/~csolnonIl peut exister de nombreux modèles à contraintes exprimant un problème donné. Une des barrières s'opposant à une diffusion plus ample de la programmation par contraintes est l'expertise importante requise pour concevoir un modèle permettant une résolution efficace d'un problème. Aussi, l'intérêt de la communauté pour la reformulation automatique des modèles à contraintes est croissant. Cet article présente une approche alternative, consistant à apprendre des contraintes implicites d'après des instanciations des variables du problème, solutions et non-solutions. Ces contraintes sont alors ajoutées au modèle afin d'améliorer la résolution. Pour valider l'impact de cette approche, nous proposons un algorithme d'apprentissage de contraintes de cardinalité globale (Gcc). Nous montrons expérimentalement l'intérêt de cet algorithme pour améliorer la qualité des modèles à contraintes