Estimer le nombre de solutions des contraintes de cardinalité grâce à leur décomposition range et roots

National audienceEn programmation par contraintes, le choix d’une heuristique de recherche plutôt qu’une autre dépend souvent du problème. Cependant il existe des heuristiques génériques utilisant plutôt des indicateurs sur la structure combinatoire du problème. Les heuristiques "Counting- Based", introduites par Pesant et al., font des choix basés sur une estimation du nombre de solutions restantes dans tel ou tel sous-arbre de l’arbre de recherche. Un inconvénient de ces heuristiques est qu’elles nécessitent des algorithmes de dénombrement spécifiques à chaque contrainte. Cette étude s’intéresse aux contraintes de cardinalité, dont alldifferent, atmost, nvalue, etc... Nous proposons une méthode de comptage de solutions pour les contraintes range et roots, introduites par Bessiere et al. Grâce à la décomposition des contraintes de cardinalité en contraintes range et roots, nous dérivons une méthode systématique de dénombrement de solutions pour la plupart de ces contraintes