Problèmes de satisfaction de contraintes

Un problème de satisfaction de contraintes (PSC) consiste à trouver une affectation de valeurs à un ensemble de variables qui satisfait simultanément toutes les contraintes entre elles, offrant ainsi une représentation uniforme pour de nombreux problèmes combinatoires.

Definition

Un problème de satisfaction de contraintes se compose d'un ensemble de variables, d'un domaine de valeurs possibles pour chacune, et d'un ensemble de contraintes spécifiant les combinaisons de valeurs admissibles ; une solution est une affectation complète qui ne viole aucune contrainte.

Scope

Ce sujet aborde le formalisme des problèmes de satisfaction de contraintes (PSC) (variables, domaines, contraintes) et les algorithmes qui les résolvent : la recherche par retour sur trace (backtracking) avec des heuristiques d'ordonnancement des variables et des valeurs, la propagation de contraintes et les techniques de cohérence (cohérence de nœud, d'arc et de chemin, comme l'algorithme AC-3), ainsi que l'exploitation de la structure du problème (PSC arborescents, conditionnement par coupe-ensemble). Il est lié à la recherche locale pour les PSC et à la pratique plus large de la programmation par contraintes. Les formulations basées sur l'optimisation continue et l'apprentissage pour des problèmes similaires sont hors de portée ici.

Core questions

• Comment divers problèmes (ordonnancement, coloration de graphes, jeux de logique) sont-ils uniformément représentés sous forme de variables, de domaines et de contraintes ?
• Comment la propagation de contraintes élague-t-elle les valeurs avant et pendant la recherche pour réduire le retour sur trace ?
• Quelles heuristiques d'ordonnancement des variables et des valeurs rendent la recherche par retour sur trace efficace ?
• Comment la structure du graphe de contraintes (par exemple, sa forme arborescente) peut-elle être exploitée pour une résolution efficace ?

Key concepts

• variables, domaines, contraintes
• graphe de contraintes
• recherche par retour sur trace
• vérification avant (forward checking)
• cohérence d'arc et AC-3
• heuristique des valeurs restantes minimales
• propagation de contraintes
• PSC arborescents et conditionnement par coupe-ensemble

Key theories

Cohérence d'arc et propagation de contraintes

Un PSC est cohérent par arc lorsque chaque valeur de chaque variable possède un partenaire cohérent dans chaque variable voisine ; des algorithmes tels que AC-3 appliquent cette cohérence en supprimant de manière répétée les valeurs non supportées, réduisant souvent drastiquement les domaines avant ou pendant la recherche.

Recherche par retour sur trace avec heuristiques

Les PSC sont résolus par affectation en profondeur d'abord avec retour sur trace, rendue pratique par des heuristiques telles que le choix de la variable la plus contrainte (valeurs restantes minimales), de la valeur la moins contraignante, et par l'intercalation de la vérification avant (forward checking) ou de la propagation pour détecter les impasses précocement.

Exploitation de la structure

Lorsque le graphe de contraintes est un arbre, un PSC peut être résolu en un temps linéaire par rapport au nombre de variables, et les structures quasi-arborescentes peuvent être réduites à ce cas via le conditionnement par coupe-ensemble ou la décomposition arborescente.

Clinical relevance

Les techniques de PSC sont le moteur de la planification et de l'ordonnancement, de l'allocation de ressources, de la configuration de produits, de la vérification matérielle et logicielle, et des solveurs de jeux de logique tels que le Sudoku ; les langages de programmation par contraintes et les solveurs basés sur ces idées sont largement utilisés dans la planification industrielle et la recherche opérationnelle.

History

Les réseaux de contraintes ont émergé dans les années 1970 des travaux sur l'étiquetage de scènes et la cohérence relationnelle, avec l'article de Mackworth de 1977 formalisant la cohérence de nœud, d'arc et de chemin. Au cours des années 1980-90, le domaine a mûri pour devenir la programmation par contraintes, consolidée dans le Handbook of Constraint Programming de 2006, et reste un sujet standard en IA.

Key figures

• Alan K. Mackworth
• Rina Dechter
• Eugene C. Freuder
• Ugo Montanari

Seminal works

• mackworth1977
• dechter2003
• rossi2006

Frequently asked questions

En quoi un problème de satisfaction de contraintes diffère-t-il d'un problème de recherche général ?

Un problème de recherche général traite les états comme des boîtes noires, mais un PSC expose la structure interne d'un état comme une affectation de variables soumises à des contraintes. Cette structure permet aux solveurs de PSC d'utiliser la propagation de contraintes et des heuristiques d'ordonnancement que la recherche générique ne peut pas exploiter.

Que fait la cohérence d'arc ?

La cohérence d'arc supprime les valeurs du domaine d'une variable qui n'ont pas de valeur compatible dans une variable voisine, compte tenu de la contrainte entre elles. L'appliquer avant et pendant la recherche élague l'espace de recherche et peut parfois résoudre un problème directement sans retour sur trace.