Problème de satisfaction de contraintes

Les problèmes de satisfaction de contraintes ( CSP ) sont des problèmes mathématiques définis comme un ensemble d'objets dont l'état doit satisfaire un certain nombre de contraintes ou de limitations . Les CSP représentent les entités d'un problème comme une collection homogène de contraintes finies sur des variables , qui est résolue par des méthodes de satisfaction de contraintes . Les CSP font l'objet de recherches en intelligence artificielle et en recherche opérationnelle , car la régularité de leur formulation fournit une base commune pour analyser et résoudre des problèmes de nombreuses familles apparemment sans rapport. Les CSP présentent souvent une grande complexité , nécessitant une combinaison d' heuristiques et de méthodes de recherche combinatoire pour être résolus dans un délai raisonnable. La programmation par contraintes (CP) est le domaine de recherche qui se concentre spécifiquement sur la résolution de ce type de problèmes. De plus, le problème de satisfaction booléenne (SAT), les théories de satisfaction modulo (SMT), la programmation mixte en nombres entiers (MIP) et la programmation par ensemble de réponses (ASP) sont tous des domaines de recherche axés sur la résolution de formes particulières du problème de satisfaction des contraintes.

Voici des exemples de problèmes qui peuvent être modélisés comme un problème de satisfaction de contraintes :

• Inférence de type
• Puzzle des huit reines
• Problème de coloriage de carte
• Problème de coupe maximale
• Sudoku , mots croisés , futoshiki , Kakuro (sommes croisées), Numbrix / Hidato et bien d'autres puzzles logiques

Ceux-ci sont souvent fournis avec des tutoriels de résolution CP , ASP, Boolean SAT et SMT. Dans le cas général, les problèmes de contraintes peuvent être beaucoup plus difficiles et peuvent ne pas être exprimables dans certains de ces systèmes plus simples. Les exemples de la « vie réelle » incluent la planification automatisée , la désambiguïsation lexicale , la musicologie , la configuration de produit et l'allocation de ressources .

L'existence d'une solution à un CSP peut être considérée comme un problème de décision . Cela peut être décidé en trouvant une solution, ou en ne parvenant pas à trouver une solution après une recherche exhaustive ( les algorithmes stochastiques n'atteignent généralement jamais une conclusion exhaustive, alors que les recherches dirigées y parviennent souvent, sur des problèmes suffisamment petits). Dans certains cas, le CSP peut être connu à l'avance pour avoir des solutions, grâce à un autre processus d'inférence mathématique.

Formellement, un problème de satisfaction de contraintes est défini comme un triplet , où

Chaque variable peut prendre les valeurs du domaine non vide . Chaque contrainte est à son tour une paire , où est un ensemble d' indices et est une relation -aire sur le produit correspondant de domaines où le produit est pris avec des indices dans l'ordre croissant. Une évaluation des variables est une fonction d'un sous-ensemble de variables sur un ensemble particulier de valeurs dans le sous-ensemble correspondant de domaines. Une évaluation satisfait une contrainte si les valeurs attribuées aux variables satisfont la relation .

Une évaluation est cohérente si elle ne viole aucune des contraintes. Une évaluation est complète si elle inclut toutes les variables. Une évaluation est une solution si elle est cohérente et complète ; on dit qu'une telle évaluation résout le problème de satisfaction des contraintes.

Les problèmes de satisfaction de contraintes sur des domaines finis sont généralement résolus à l'aide d'une forme de recherche . Les techniques les plus utilisées sont des variantes de rétro-suivi , de propagation de contraintes et de recherche locale . Ces techniques sont également souvent combinées, comme dans la méthode VLNS , et les recherches actuelles impliquent d'autres technologies telles que la programmation linéaire .

Le backtracking est un algorithme récursif. Il maintient une affectation partielle des variables. Au départ, toutes les variables ne sont pas affectées. À chaque étape, une variable est choisie, et toutes les valeurs possibles lui sont affectées à tour de rôle. Pour chaque valeur, la cohérence de l'affectation partielle avec les contraintes est vérifiée ; en cas de cohérence, un appel récursif est effectué. Lorsque toutes les valeurs ont été essayées, l'algorithme effectue un backtracking. Dans cet algorithme de backtracking de base, la cohérence est définie comme la satisfaction de toutes les contraintes dont les variables sont toutes affectées. Il existe plusieurs variantes du backtracking. Le backmarking améliore l'efficacité de la vérification de la cohérence. Le backjumping permet d'économiser une partie de la recherche en effectuant un backtracking sur « plus d'une variable » dans certains cas. L'apprentissage par contrainte déduit et enregistre de nouvelles contraintes qui peuvent être utilisées ultérieurement pour éviter une partie de la recherche. Le look-ahead est également souvent utilisé dans le backtracking pour tenter de prévoir les effets du choix d'une variable ou d'une valeur, déterminant ainsi parfois à l'avance quand un sous-problème est satisfaisable ou insatisfaisable.

Les techniques de propagation de contraintes sont des méthodes utilisées pour modifier un problème de satisfaction de contraintes. Plus précisément, ce sont des méthodes qui imposent une forme de cohérence locale , qui sont des conditions liées à la cohérence d'un groupe de variables et/ou de contraintes. La propagation de contraintes a diverses utilisations. Tout d'abord, elle transforme un problème en un problème équivalent mais généralement plus simple à résoudre. Ensuite, elle peut prouver la satisfiabilité ou l'insatisfiabilité des problèmes. Il n'est pas garanti que cela se produise en général ; cependant, cela se produit toujours pour certaines formes de propagation de contraintes et/ou pour certains types de problèmes. Les formes de cohérence locale les plus connues et les plus utilisées sont la cohérence d'arc , la cohérence d'hyper-arc et la cohérence de chemin . La méthode de propagation de contraintes la plus populaire est l' algorithme AC-3 , qui impose la cohérence d'arc.

Les méthodes de recherche locale sont des algorithmes de satisfiabilité incomplète. Elles peuvent trouver une solution à un problème, mais elles peuvent échouer même si le problème est satisfiable. Elles fonctionnent en améliorant de manière itérative une affectation complète sur les variables. À chaque étape, un petit nombre de variables sont modifiées en valeur, dans le but global d'augmenter le nombre de contraintes satisfaites par cette affectation. L' algorithme min-conflicts est un algorithme de recherche locale spécifique aux CSP et repose sur ce principe. En pratique, la recherche locale semble bien fonctionner lorsque ces modifications sont également affectées par des choix aléatoires. Une intégration de la recherche avec la recherche locale a été développée, conduisant à des algorithmes hybrides .

Les CSP sont également étudiés dans la théorie de la complexité computationnelle , la théorie des modèles finis et l'algèbre universelle . Il s'est avéré que les questions sur la complexité des CSP se traduisent par d'importantes questions d'algèbre universelle sur les algèbres sous-jacentes. Cette approche est connue sous le nom d' approche algébrique des CSP.

Étant donné que chaque problème de décision informatique est équivalent en temps polynomial à un CSP avec un modèle infini, les CSP généraux peuvent avoir une complexité arbitraire. En particulier, il existe également des CSP dans la classe des problèmes NP-intermédiaires , dont l'existence a été démontrée par Ladner , sous l'hypothèse que P ≠ NP .

Cependant, une grande classe de CSP issus d'applications naturelles satisfait une dichotomie de complexité, ce qui signifie que chaque CSP de cette classe est soit en P , soit NP-complet . Ces CSP fournissent ainsi l'un des plus grands sous-ensembles connus de NP qui évite les problèmes NP-intermédiaires . Une dichotomie de complexité a été prouvée pour la première fois par Schaefer pour les CSP booléens, c'est-à-dire les CSP sur un domaine à 2 éléments et où toutes les relations disponibles sont des opérateurs booléens . Ce résultat a été généralisé à diverses classes de CSP, notamment pour tous les CSP sur des domaines finis. Cette conjecture de dichotomie de domaine fini a été formulée pour la première fois par Tomás Feder et Moshe Vardi, et finalement prouvée indépendamment par Andrei Bulatov et Dmitriy Zhuk en 2017.

D’autres classes pour lesquelles une dichotomie de complexité a été confirmée sont

• toutes les réductions du premier ordre de ,
• tous les réduits du premier ordre du graphe aléatoire dénombrable ,
• tous les réduits du premier ordre du compagnon modèle de la classe de toutes les relations C,
• tous les réduits du premier ordre du poset homogène universel ,
• tous les réduits du premier ordre de graphes homogènes non orientés,
• tous les réduits du premier ordre de toutes les structures unaires,
• tous les CSP de la classe de complexité MMSNP.

La plupart des classes de CSP connues pour être traitables sont celles où l' hypergraphe des contraintes a une largeur d'arbre limitée , ou où les contraintes ont une forme arbitraire mais il existe des polymorphismes équationnellement non triviaux de l'ensemble des relations de contraintes.

Une conjecture de dichotomie de domaine infini a été formulée pour tous les CSP de réduits de structures homogènes à bornes finies, affirmant que le CSP d'une telle structure est dans P si et seulement si son clone de polymorphisme est équationnellement non trivial, et NP-difficile sinon.

La complexité de ces CSP à domaine infini ainsi que d'autres généralisations (CSP valorisés, CSP quantifiés, CSP promis) est toujours un domaine de recherche actif. [1][2]

Chaque CSP peut également être considéré comme un problème de confinement de requête conjonctive .

Une situation similaire existe entre les classes fonctionnelles FP et #P . Par une généralisation du théorème de Ladner , il existe également des problèmes ni FP ni #P-complets tant que FP ≠ #P. Comme dans le cas de décision, un problème dans le #CSP est défini par un ensemble de relations. Chaque problème prend une formule booléenne en entrée et la tâche consiste à calculer le nombre d'affectations satisfaisantes. Ceci peut être encore généralisé en utilisant des tailles de domaine plus grandes et en attachant un poids à chaque affectation satisfaisante et en calculant la somme de ces poids. Il est connu que tout problème #CSP pondéré complexe est soit FP soit #P-difficile.

Le modèle classique du problème de satisfaction de contraintes définit un modèle de contraintes statiques et inflexibles. Ce modèle rigide est une lacune qui rend difficile la représentation aisée des problèmes. Plusieurs modifications de la définition de base du problème de satisfaction de contraintes ont été proposées pour adapter le modèle à une grande variété de problèmes.

Les CSP dynamiques ( DCSP s) sont utiles lorsque la formulation originale d'un problème est modifiée d'une manière ou d'une autre, généralement parce que l'ensemble des contraintes à prendre en compte évolue en raison de l'environnement. Les DCSP sont considérés comme une séquence de CSP statiques, chacun étant une transformation du précédent dans lequel des variables et des contraintes peuvent être ajoutées (restriction) ou supprimées (relaxation). Les informations trouvées dans les formulations initiales du problème peuvent être utilisées pour affiner les suivantes. La méthode de résolution peut être classée selon la manière dont les informations sont transférées :

• Oracles : la solution trouvée aux CSP précédents de la séquence est utilisée comme heuristique pour guider la résolution du CSP actuel à partir de zéro.
• Réparation locale : chaque CSP est calculé à partir de la solution partielle du précédent et en réparant les contraintes incohérentes avec une recherche locale .
• Enregistrement des contraintes : de nouvelles contraintes sont définies à chaque étape de la recherche pour représenter l'apprentissage d'un groupe de décisions incohérentes. Ces contraintes sont reportées sur les nouveaux problèmes CSP.

Les CSP classiques traitent les contraintes comme étant dures, ce qui signifie qu'elles sont impératives (chaque solution doit les satisfaire toutes) et inflexibles (dans le sens où elles doivent être complètement satisfaites sinon elles sont complètement violées). Les CSP flexibles assouplissent ces hypothèses, en assouplissant partiellement les contraintes et en permettant à la solution de ne pas les respecter toutes. Cela est similaire aux préférences dans la planification basée sur les préférences . Certains types de CSP flexibles incluent :

• MAX-CSP, où un certain nombre de contraintes peuvent être violées et la qualité d'une solution est mesurée par le nombre de contraintes satisfaites.
• CSP pondéré , un MAX-CSP dans lequel chaque violation d'une contrainte est pondérée selon une préférence prédéfinie. Ainsi, la satisfaction de la contrainte avec plus de poids est préférée.
• Les contraintes du modèle CSP flou sont des relations floues dans lesquelles la satisfaction d'une contrainte est une fonction continue des valeurs de ses variables, allant de totalement satisfaite à totalement violée.

Dans les DCSP chaque variable de contrainte est considérée comme ayant une localisation géographique distincte. De fortes contraintes sont imposées sur l'échange d'informations entre les variables, ce qui nécessite l'utilisation d'algorithmes entièrement distribués pour résoudre le problème de satisfaction des contraintes.