Contributions à la résolution générique des problèmes de satisfaction de contraintes

De très nombreux problèmes logiques, d’aide à la décision ou issus de l’ingénierie des systèmes sont des problèmes combinatoires. Il s’agit de problèmes de décision ou d’optimisation de nature exponentielle : Si on étend linéairement la taille du problème (par exemple, en ajoutant une variable ou une valeur), on multiplie le nombre d’hypothèses à envisager pour résoudre le problème. Ils sont donc extrêmement difficiles à résoudre, pour un humain comme pour un ordinateur, et nécessitent l’utilisation de techniques avancées d’intelligence artificielle ou de recherche opérationnelle pour être résolus par un ordinateur. La programmation par contraintes (PC) a été développée dès les années 70 afin de réussir à formaliser facilement et à résoudre informatiquement de tels problèmes. Les langages de programmation logiques, comme Prolog, ou fonctionnels, comme Lisp, sont des langages déclaratifs, par opposition aux langages impératifs classiques comme Ada ou C. L’objectif derrière ces langages de programmation déclaratifs est de définir une méthode de programmation « intelligente », où un utilisateur non expert n’aurait qu’à définir sa problématique à l’ordinateur et obtenir immédiatement une solution. Les domaines scientifiques ayant trait au développement de tels systèmes ont été depuis regroupés sous l’appellation « Intelligence Artificielle ». Le problème de satisfaction de contraintes (CSP pour Constraint Satisfaction Problem) se situe au cœur de la problématique de la programmation par contraintes. Étant donné un problème combinatoire quelconque formalisé sous forme d’un réseau de contraintes et de variables, l’objectif est de déterminer s’il existe une solution au problème, c’est à dire une instanciation d’une valeur à chaque variable de sorte que toutes les contraintes soient satisfaites. Le problème de satisfaction de contraintes reste un des problèmes combinatoires de référence. Il appartient à la classe de complexité NP, ce qui signifie que l’on conjecture très fortement qu’il n’existe pas d’algorithme capable de résoudre ce problème en temps polynomial, mais qu’il faut obligatoirement utiliser des algorithmes dont les complexités en temps et/ou en espace évoluent exponentiellement avec la taille du problème. Le problème de satisfaction de contrainte est aussi NP-complet, ce qui signifie qu’il capture toute l’essence des problèmes combinatoires. Tout problème NP (qui inclut les classes de complexités plus « faciles ») peut être formalisé sous forme d’un CSP. En améliorant les techniques de résolution pratiques des CSP, on améliore ainsi notre capacité à résoudre tout problème combinatoire. Ces méthodes sont d’ores et déjà utilisées dans de nombreux domaines industriels, comme la planification, l’ordonnancement, le diagnostic, le contrôle d’erreurs dans les circuits électroniques, etc. Deux approches sont couramment utilisées pour résoudre les problèmes de satisfaction de contraintes : l’inférence et la recherche. Les méthodes d’inférence utilisent des propriétés du réseau de contraintes, appelées consistances, pour déduire des informations complémentaires, notamment des valeurs ou des multiplets de valeurs ne pouvant conduire à une solution. Ces méthodes permettent en particulier de réduire fortement la taille du problème, afin de faciliter le travail de recherche, systématique (exponentielle) ou incomplète. Les méthodes de recherche tentent de minimiser l’espace à explorer afin de découvrir une solution, ou de prouver l’absence de solution à un problème. On utilise pour cela essentiellement des heuristiques, c’est à dire des méthodes capables d’évaluer la pertinence des différentes hypothèses qui seront effectuées au cours d’une recherche. La recherche peut être systématique, lorsque l’on essaie d’explorer totalement les conséquences de l’attribution d’une valeur à une variable. Une autre approche possible serait d’affecter une valeur à chaque variable sans se soucier des contraintes, puis ensuite d’essayer d’améliorer (réparer) la solution jusqu’à ce que toutes les contraintes soient satisfaites. Les réparations sont alors faites sans ordre précis, laissant ainsi un maximum de liberté de choix aux heuristiques, mais en perdant la certitude d’atteindre une solution et d’en prouver l’absence .

Problèmes de satisfaction de contraintes 

Les problèmes de satisfaction de contraintes (Constraint Satisfaction Problems ou CSP) sont au cœur de la programmation par contraintes. Le problème à résoudre est formalisé par un ensemble de variables et un ensemble de contraintes formant un réseau de contraintes (Constraint Network ou CN). L’objectif du problème est de déterminer s’il existe une valeur pour chaque variable telle que toutes les contraintes soient satisfaites. Les variables peuvent être définies sur un domaine continu (⊆ R) ou discret (⊆ Z). Les contraintes peuvent impliquer un nombre arbitraire de variables.

Un CSP est avant tout un problème de décision. La réponse attendue est soit « vrai», si il existe une solution, soit « faux » si aucune solution n’existe. Cependant, en pratique, c’est généralement la découverte d’une solution valable qui est recherchée. Des variantes du problème de base existent, qui sont davantage tournées vers l’optimisation : par exemple, le problème Max-CSP consiste à trouver une solution optimale, qui satisfait le plus de contraintes possible. Une fonction d’optimisation peut également être associée à un CSP simple. L’objectif est alors de trouver une solution valide qui minimise ou maximise le résultat de la fonction d’optimisation.

Test de contrainte : Les algorithmes travaillant sur les CSP sont amenés à tester les contraintes à de nombreuses reprises. Un test de contrainte consiste à vérifier si une instanciation satisfait une contrainte, soit en pratique à calculer le résultat de la fonction d’un des éléments du produit cartésien du domaine des variables impliquées par la contrainte. Il s’agit de l’opération de base de tout algorithme travaillant sur un CSP, qu’il soit complet ou incomplet. On peut noter que le coût en terme d’opérations CPU nécessaires pour tester une contrainte est très variable en fonction de la nature de celle-ci. Les contraintes implicites peuvent représenter des conditions très complexes, nécessitant de nombreux calculs pour déterminer si la contrainte est satisfaite ou non. Les contraintes en extension, représentées sous forme de matrice de booléens, sont généralement considérées comme les contraintes les plus rapides à tester, mais ne sont envisageables que pour des arités faibles. Les algorithmes cherchent généralement à minimiser le nombre de tests de contraintes à effectuer pour résoudre le problème, mais il arrive fréquemment que la diminution du nombre de tests de contraintes entraine une complexification des algorithmes, et par là même de l’apparition de calculs supplémentaires ou de gestion de structures de données au sein des algorithmes [VAN DONGEN 2004].

Coloration de graphes
Le problème de coloration de graphes généralise un grand nombre de problèmes réels de planification et d’ordonnancement. Il consiste à affecter une couleur à chaque nœud d’un graphe sans que deux nœuds voisins soient de la même couleur. On cherche généralement à trouver le nombre de couleurs minimal pour un graphe donné pour que le problème ait une solution. Ce problème remonte à l’origine même de la théorie des graphes. On peut le définir sous forme de CSP tout simplement en reproduisant le graphe à colorer sous forme d’un réseau de contraintes. Toutes les contraintes sont des contraintes de différence .

Le Problème des Pigeons (Pigeon Hole Problem) 

Le problème des pigeons se formule trivialement : comment placer n+ 1 pigeons dans n boîtes, avec au plus un pigeon par boîte ? Ce problème n’a évidemment pas de solution (il est insatisfiable). On peut donc tout à fait le résoudre en temps constant en théorie, mais s’il est naïvement codé sous forme d’un réseau de contraintes binaires (il s’agit alors du problème de coloration de graphes, avec n+1 nœuds et n couleurs, les contraintes formant une clique complète sur tous les nœuds) ou sous forme de clauses SAT , sa résolution devient exponentielle et le problème est alors particulièrement difficile à résoudre.

Certains algorithmes génériques systématiques pour le problème SAT ou CSP implantant une détection des symétries savent cependant résoudre le problème des Pigeons en temps polynomial [BENHAMOU & SAÏS 1994]. Il est également possible de détecter un « cas de pigeons » avec la contrainte all-different : si il reste moins de valeurs possibles que de variables impliquées par la contrainte non instanciées, alors l’instanciation courante de ces variables est insatisfiable. Ces techniques ne semblent malheureusement pas assez performantes à l’heure actuelle pour être appliquées à n’importe quel type de problème dans le cadre d’un prouveur CSP.

Problèmes d’ordonnancement d’atelier 

L’ordonnancement d’atelier consiste à organiser dans le temps le fonctionnement d’un atelier pour utiliser au mieux les ressources humaines et matérielles disponibles dans le but de produire les quantités désirées dans le temps imparti. On s’intéressera ici aux problèmes de type Job Shop et Open Shop. Ce sont des généralisations du problème de planification bien connu du Voyageur de Commerce. Ces problèmes ont été longuement étudiés, notamment en Recherche Opérationnelle, et de nombreuses techniques de résolution heuristiques spécifiques ont été développées. Nous étudierons ici leur formalisation sous forme de CSP et leur résolution via des méthodes génériques.

Un problème d’ordonnancement d’atelier consiste en un ensemble de tâches de durées définies à réaliser en un temps imparti. Ces tâches utilisent un certain nombre de ressources (ou machines) non partageables. L’objectif du problème d’ordonnancement est de trouver une date de début pour chaque tâche de telle sorte que toutes soient exécutées dans le temps imparti et sans que deux tâches utilisent simultanément la même ressource.

Un problème de Job Shop ou Open Shop est défini par un ensemble de m machines et de j travaux découpés en tâches, chaque tâche devant être exécutée sur une machine différente. On donne d’une part la durée de chaque tâche sous forme de matrice à deux dimensions j × m et d’autre part, le numéro de la machine sur laquelle chaque tâche doit être effectuée.