Cohérence locale - Local consistency

Dans la satisfaction de contraintes , les conditions de cohérence locale sont des propriétés des problèmes de satisfaction de contraintes liés à la cohérence de sous-ensembles de variables ou de contraintes. Ils peuvent être utilisés pour réduire l'espace de recherche et faciliter la résolution du problème. Différents types de conditions de cohérence locale sont exploités, notamment la cohérence des nœuds , la cohérence de l'arc et la cohérence des chemins .

Chaque condition de cohérence locale peut être appliquée par une transformation qui modifie le problème sans changer ses solutions. Une telle transformation est appelée propagation de contraintes . La propagation des contraintes fonctionne en réduisant les domaines de variables, en renforçant les contraintes ou en en créant de nouvelles. Cela conduit à une réduction de l'espace de recherche, ce qui rend le problème plus facile à résoudre par certains algorithmes. La propagation des contraintes peut également être utilisée comme un vérificateur d'insatisfaisabilité, incomplet en général mais complet dans certains cas particuliers.

Les conditions de cohérence locale peuvent être regroupées en différentes classes. Les conditions de cohérence locale d'origine exigent que chaque affectation cohérente puisse être étendue de manière cohérente à une autre variable. La cohérence directionnelle ne requiert que cette condition soit satisfaite lorsque l'autre variable est supérieure à celles de l'affectation, selon un ordre donné. La cohérence relationnelle inclut des extensions à plusieurs variables, mais cette extension n'est requise que pour satisfaire une contrainte ou un ensemble de contraintes donné.

Hypothèses

Dans cet article, un problème de satisfaction de contraintes est défini comme un ensemble de variables, un ensemble de domaines et un ensemble de contraintes. Les variables et les domaines sont associés: le domaine d'une variable contient toutes les valeurs que la variable peut prendre. Une contrainte est composée d'une séquence de variables, appelée sa portée, et d'un ensemble de leurs évaluations, qui sont les évaluations satisfaisant la contrainte.

Les problèmes de satisfaction des contraintes mentionnés dans cet article sont supposés se présenter sous une forme particulière. Un problème est sous forme normalisée , respectivement sous forme régulière , si chaque séquence de variables est la portée d'au plus une contrainte ou d'exactement une contrainte. L'hypothèse de régularité faite uniquement pour les contraintes binaires conduit à la forme standardisée . Ces conditions peuvent toujours être appliquées en combinant toutes les contraintes sur une séquence de variables en une seule et / ou en ajoutant une contrainte qui est satisfaite par toutes les valeurs d'une séquence de variables.

Dans les figures utilisées dans cet article, l'absence de liens entre deux variables indique qu'aucune contrainte ou qu'une contrainte satisfaite par toutes les valeurs n'existe entre ces deux variables.

Cohérence locale

Les conditions de cohérence locale "standard" exigent toutes que toutes les évaluations partielles cohérentes puissent être étendues à une autre variable de telle sorte que l'affectation résultante soit cohérente. Une évaluation partielle est cohérente si elle satisfait toutes les contraintes dont la portée est un sous-ensemble des variables affectées.

Cohérence des nœuds

La cohérence des nœuds exige que chaque contrainte unaire sur une variable soit satisfaite par toutes les valeurs du domaine de la variable, et vice versa. Cette condition peut être appliquée de manière triviale en réduisant le domaine de chaque variable aux valeurs qui satisfont toutes les contraintes unaires sur cette variable. En conséquence, les contraintes unaires peuvent être négligées et supposées incorporées dans les domaines.

Par exemple, étant donné une variable avec un domaine et une contrainte , la cohérence de nœud restreindrait le domaine à et la contrainte pourrait alors être rejetée. Cette étape de prétraitement simplifie les étapes ultérieures. ${\ displaystyle V}$${\ displaystyle \ left \ {1,2,3,4 \ right \}}$${\ displaystyle V \ leq 3}$${\ displaystyle \ left \ {1,2,3 \ right \}}$

Cohérence de l'arc

x2 est conforme à l'arc avec x3 mais pas avec x1, car la valeur x2 = 1 ne correspond à aucune valeur pour x1.

Une variable d'un problème de satisfaction de contrainte est cohérente avec une autre si chacune de ses valeurs admissibles est cohérente avec une valeur admissible de la deuxième variable. Formellement, une variable est conforme à l'arc avec une autre variable si, pour chaque valeur dans le domaine de, il existe une valeur dans le domaine de tel qui satisfait la contrainte binaire entre et . Un problème est cohérent si chaque variable est cohérente avec toutes les autres. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle a}$${\ displaystyle x_ {i}}$${\ displaystyle b}$${\ displaystyle x_ {j}}$${\ displaystyle (a, b)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$

Par exemple, considérez la contrainte où les variables s'étendent sur le domaine 1 à 3. Comme il ne peut jamais être 3, il n'y a pas d'arc de 3 à une valeur dans donc il est sûr de supprimer. De même, ne peut jamais être 1, donc il n'y a pas d'arc, donc il peut être supprimé. ${\ displaystyle x <y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$

La cohérence d'arc peut également être définie par rapport à une contrainte binaire spécifique: une contrainte binaire est cohérente avec l'arc si chaque valeur d'une variable a une valeur de la deuxième variable telle qu'elle satisfait la contrainte. Cette définition de la cohérence de l'arc est similaire à celle ci-dessus, mais est spécifique à une contrainte. Cette différence est particulièrement pertinente pour les problèmes non normalisés, où la définition ci-dessus prendrait en compte toutes les contraintes entre deux variables alors que celle-ci n'en considère qu'une spécifique.

La cohérence de l'arc est appliquée en supprimant 1 comme valeur de x2. En conséquence, x3 n'est plus cohérent avec l'arc de x2 car x3 = 2 ne correspond pas à une valeur pour x2.

Si une variable n'est pas cohérente avec une autre, cela peut être fait en supprimant certaines valeurs de son domaine. C'est la forme de propagation de contrainte qui impose la cohérence d'arc: elle supprime, du domaine de la variable, toute valeur qui ne correspond pas à une valeur de l'autre variable. Cette transformation maintient les solutions aux problèmes, car les valeurs supprimées ne sont de toute façon pas en solution.

La propagation des contraintes peut rendre l'ensemble du problème cohérent en répétant cette suppression pour toutes les paires de variables. Ce processus peut devoir considérer plusieurs fois une paire donnée de variables. En effet, la suppression de valeurs du domaine d'une variable peut faire en sorte que d'autres variables ne deviennent plus cohérentes avec elle. Par exemple, si est conforme à l'arc mais que l'algorithme réduit le domaine de , la cohérence d'arc de avec ne tient plus et doit être à nouveau appliquée. ${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$

Un algorithme simpliste passerait en revue les paires de variables, imposant la cohérence d'arc, répétant le cycle jusqu'à ce qu'aucun domaine ne change pendant un cycle entier. L' algorithme AC-3 améliore cet algorithme en ignorant les contraintes qui n'ont pas été modifiées depuis leur dernière analyse. En particulier, il fonctionne sur un ensemble de contraintes qui les contient initialement toutes; à chaque étape, il prend une contrainte et impose la cohérence d'arc; si cette opération a pu produire une violation de la cohérence d'arc sur une autre contrainte, elle la replace dans l'ensemble des contraintes à analyser. De cette façon, une fois que la cohérence d'arc est appliquée à une contrainte, cette contrainte n'est plus considérée à moins que le domaine d'une de ses variables ne soit changé.

Cohérence du chemin

x1 et x2 ne sont pas cohérents avec x3. Ils peuvent être rendus cohérents en supprimant les valeurs bleues de R12.

La cohérence de chemin est une propriété similaire à la cohérence d'arc, mais prend en compte des paires de variables au lieu d'une seule. Une paire de variables est cohérente avec une troisième variable si chaque évaluation cohérente de la paire peut être étendue à l'autre variable de telle manière que toutes les contraintes binaires sont satisfaites. Formellement, et sont chemin cohérent avec if, pour chaque paire de valeurs qui satisfait la contrainte binaire entre et , il existe une valeur dans le domaine de tel que et satisfait la contrainte entre et et entre et , respectivement. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {k}}$${\ displaystyle (a, b)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle c}$${\ displaystyle x_ {k}}$${\ displaystyle (a, c)}$${\ displaystyle (b, c)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {k}}$

La forme de propagation de contrainte qui applique la cohérence de chemin fonctionne en supprimant une affectation satisfaisante d'une contrainte. En effet, la cohérence de chemin peut être appliquée en supprimant d'une contrainte binaire toutes les évaluations qui ne peuvent pas être étendues à une autre variable. En ce qui concerne la cohérence d'arc, cette suppression pourrait devoir considérer une contrainte binaire plus d'une fois. En ce qui concerne la cohérence de l'arc, le problème résultant a les mêmes solutions que l'original, car les valeurs supprimées ne sont pas en solution.

Deux variables ne faisant pas partie d'une contrainte peuvent être considérées comme liées par une contrainte virtuelle autorisant toute paire de valeurs possible, représentée par les bords bleus sur cette figure.

L'application de la cohérence de chemin de x1 et x2 avec x3 supprime le bord en haut. Les valeurs de x1 et x2 ne sont plus libres, mais liées par une nouvelle contrainte réelle.

La forme de propagation de contraintes qui renforce la cohérence des chemins peut introduire de nouvelles contraintes. Lorsque deux variables ne sont pas liées par une contrainte binaire, elles sont virtuellement liées par la contrainte autorisant n'importe quelle paire de valeurs. Cependant, certaines paires de valeurs peuvent être supprimées par propagation de contraintes. La contrainte résultante n'est plus satisfaite par toutes les paires de valeurs. Il ne s’agit donc plus d’une contrainte virtuelle et triviale.

Le nom «cohérence de chemin» dérive de la définition originale, qui impliquait une paire de variables et un chemin entre elles, plutôt qu'une paire et une seule variable. Bien que les deux définitions soient différentes pour une seule paire de variables, elles sont équivalentes en se référant à l'ensemble du problème.

Généralisations

La cohérence d'arc et de chemin peut être généralisée à des contraintes non binaires en utilisant des tuples de variables au lieu d'un seul ou d'une paire. Un tuple de variables est - cohérent avec une autre variable si chaque évaluation cohérente des variables peut être étendue avec une valeur de l'autre variable tout en préservant la cohérence. Cette définition s'étend à des problèmes entiers de manière évidente. La forte cohérence est la cohérence pour tous . ${\ displaystyle i-1}$${\ displaystyle i}$${\ displaystyle i-1}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle j \ leq i}$

Le cas particulier de la cohérence 2 coïncide avec la cohérence de l'arc (tous les problèmes sont supposés cohérents avec les nœuds dans cet article). D'un autre côté, la cohérence 3 coïncide avec la cohérence de chemin uniquement si toutes les contraintes sont binaires, car la cohérence de chemin n'implique pas de contraintes ternaires, contrairement à la cohérence 3.

Une autre façon de généraliser la cohérence d'arc est la cohérence d' hyper-arc ou la cohérence d'arc généralisée , qui nécessite l'extensibilité d'une seule variable afin de satisfaire une contrainte. A savoir, une variable est hyper-arc cohérente avec une contrainte si chaque valeur de la variable peut être étendue aux autres variables de la contrainte de telle manière que la contrainte est satisfaite.

Cohérence et satisfiabilité

Cette instance est cohérente avec l'arc et ne contient aucun domaine vide, mais n'a pas de solution. Les lignes bleues indiquent les affectations forcées par le choix x1 = 1.

La propagation de contraintes (imposant une forme de cohérence locale) peut produire un domaine vide ou une contrainte insatisfiable . Dans ce cas, le problème n'a pas de solution. L'inverse n'est pas vrai en général: une instance incohérente peut être cohérente en arc ou en chemin tout en n'ayant pas de domaine vide ou de contrainte insatisfiable.

En effet, la cohérence locale n'est que relative à la cohérence des groupes de variables. Par exemple, la cohérence d'arc garantit que chaque évaluation cohérente d'une variable peut être étendue de manière cohérente à une autre variable. Cependant, lorsqu'une valeur unique d'une variable est étendue à deux autres variables, il n'y a aucune garantie que ces deux valeurs soient cohérentes l'une avec l'autre. Par exemple, peut être cohérent avec et avec , mais ces deux évaluations peuvent ne pas être cohérentes l'une avec l'autre. ${\ displaystyle x_ {1} = 1}$${\ displaystyle x_ {2} = 1}$${\ displaystyle x_ {3} = 1}$

Cependant, la propagation de contraintes peut être utilisée pour prouver la satisfiabilité dans certains cas. Un ensemble de contraintes binaires qui est cohérent avec l'arc et qui n'a pas de domaine vide ne peut être incohérent que si le réseau de contraintes contient des cycles. En effet, si les contraintes sont binaires et forment un graphe acyclique, les valeurs peuvent toujours être propagées à travers les contraintes: pour chaque valeur d'une variable, toutes les variables d'une contrainte avec elle ont une valeur satisfaisant cette contrainte. Par conséquent, une solution peut être trouvée en choisissant de manière itérative une variable non affectée et en se propageant récursivement entre les contraintes. Cet algorithme n'essaie jamais d'attribuer une valeur à une variable déjà affectée, car cela impliquerait l'existence de cycles dans le réseau de contraintes.

Une condition similaire est valable pour la cohérence du chemin. Les cas particuliers dans lesquels la satisfiabilité peut être établie en imposant la cohérence d'arc et la cohérence de chemin sont les suivants.

1. l'application de la cohérence d'arc établit la satisfiabilité des problèmes constitués de contraintes binaires sans cycles (un arbre de contraintes binaires);
2. l'application de la cohérence de chemin établit la satisfiabilité pour les contraintes binaires (éventuellement avec des cycles) avec des domaines binaires;
3. l'application d'une forte cohérence établit la satisfiabilité des problèmes contenant des variables.${\ displaystyle n}$${\ displaystyle n}$

Cas spéciaux

Certaines définitions ou résultats concernant la cohérence relative ne sont valables que dans des cas particuliers.

Lorsque les domaines sont composés d' entiers , la cohérence liée peut être définie. Cette forme de cohérence est basée sur la cohérence des valeurs extrêmes des domaines, c'est-à-dire des valeurs minimum et maximum qu'une variable peut prendre.

Lorsque les contraintes sont algébriques ou booléennes , la cohérence d'arc équivaut à ajouter une nouvelle contrainte ou à modifier syntaxiquement une ancienne, et cela peut être fait en composant de manière appropriée des contraintes.

Contraintes spécialisées

Certains types de contraintes sont couramment utilisés. Par exemple, la contrainte selon laquelle certaines variables sont toutes différentes est souvent utilisée. Il existe des algorithmes spécialisés efficaces pour appliquer la cohérence d'arc sur de telles contraintes.

La contrainte imposant à un certain nombre de variables d'être différent est généralement écrite ou . Cette contrainte équivaut à la non-égalité de toutes les paires de variables différentes, c'est-à-dire pour toutes . Lorsque le domaine d'une variable est réduit à une seule valeur, cette valeur peut être supprimée de tous les autres domaines par propagation de contraintes lors de l'application de la cohérence d'arc. L'utilisation de la contrainte spécialisée permet d'exploiter des propriétés qui ne sont pas valables pour les diséquations binaires individuelles . ${\ displaystyle \ mathop {\ rm {alldifferent}} (x_ {1}, \ ldots, x_ {n})}$alldifferent([X1,...,Xn])${\ displaystyle x_ {i} \ not = x_ {j}}$${\ displaystyle i \ not = j}$

Une première propriété est que le nombre total d'éléments dans les domaines de toutes les variables doit être au moins égal au nombre de variables. Plus précisément, une fois la cohérence d'arc appliquée, le nombre de variables non attribuées ne doit pas dépasser le nombre de valeurs dans l'union de leurs domaines. Sinon, la contrainte ne peut pas être satisfaite. Cette condition peut être vérifiée facilement sur une contrainte dans le alldifferentformulaire, mais ne correspond pas à la cohérence d'arc du réseau de déséquilibres. Une deuxième propriété de la alldifferentcontrainte unique est que la cohérence d'hyper-arc peut être efficacement vérifiée à l'aide d'un algorithme d' appariement bipartite . En particulier, un graphe est construit avec des variables et des valeurs en tant que deux ensembles de nœuds, et un algorithme spécialisé de correspondance de graphes bipartis est exécuté dessus pour vérifier l'existence d'une telle correspondance.

Un autre type de contrainte couramment utilisé est cumulativecelui. Il a été introduit pour des problèmes d'horaire et de placement. A titre d'exemple, cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)peut être utilisé pour formaliser la condition dans laquelle il y a des mactivités, chacune avec l'heure de début si, la durée diet l'utilisation d'une quantité ride ressource. La contrainte indique que la quantité totale de ressources disponibles est L. Il existe des techniques spécialisées de propagation de contraintes pour les contraintes cumulatives; différentes techniques sont utilisées selon les domaines variables déjà réduits à une seule valeur.

Une troisième contrainte spécialisée qui est utilisée dans la programmation logique de contraintes est elementcelle. Dans la programmation de logique de contrainte, les listes sont autorisées comme valeurs de variables. Une contrainte element(I, L, X)est satisfaite si Lest une liste et Xest le I-ème élément de cette liste. Il existe des règles de propagation de contraintes spécialisées pour ces contraintes. Par exemple, si Let Isont réduits à un domaine à valeur unique, une valeur unique pour Xpeut être déterminée. Plus généralement, des valeurs impossibles de Xpeuvent être déduites du domaine de et vice versa. ${\ displaystyle I}$

Cohérence directionnelle

La cohérence directionnelle est la variante d'arc, de chemin et de cohérence conçue pour être utilisée par un algorithme qui attribue des valeurs aux variables en suivant un ordre donné de variables. Ils sont similaires à leurs homologues non directionnels, mais nécessitent seulement qu'une affectation cohérente à certaines variables puisse être étendue de manière cohérente à une autre variable plus grande qu'eux selon l'ordre. ${\ displaystyle i}$

Arc directionnel et cohérence du chemin

Une instance qui est directionnellement cohérente d'arc selon l'ordre x1 x2 x3 mais non cohérente d'arc (aucune contrainte n'est présente entre x1 et x3; arêtes correspondantes omises). Chaque valeur d'une variable d'indice inférieur correspond aux valeurs de variables d'indice supérieur. Les points d'interrogation indiquent les points où l'inverse ne tient pas.

Si un algorithme évalue les variables dans l'ordre , la cohérence n'est utile que lorsqu'il garantit que les valeurs des variables d'indice inférieur sont toutes cohérentes avec les valeurs des variables d'indice supérieur. ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$

Lors du choix d'une valeur pour une variable, les valeurs qui ne correspondent pas à toutes les valeurs d'une variable non affectée peuvent être négligées. En effet, même si ces valeurs sont toutes cohérentes avec l'évaluation partielle actuelle, l'algorithme échouera par la suite à trouver une valeur cohérente pour la variable non attribuée. En revanche, il n'est pas nécessaire de renforcer la cohérence avec les variables déjà évaluées: si l'algorithme choisit une valeur qui n'est pas cohérente avec l'évaluation partielle en cours, une incohérence est quand même détectée.

En supposant que l'ordre d'évaluation des variables est , un problème de satisfaction de contrainte est directionnellement cohérent si chaque variable est cohérente avec toute autre variable telle que . La cohérence du chemin directionnel est similaire, mais deux variables doivent être cohérentes avec le chemin uniquement si . Une forte cohérence de trajectoire directionnelle signifie à la fois une cohérence de trajectoire directionnelle et une cohérence d'arc directionnel. Des définitions similaires peuvent être données pour les autres formes de cohérence. ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle i <j}$${\ displaystyle x_ {i}, x_ {j}}$${\ displaystyle x_ {z}}$${\ Displaystyle i, j <z}$

Propagation des contraintes pour la cohérence de l'arc et du chemin

La propagation des contraintes imposant la cohérence de l'arc directionnel itère sur les variables de la dernière à la première, imposant à chaque étape la cohérence de l'arc de chaque variable d'indice inférieur avec elle. Si l'ordre des variables est , cet algorithme itère sur les variables de à ; pour variable , il applique la cohérence d'arc de chaque variable d'indice inférieur à avec . ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {n}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {j}}$${\ displaystyle j}$${\ displaystyle x_ {j}}$

Une instance qui n'est pas cohérente d'arc directionnel: ne correspond à aucune valeur de et ne correspond à aucune valeur de . Aucune contrainte n'est présente entre et (les arêtes correspondantes sont omises). ${\ displaystyle x_ {1} = 2}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$${\ displaystyle x_ {3}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {3}}$	L'application de la cohérence d'arc directionnel commence par et rend l' arc cohérent en supprimant la valeur . ${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$	L'application de la cohérence de l'arc directionnel se poursuit . Depuis a déjà été supprimé, les deux et sont supprimés. ${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$${\ displaystyle x_ {1} = 2}$${\ displaystyle x_ {1} = 3}$

La cohérence de chemin directionnel et la cohérence de chemin directionnel forte peuvent être appliquées par des algorithmes similaires à celui de la cohérence de l'arc. Ils traitent les variables de à ; pour chaque variable, deux variables avec sont prises en compte et leur cohérence de chemin avec est appliquée. Aucune opération n'est requise si le problème ne contient aucune contrainte sur et ou aucune contrainte entre et . Cependant, même s'il n'y a pas de contrainte entre et , une contrainte triviale est supposée. Si la propagation de contraintes réduit son ensemble d'affectations satisfaisantes, elle crée effectivement une nouvelle contrainte non triviale. La propagation de contraintes imposant une forte cohérence de chemin directionnel est similaire, mais renforce également la cohérence de l'arc. ${\ displaystyle x_ {n}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {i}, x_ {j}}$${\ Displaystyle i, j <z}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$

Cohérence directionnelle et satisfiabilité

La cohérence directionnelle garantit que les solutions partielles satisfaisant une contrainte peuvent être systématiquement étendues à une autre variable d'indice plus élevé. Cependant, cela ne garantit pas que les extensions de différentes variables sont cohérentes les unes avec les autres. Par exemple, une solution partielle peut être systématiquement étendue à variable ou à variable , mais pourtant ces deux extensions ne sont pas cohérentes l'une avec l'autre. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$

Il y a deux cas dans lesquels cela ne se produit pas et la cohérence directionnelle garantit la satisfiabilité si aucun domaine n'est vide et qu'aucune contrainte n'est insatisfaisable.

Le premier cas est celui d'un problème de contrainte binaire avec un ordre des variables qui fait que le graphe ordonné de contraintes a une largeur 1. Un tel ordre existe si et seulement si le graphe de contraintes est un arbre. Si tel est le cas, la largeur du graphique limite le nombre maximal de nœuds inférieurs (selon l'ordre) auxquels un nœud est joint. La cohérence de l'arc directionnel garantit que chaque affectation cohérente à une variable peut être étendue aux nœuds supérieurs, et la largeur 1 garantit qu'un nœud n'est pas joint à plus d'un nœud inférieur. Par conséquent, une fois que la variable inférieure est affectée, sa valeur peut être étendue de manière cohérente à chaque variable supérieure avec laquelle elle est jointe. Cette extension ne peut pas conduire ultérieurement à une incohérence. En effet, aucune autre variable inférieure n'est jointe à cette variable supérieure, car le graphique a une largeur de 1.

En conséquence, si un problème de contrainte a la largeur 1 par rapport à un ordre de ses variables (ce qui implique que son graphe correspondant est un arbre) et que le problème est directionnellement cohérent par rapport au même ordre, une solution (le cas échéant) peuvent être trouvés en attribuant itérativement des variables en fonction de l'ordre.

Le second cas dans lequel la cohérence directionnelle garantit la satisfiabilité si aucun domaine n'est vide et qu'aucune contrainte n'est insatisfaisable est celui des problèmes de contraintes binaires dont le graphe a induit une largeur 2, en utilisant une forte cohérence de chemin directionnel. En effet, cette forme de cohérence garantit que chaque affectation à une variable ou à une paire de variables peut être étendue à une variable supérieure, et width 2 garantit que cette variable n'est pas jointe à une autre paire de variables inférieures.

La raison pour laquelle la largeur induite est considérée au lieu de la largeur est que l'application de la cohérence de chemin directionnel peut ajouter des contraintes. En effet, si deux variables ne sont pas dans la même contrainte mais sont dans une contrainte avec une variable plus élevée, certaines paires de leurs valeurs peuvent violer la cohérence de chemin. La suppression de ces paires crée une nouvelle contrainte. En conséquence, la propagation de contraintes peut produire un problème dont le graphique a plus d'arêtes que l'original. Cependant, toutes ces arêtes sont nécessairement dans le graphe induit, car elles sont toutes entre deux parents du même nœud. La largeur 2 garantit que chaque évaluation partielle cohérente peut être étendue à une solution, mais cette largeur est relative au graphique généré. En conséquence, une largeur induite de 2 est nécessaire pour une forte cohérence de chemin directionnel afin de garantir l'existence de solutions.

I-cohérence directionnelle

Les lignes bleues indiquent qu'il n'y a pas de contrainte entre x3 et x4, de sorte que chaque paire de valeurs est autorisée. Dans ces images, l'absence d'arêtes entre deux variables indique implicitement l'absence de contrainte. Ce problème a la largeur 2.

La cohérence directionnelle est la garantie que chaque affectation cohérente à des variables peut être étendue de manière cohérente à une autre variable qui est plus élevée dans l'ordre. La forte cohérence directionnelle est définie de la même manière, mais tous les groupes d' au plus variables sont considérés. Si un problème est fortement cohérent dans la direction et a une largeur inférieure à et n'a pas de domaine vide ou de contrainte insatisfaisable, il a des solutions. ${\ displaystyle i}$${\ displaystyle i-1}$${\ displaystyle i}$ ${\ displaystyle i-1}$${\ displaystyle i}$${\ displaystyle i}$

Chaque problème peut être rendu fortement cohérent dans la direction , mais cette opération peut augmenter la largeur de ses graphiques correspondants. La procédure de propagation de contraintes qui assure la cohérence directionnelle est similaire à celle utilisée pour la cohérence de l'arc directionnel et la cohérence du chemin. Les variables sont considérées tour à tour, de la dernière à la première selon l'ordre. Pour la variable , l'algorithme considère chaque groupe de variables qui ont un index inférieur à et sont dans une contrainte avec . La cohérence de ces variables avec est vérifiée et éventuellement appliquée en supprimant les affectations satisfaisantes de la contrainte entre toutes ces variables (le cas échéant, ou en en créant une nouvelle dans le cas contraire). ${\ displaystyle i}$${\ displaystyle x_ {k}}$${\ displaystyle i-1}$${\ displaystyle k}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {k}}$${\ displaystyle i}$

L'application de la cohérence sur x5 supprime la ligne rouge, créant ainsi une nouvelle contrainte non triviale entre x3 et x4. En conséquence, x4 a x3 comme nouveau parent, en plus de x1 et x2. Ce changement augmente la largeur à 3.

Cette procédure génère une instance fortement cohérente directionnelle . Cependant, il peut également ajouter de nouvelles contraintes à l'instance. Par conséquent, même si la largeur du problème d'origine est , la largeur de l'instance résultante peut être plus grande. Si tel est le cas, la cohérence forte directionnelle n'implique pas de satisfiabilité même si aucun domaine n'est vide et qu'aucune contrainte n'est insatisfiable. ${\ displaystyle i}$${\ displaystyle i}$

Cependant, la propagation de contraintes n'ajoute que des contraintes aux variables inférieures à celle qu'elle considère actuellement. En conséquence, aucune contrainte sur une variable n'est modifiée ou ajoutée une fois que l'algorithme a traité cette variable. Au lieu de considérer un fixe , on peut le modifier au nombre de parents de chaque variable considérée (les parents d'une variable sont les variables d'indice inférieur à la variable et qui sont en contrainte avec la variable). Cela correspond à considérer tous les parents d'une variable donnée à chaque étape. En d'autres termes, pour chaque variable de la dernière à la première, tous ses parents sont inclus dans une nouvelle contrainte qui limite leurs valeurs à celles qui sont cohérentes avec . Puisque cet algorithme peut être vu comme une modification du précédent avec une valeur qui est changée en nombre de parents de chaque nœud, il est appelé cohérence adaptative . ${\ displaystyle i}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle i}$

Cet algorithme applique une cohérence fortement directionnelle égale à la largeur induite du problème. L'instance résultante est satisfiable si et seulement si aucun domaine ou contrainte n'est rendu vide. Si tel est le cas, une solution peut être facilement trouvée en définissant de manière itérative une variable non affectée sur une valeur arbitraire et en propageant cette évaluation partielle à d'autres variables. Cet algorithme n'est pas toujours polynomial-temps, car le nombre de contraintes introduites en imposant une forte cohérence directionnelle peut produire une augmentation exponentielle de la taille. Le problème peut cependant être résolu en temps polynomial si la forte cohérence directionnelle imposante n'agrandit pas superpolynomialement l'instance. En conséquence, si une instance a une largeur induite limitée par une constante, elle peut être résolue en temps polynomial. ${\ displaystyle i}$${\ displaystyle i}$

Élimination du godet

L'élimination de seau est un algorithme de satisfiabilité. Il peut être défini comme une reformulation de la cohérence adaptative. Ses définitions utilisent des buckets, qui sont des conteneurs de contrainte, chaque variable ayant un bucket associé. Une contrainte appartient toujours au compartiment de sa variable la plus élevée.

L'algorithme d'élimination de compartiment procède à son tour de la variable la plus élevée à la variable la plus basse. A chaque étape, les contraintes dans les buckets de cette variable sont considérées. Par définition, ces contraintes n'impliquent que des variables inférieures à . L'algorithme modifie la contrainte entre ces variables inférieures (le cas échéant, sinon il en crée une nouvelle). En particulier, il impose à leurs valeurs d'être extensibles de manière cohérente avec les contraintes du seau de . Cette nouvelle contrainte, le cas échéant, est ensuite placée dans le compartiment approprié. Étant donné que cette contrainte n'implique que des variables inférieures à , elle est ajoutée à un compartiment d'une variable inférieure à . ${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$

Cet algorithme équivaut à appliquer la cohérence adaptative. Puisqu'ils appliquent tous les deux la cohérence d'une variable avec tous ses parents et qu'aucune nouvelle contrainte n'est ajoutée après la prise en compte d'une variable, il en résulte une instance qui peut être résolue sans retour en arrière .

Puisque le graphe de l'instance qu'ils produisent est un sous-graphe du graphe induit, si la largeur induite est limitée par une constante, l'instance générée est de taille polynomiale dans la taille de l'instance d'origine. En conséquence, si la largeur induite d'une instance est limitée par une constante, sa résolution peut être effectuée en temps polynomial par les deux algorithmes.

Cohérence relationnelle

Alors que les définitions précédentes de la cohérence concernent la cohérence des affectations, la cohérence relationnelle implique la satisfaction d'une contrainte ou d'un ensemble de contraintes donné uniquement. Plus précisément, la cohérence relationnelle implique que chaque affectation partielle cohérente peut être étendue de telle sorte qu'une contrainte ou un ensemble de contraintes donné soit satisfait. Formellement, une contrainte sur les variables est cohérente avec l'une de ses variables si chaque affectation cohérente à peut être étendue de cette manière est satisfaite. La différence entre la cohérence «régulière» et la cohérence de l'arc relationnel est que cette dernière ne nécessite que l'affectation étendue pour satisfaire une contrainte donnée, tandis que la première exige qu'elle satisfasse toutes les contraintes pertinentes. ${\ displaystyle C}$${\ displaystyle X}$${\ displaystyle x}$${\ displaystyle X \ backslash \ {x \}}$${\ displaystyle x}$${\ displaystyle C}$${\ displaystyle i}$

I-cohérence (régulière): si une évaluation est cohérente, elle peut être étendue à une autre variable de manière à ce que toutes les contraintes pertinentes soient satisfaites.

Cohérence de l'arc relationnel: si une évaluation sur les variables d'une contrainte mais une est cohérente, elle peut toujours être étendue à cette variable de manière à ce que la contrainte soit satisfaite. Les arêtes cyan représentent des contraintes qui ne doivent pas être satisfaites par l'extension.

Cette définition peut être étendue à plus d'une contrainte et à plusieurs variables. En particulier, la cohérence de chemin relationnel est similaire à la cohérence d'arc relationnelle, mais deux contraintes sont utilisées à la place d'une. Deux contraintes sont un chemin relationnel cohérent avec une variable si chaque affectation cohérente à toutes leurs variables mais celle considérée peut être étendue de telle manière que les deux contraintes sont satisfaites.

Pour plus de deux contraintes, la cohérence relationnelle est définie. La cohérence relationnelle implique un ensemble de contraintes et une variable qui est dans le champ de toutes ces contraintes. En particulier, ces contraintes sont relationnelles - cohérentes avec la variable si chaque affectation cohérente à toutes les autres variables qui sont dans leurs portées peut être étendue à la variable de telle manière que ces contraintes soient satisfaites. Un problème est - relationnel cohérent si chaque ensemble de contraintes est relationnel - cohérent avec chaque variable qui est dans toutes leurs portées. Une forte cohérence relationnelle est définie comme ci-dessus: c'est la propriété d'être cohérente relationnelle pour tout . ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle k}$${\ Displaystyle k <m}$

La cohérence relationnelle peut également être définie pour plusieurs variables au lieu d'une. Un ensemble de contraintes est relationnel- cohérent si chaque affectation cohérente à un sous-ensemble de leurs variables peut être étendue à une évaluation à toutes les variables qui satisfont toutes les contraintes. Cette définition ne prolonge pas exactement ce qui précède car les variables auxquelles les évaluations sont censées être extensibles ne sont pas nécessairement dans toutes les portées des contraintes impliquées. ${\ displaystyle m}$${\ displaystyle (i, m)}$${\ displaystyle i}$

Si un ordre des variables est donné, la cohérence relationnelle peut être limitée aux cas où la ou les variables d'évaluation devraient être extensibles pour suivre les autres variables dans l'ordre. Cette condition modifiée est appelée cohérence relationnelle directionnelle.

Cohérence relationnelle et satisfiabilité

Un problème de satisfaction de contraintes peut être relationnellement cohérent, ne pas avoir de domaine vide ni de contrainte insatisfaisable, et pourtant être insatisfaisable. Il existe cependant certains cas dans lesquels cela n'est pas possible.

Le premier cas est celui d' un problème fortement relationnel- cohérent lorsque les domaines contiennent au plus des éléments. Dans ce cas, une évaluation cohérente des variables peut toujours être étendue à une seule autre variable. Si est une telle évaluation et est la variable, il n'y a que des valeurs possibles que la variable peut prendre. Si toutes ces valeurs ne sont pas cohérentes avec l'évaluation, il existe des contraintes (non nécessairement uniques) qui sont violées par l'évaluation et l'une de ses valeurs possibles. En conséquence, l'évaluation ne peut pas être étendue pour satisfaire toutes ces contraintes -ou moins, violant la condition de forte cohérence relationnelle . ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle k}$${\ displaystyle x_ {1} = a_ {1}, \ ldots, x_ {k} = a_ {k}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$

Le deuxième cas est lié à une mesure des contraintes, plutôt que des domaines. Une contrainte est -tight si chaque évaluation à toutes ses variables sauf une peut être étendue pour satisfaire la contrainte soit par toutes les valeurs possibles de l'autre variable, soit par au plus de ses valeurs. Un problème ayant des contraintes-serrées est satisfiable si et seulement si elles sont fortement cohérentes sur le plan relationnel . ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m + 1}$

Une matrice de ligne convexe: les 1 de chaque ligne sont contigus (aucun 0 entre eux).

Le troisième cas est celui des contraintes binaires qui peuvent être représentées par des matrices en ligne convexe. Une contrainte binaire peut être représentée par une matrice bidimensionnelle , où vaut 0 ou 1 selon que la -ème valeur du domaine de et la -ème valeur du domaine de satisfont à la contrainte. Une ligne de cette matrice est convexe si les 1 qu'elle contient sont consécutifs (formellement, si deux éléments sont 1, tous les éléments intermédiaires sont également 1). Une matrice est convexe en ligne si toutes ses lignes sont convexes. ${\ displaystyle M}$${\ displaystyle M_ {ij}}$${\ displaystyle i}$${\ displaystyle x_ {i}}$${\ displaystyle j}$${\ displaystyle x_ {j}}$

Chaque matrice représente la contrainte entre x _i et x _{k +1} . Si a ₁ ... a _k sont des valeurs pour x ₁ ... x _k , les lignes de a ₁ ... a _k dans chaque matrice indiquent les valeurs autorisées pour x _{k +1} . La convexité des lignes et la forte cohérence des chemins relationnels impliquent l'existence d'une valeur cohérente a _{k +1} pour x _{k +1} .

La condition qui rend une forte cohérence de chemin relationnel équivalente à la satisfiabilité est celle des problèmes de satisfaction de contraintes pour lesquels il existe un ordre des variables qui fait que toutes les contraintes sont représentées par des matrices convexes en ligne. Ce résultat est basé sur le fait qu'un ensemble de lignes convexes ayant un élément commun par paires ont également un élément globalement commun. En considérant une évaluation sur des variables, les valeurs autorisées pour la -th sont données en sélectionnant des lignes à partir de certaines contraintes. En particulier, pour chaque variable parmi celles-ci, la ligne relative à sa valeur dans la matrice représentant la contrainte la reliant à l' une représente les valeurs autorisées de cette dernière. Étant donné que ces lignes sont convexes et qu'elles ont un élément commun par paires en raison de la cohérence du chemin, elles ont également un élément commun partagé, qui représente une valeur de la dernière variable cohérente avec les autres. ${\ displaystyle k}$${\ displaystyle k + 1}$${\ displaystyle k}$${\ displaystyle k + 1}$

Utilisations de la cohérence locale

Toutes les formes de cohérence locale peuvent être imposées par la propagation de contraintes, ce qui peut réduire les domaines de variables et les ensembles d'affectations satisfaisant une contrainte et peut introduire de nouvelles contraintes. Chaque fois que la propagation d'une contrainte produit un domaine vide ou une contrainte insatisfaisable, le problème d'origine n'est pas satisfaisable. Par conséquent, toutes les formes de cohérence locale peuvent être utilisées comme approximations de la satisfiabilité. Plus précisément, ils peuvent être utilisés comme des algorithmes d'insatisfaisabilité incomplets, car ils peuvent prouver qu'un problème n'est pas satisfaisable, mais sont en général incapables de prouver qu'un problème est satisfiable. Ces algorithmes approchées peuvent être utilisés par des algorithmes de recherche ( retours en arrière , backjumping , recherche locale , etc.) heuristiques pour dire si une solution partielle peut être étendue pour répondre à toutes les contraintes , sans autre analyse.

Même si la propagation de contraintes ne produit pas un domaine vide ou une contrainte insatisfaisable, elle peut néanmoins réduire les domaines ou renforcer les contraintes. Si tel est le cas, l' espace de recherche du problème est réduit, réduisant ainsi la quantité de recherche nécessaire pour résoudre le problème.

La cohérence locale prouve la satisfiabilité dans certains cas restreints (voir Complexité de la satisfaction des contraintes # Restrictions ). C'est le cas pour certains types particuliers de problèmes et / ou pour certains types de cohérence locale. Par exemple, appliquer la cohérence d'arc sur des problèmes acycliques binaires permet de dire si le problème est satisfaisable. L'application d'une forte cohérence directionnelle permet de dire la satisfiabilité des problèmes qui ont induit une largeur selon le même ordre. La cohérence directionnelle adaptative permet de dire la satisfiabilité d'un problème arbitraire. ${\ displaystyle i}$${\ displaystyle i-1}$

Voir également

• Propagation unitaire
• Programmation par contraintes
• Programmation de logique de contrainte
• Look-ahead (retour en arrière)

Liens externes

• Propagation des contraintes - Mémoire de Guido Tack donnant un bon aperçu des problèmes de théorie et de mise en œuvre

Les références

• Lecoutre, Christophe (2009). Réseaux de contraintes: techniques et algorithmes . ISTE / Wiley. ISBN  978-1-84821-106-3
• Dechter, Rina (2003). Traitement des contraintes . Morgan Kaufmann. ISBN  1-55860-890-7
• Apt, Krzysztof (2003). Principes de la programmation par contraintes . La presse de l'Universite de Cambridge. ISBN  0-521-82583-0
• Marriott, Kim; Peter J. Stuckey (1998). Programmation avec contraintes: une introduction . MIT Press. ISBN  0-262-13341-5