Un processus en résolution de contraintes où des règles d'inférence locales sont appliquées aux contraintes pour réduire itérativement les domaines des variables en éliminant les valeurs qui ne peuvent pas participer à une solution sous les contraintes actuelles, souvent en prétraitement ou pendant la recherche pour élaguer l'espace de recherche.

Principe

Appliquer de manière répétée une notion de consistance locale choisie (consistance de nœud, d'arc, de chemin, k‑consistance, ou propagateurs globaux spécifiques) : détecter et supprimer les valeurs de domaine contradictoires par des algorithmes de propagation (par ex. AC‑3, AC‑4, GAC pour contraintes globales) jusqu'à atteindre un point fixe ou une contradiction.

Démonstration

Dans un CSP Sudoku, la propagation de consistance d'arc supprime les chiffres impossibles du domaine de chaque case en considérant les contraintes de ligne, colonne et bloc ; à mesure que les domaines rétrécissent, la propagation peut forcer des singletons qui provoquent d'autres réductions, élaguant fortement la recherche par backtracking.

Mauvaise application

Compter sur la propagation locale pour résoudre complètement des CSP NP‑difficiles ou appliquer un filtrage trop agressif qui est non sûr (supprime des valeurs appartenant à une solution globale) à cause d'une implémentation incorrecte d'un propagateur ; ou utiliser la propagation sans la combiner à la recherche lorsque la propagation seule ne suffit pas à décider la satisfiabilité.

Conséquence

La propagation réduit l'effort de recherche en élaguant les combinaisons de valeurs infaisables, permet la détection précoce des contradictions, supporte la résolution incrémentale et dynamique, et s'interface bien avec des heuristiques de branchement ; toutefois elle ne remplace pas en général la recherche exhaustive sauf sur des classes tractables.

Inversion

La génération ou la relaxation de contraintes inverse la fonction de rétrécissement de la propagation : au lieu d'élaguer les domaines pour écarter des valeurs, on peut élargir les domaines ou affaiblir les contraintes pour guider une recherche ou capturer de l'information duale, échangeant élagage contre flexibilité ou sur‑approximation.

Limite

S'applique aux CSP à domaines finis ou finement représentables et dépend du niveau de consistance choisi ; la propagation est sûre (ne supprime pas toutes les solutions) seulement si les propagateurs sont corrects, et la complétude (trouver une solution sans recherche) ne tient que pour des classes de problèmes particulières ou des niveaux de consistance globaux.

Tension sémantique

La tension apparaît entre propagation et approches par encodage (vers SAT/SMT) ou entre consistance locale et raisonnement global : la propagation locale est moins coûteuse mais plus faible que l'implication complète des contraintes, tandis qu'une propagation plus forte (contraintes globales) est plus coûteuse mais permet un élagage plus profond.

Synthèse

La propagation de contraintes est un mécanisme d'inférence locale itératif et correct qui émonde les domaines de variables selon les contraintes pour rendre la recherche praticable ; combinée au branchement, aux propagateurs globaux et aux heuristiques, elle constitue l'épine dorsale de la programmation par contraintes pratique, équilibrant coût d'inférence et puissance d'élagage.