La contrainte all-diff

La contrainte all-diff traite un $\mathcal{CSP}$, ou un sous-problème d'un $\mathcal{CSP}$, ayant un certain nombre de variables dont les valeurs potentielles varient dans des domaines finis, et contraintes à être toutes différentes. Autrement dit, $\forall i \neq j$ tels que $i,j \in \llbracket 1, n \rrbracket$, on a $x_i \neq x_j$. Au lieu d'avoir $\frac{n(n-1)}{2}$ contraintes à traiter, on ne parle que d'une seule, que l'on nomme la contrainte all-diff. L'exemple 2.1 est une instance d'un tel $\mathcal{CSP}$, qui illustre parfaitement les difficultés des méthodes basées sur l'arc consistance pour résoudre ce type de problèmes.

Figure 1: Illustration de la contrainte globale All-diff

L'algorithme proposé par J.C. Régin [10], modélise les variables et les valeurs des domaines par un graphe biparti. Puis en quelques étapes il établit l'arc cohérence, de manière à ce qu'on ne puisse pas trouver un meilleur filtrage(consistance globale). C'est un algorithme en temps polynômial :

1. À partir du $\mathcal{CSP}$, génerer un graphe biparti variable-valeur.
2. Calculer le couplage maximum du graphe
3. Si une variable est libre, alors pas de solutions
4. Appliquer la décomposition de Dulmage-Mendelson à partir du couplage obtenu.
5. Calculer les composantes fortement connexes de la partie ``bien-valuée''
6. Éliminer les valeurs des domaines correspondant aux arètes reliant les parties ``bien-valuée'' et ``sur-valuée'' et aux arètes reliant dux composantes fortement connexes.