Auteurs : le groupe de projet
Ce qu'est CON'FLEX :
CON'FLEX est un outil de résolution de problèmes de type CSP (Constraint Satisfaction Problems). De façon générale, un problème de satisfaction de contraintes consiste à trouver, parmi les valeurs possibles d'un ensemble de variables, celles qui satisfont un ensemble de contraintes. Des exemples de tels problèmes sont le coloriage de la carte de l'Europe avec seulement n couleurs de telle sorte qu'aucun pays ne soit de la même couleur que ses voisins, la résolution d'un système d'équations, la construction de l'emploi du temps d'un collège. Le formalisme CSP, adopté dans CON'FLEX, permet de résoudre de tels problèmes sans imposer une forme particulière aux contraintes sur les valeurs des variables. Le principe de la résolution repose sur une exploration de l'espace des solutions. Pour chaque point exploré (c'est-à-dire pour une combinaison de valeurs des variables), on teste si toutes les contraintes sont satisfaites. Si c'est le cas, on se trouve en un point-solution. Sinon, on se déplace vers un autre point. Les algorithmes associés au formalisme CSP visent d'une part à réduire l'espace de recherche et d'autre part à le parcourir intelligemment.
CON'FLEX intègre des résultats classiques, publiés dans la littérature CSP depuis une dizaine d'années, et des résultats nouveaux pour lesquels les membres du groupe de projet ont fourni une contribution théorique et un réel champ d'application. Il s'agit de l'extension du formalisme CSP aux problèmes dits flexibles, c'est-à-dire ceux où les variables ont des domaines aux frontières imprécises, où les contraintes sont plus ou moins importantes à satisfaire et, par ailleurs, plus ou moins satisfaites par les différentes combinaisons de valeurs des variables, et enfin où on peut admettre une solution qui ne satisfait que partiellement l'ensemble des contraintes. Ce dernier point permet de poser le problème en terme d'optimisation.
Pour utiliser CON'FLEX, aucune connaissance d'un langage de programmation n'est requise. Il suffit en effet de déclarer l'existence de variables et de contraintes, dans un ordre relativement libre, à partir d'un vocabulaire limité et d'une grammaire simple, spécifiques à CON'FLEX. Ces déclarations constituent le fichier d'entrée du logiciel.
CON'FLEX est un logiciel dont le code source est essentiellement un ensemble de classes C++ (il comprend aussi un module d'interprétation du fichier d'entrée, exploitant les utilitaires lex et yacc). Le code exécutable est produit par le compilateur g++ (une version produite par Sun/CC est aussi disponible). Le logiciel est lancé dans le shell unix simplement par la commande conflex avec le fichier de description du problème comme seul argument requis. Les résultats sont récupérés sur l'écran où dans un fichier de redirection des sorties. Aucune autre fonctionnalité d'interface entre l'utilisateur et le logiciel n'est à ce jour développée, qui fournirait une assistance interactive dans le codage du problème, le paramétrage de la résolution, la représentation graphique du réseau de contraintes, la visualisation des résultats intermédiaires et des solutions, etc...
Bien que fournissant correctement les solutions à de nombreux problèmes-tests, la version actuelle de CON'FLEX est mise à disposition sans garantie. Le groupe de projet souhaite que les utilisateurs lui renvoient des informations sur les problèmes traités et la qualité des résultats obtenus. Des avis sur les fonctionnalités de l'interface utilisateur à développer seront les bienvenus. Une boîte aux lettres est créée à cet effet : conflex@toulouse.inra.fr.
Mots-clés : recherche opérationnelle, intelligence artificielle, problèmes de satisfaction de contraintes, CSP, CSP flexibles, filtrage, recherche arborescente
Implémentation : CON'FLEX est une commande exécutable dans un environnement unix ou windows.
Dernière version : v1.2, Janvier 1998
Pour en savoir plus : Les principales références bibliographiques sont données dans le manuel de l'utilisateur de CON'FLEX. De nombreuses informations de diverses natures sur les CSP peuvent aussi être trouvées à l'adresse suivante : http://www.cs.unh.edu/ccc/archive/.
Pour obtenir CON'FLEX : Les titulaires d'un compte sur le serveur du Laboratoire de Biométrie et Intelligence Artificielle de l'INRA ont directement accès à la commande exécutable (consulter l'administrateur système pour connaître le chemin d'accès approprié). Les autres utilisateurs doivent télécharger le module exécutable et divers documents (manuel de l'utilisateur, exemples) sur leur propre site, selon les modalités et à partir des adresses fournies dans la fiche CON'FLEX Adresses.