To see the other types of publications on this topic, follow the link: Satisfaction de problèmes de contraintes.
Dissertations / Theses on the topic 'Satisfaction de problèmes de contraintes'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Satisfaction de problèmes de contraintes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Bellicha, Félix Amit. "Flexibilité dans les problèmes de satisfaction de contraintes." Montpellier 2, 1996. http://www.theses.fr/1996MON20265.
Full textAbstract:
Nous etudions certains aspects de plusieurs modeles bases sur la satisfaction de contraintes. D'abord, dans le cadre des problemes de satisfaction de contraintes classiques (csp), nous proposons un nouvel algorithme de filtrage des csp binaires (les contraintes portent sur deux variables): il repose sur la mise en evidence de proprietes structurelles reliees aux inclusions de voisinages dans les graphes. Ce filtrage peut diminuer l'ensemble des solutions, mais il preserve la satisfiabilite du probleme. Des formes affaiblies de ce filtrage sont utilisees pour ameliorer des methodes classiques de resolution. Ensuite, nous etudions deux extensions du modele csp classique, qui permettent l'expression de diverses formes de flexibilite: le modele des csp dynamiques (dcsp), ou le facteur temps est introduit, et celui des csp values (vscp), ou des mesures de preferences ou d'incertitude peuvent etre exprimees. Pour ces deux modeles, nous proposons dans le cas binaire des techniques voisines, basees sur une propagation d'informations, dont l'objet est: pour les dcsp, le maintien de solutions successives optimalement proches (differentes mesures de distance etant possibles). Une premiere version statique est completee par une version incrementale. Pour les vcsp, le calcul de solution optimale pour la version statique, et le maintien de solution optimale pour la version incrementale
2
Martinez, David. "Résolution interactive de problèmes de satisfaction de contraintes." Toulouse, ENSAE, 1998. http://www.theses.fr/1998ESAE0005.
Full textAbstract:
Les problèmes de satisfaction de contraintes (CSP) sont une branche de l'intelligence artificielle. Ils offrent un cadre formel, générique et simple pour représenter des problèmes de décision sur des domaines discrets. Sur ce cadre, de nombreuses techniques de recherche de solutions ou d'aide à cette recherche ont été développées : simplification, décomposition, recherche arborescente, recherche locale face à une instance à résoudre, il est difficile pour un utilisateur de choisir sa méthode de résolution et ses heuristiques de choix de variables et de valeurs. Pour éviter d'effectuer un choix, nous proposons une résolution coopérative ou plusieurs méthodes utilisant chacune une heuristique particulière sont exécutées en parallèle et s'échangent des informations pertinentes. D'autre part, les méthodes classiques de recherche locale ou arborescente prennent difficilement en compte les connaissances et les préférences de l'utilisateur, ce qui peut se traduire par une inefficacité de la recherche et une mauvaise qualité des solutions produites. Dans une telle situation, nous proposons deux approches pour une résolution interactive. Dans la première, le rôle essentiel est tenu par le logiciel ; l'utilisateur n'influe que sur la stratégie de recherche utilisée par le logiciel. Dans la seconde, le rôle essentiel est tenu par l'utilisateur, seul habilité à effectuer des choix. Le seul rôle du logiciel est de propager les conséquences de ces choix. Cette propagation s'effectue grâce à un algorithme générique s'appuyant sur une définition générique de niveaux de cohérence locale inverse. Ce schéma regroupe tous les niveaux de cohérence inverse connus et permet la définition de nouveaux niveaux.
3
Hamadi, Youssef. "Traitement des problèmes de satisfaction de contraintes distribués." Montpellier 2, 1999. http://www.theses.fr/1999MON20097.
Full textAbstract:
Dans cette these, nous considerons la resolution efficace de problemes np-complets distribues. Nous presentons pour cela une extension au formalisme csp. Cette extension, dite des problemes distribues de satisfaction de contraintes en domaines finis (dcsp) permet d'etendre le paradigme au traitement des problemes distribues de satisfaction de contraintes. La distribution de l'information qui caracterise les systemes d'information va de pair avec la distribution des problemes, il est donc important d'apporter de nouveaux outils algorithmiques les traitant efficacement. Cette these constitue plus qu'une extension des methodes classiques de resolution csp au nouveau cadre. Nous nous reapproprions les conditions d'optimalite de la resolution en integrant les contraintes inherentes au cadre distribue et notamment les contraintes de localite des informations et de cout des echanges. Ces considerations nous permettent de presenter des methodes de traitement efficaces dans ce nouveau cadre. Nous presentons le premier algorithme distribue de filtrage d'un reseau de contrainte par arc-consistance qui soit a la fois optimal en nombre et en taille des messages echanges. Cette methode de filtrage est completee par la premiere methode de recherche distribuee complete de consommation spatiale non exponentielle. Nous etendons la recherche distribuee de solution pour la rendre entrelacee. Le filtrage distribue par arc-consistance, nous permet de presenter la premiere caracterisation du phenomene de transition de phase dans un cadre distribue. Finalement, nous etendons notre problematique au traitement du probleme sat sur architecture reconfigurable en presentant la premiere adaptation d'une meta-heuristique pour ces architectures.
4
Tounsi, Mohamed. "Contribution à la résolution des problèmes de satisfaction de contraintes discrets." Nantes, 2002. http://www.theses.fr/2002NANT2056.
Full textAbstract:
L'objectif de notre travail consiste en l'amélioration des techniques de résolution de problèmes d'optimisation sous contraintes. Il existe trois approches pour résoudre de tels problèmes : les méthodes complètes, les méthodes de recherche locale et enfin les méthodes hybrides entre ces deux dernières. Bien que ces trois approches aient montré leur efficacité dans plusieurs domaines, de sérieux inconvénients apparaissent lors de la résolution des problèmes d'optimisation. En l'occurence, le temps d'exécution des méthodes complètes est souvent beaucoup trop important pour des instances de grande taille et les méthodes de recherche locale nécessitent un paramétrage précis de différents paramètres utilisés pour réaliser la diversification de la recherche. Par conséquent, nous nous sommes intéressés à la mise au point de nouvelles approches permettant d'augmenter l'efficacité des algorithmes en terme de qualité de solution et de temps d'exécution. . .
5
Lesaint, David. "Calcul d'ensembles de solutions pour problèmes de satisfaction de contraintes." Toulouse, ENSAE, 1995. http://www.theses.fr/1995ESAE0006.
Full textAbstract:
Le formalisme des problèmes de satisfaction de contraintes (CSP) et les méthodes associées offrent un cadre théorique de plus en plus utilisé pour traiter les problèmes d'intelligence artificielle. Toutefois, la plupart des méthodes se concentrent sur le calcul d'une solution ce qui constitue un objectif trop limite. Nous introduisons dans cette thèse la notion de relation complète qui permet de calculer et représenter de facon compacte des ensembles de solutions. Nous proposons d'abord une méthode pour calculer une partition des solutions d'un CSP binaire par relations complètes. Cette méthode met en oeuvre décomposition structurelle et décomposition des contraintes par identification de symétries (calcul d'interchangeabilité). Sa complexité, qui est fonction de la taille d'un transversal minimal du graphe, n'est pas liée au nombre de solutions, à l'inverse des méthodes énumératives. Une évaluation expérimentale sur problèmes jouets en démontre le bon comportement. Nous montrons ensuite que cette méthode relève d'un schéma plus général qui consiste à résoudre le CSP dual d'un CSP pour obtenir une partition de ses solutions. Il est possible de construire un dual binaire pour tout CSP binaire: certaines classes polynomiales s'avèrent alors être stables par passage au dual binaire, assurant ainsi un coût polynomial pour le calcul d'un sous-ensemble des solutions. Nous proposons enfin une extension de l'algorithme backtrack standard pour le calcul de quelques solutions. Expérimentée sur problèmes aléatoires, cette extension entraîne un surcoût modeste par rapport au calcul d'une seule solution bien qu'elle fournisse en meilleur cas un nombre exponentiel de solutions.
6
Madelaine, Florent. "Problèmes de satisfaction de contraintes : une étude logique et combinatoire." Caen, 2003. http://www.theses.fr/2003CAEN2005.
Full textAbstract:
Feder et Vardi ont prouvé que la classe capturée par un fragment monadique de la logique du second ordre existentiel, MMSPN, est calculatoirement équivalente (via des réductions probabilistes) à la classe des problèmes de satisfaction de contraintes (CSP), mais que la seconde est strictement incluse dans la première. Je caractérise exactement cetteinclusion. J'introduis les problèmes de motifs interdits (FP) qui correspondent exactement à MMSNP et développe des outils algébriques originaux comme le recoloriage qui permettent de définir une forme normale et conduisent à une preuve de nature constructive : soit le problème donné est transformé en un problème de CSP, soit des contre-exemples sont construits. Je contraste par ailleurs ce résultat avec un résultat récent, dû à Tardif et Nesetril qui utilise une correspondance entre dualité et densité que je généralise par ailleurs à FP. Finalement, je considère les problèmes de contraintes dans le cas de fonctions unaires.
7
Riff-Rojas, Maria-Cristina. "Résolution de problèmes de satisfaction de contraintes avec des algorithmes évolutionnistes." Phd thesis, Ecole Nationale des Ponts et Chaussées, 1997. http://tel.archives-ouvertes.fr/tel-00523169.
Full textAbstract:
Dans les disciplines de l'intelligence artificielle et de la recherche opérationnelle, on rencontre de nombreux problèmes comme l'allocation de ressources, l'ordonnancement, la, conception, le diagnostic automatisé. Ces problèmes se formulent aisément comme des problèmes de satisfaction de contraintes (CSP). Un CSP est défini comme étant un ensemble de contraintes impliquant un certain nombre de variables. L'objectif consiste simplement à trouver un ensemble de valeurs à affecter aux variables, de sorte que toutes les contraintes soient satisfaites. Dans le cas le plus général, les problèmes de satisfaction de contraintes ont un aspect fortement combinatoire qui leur confère une grande complexité. Nous nous intéressons dans le cadre de cette thèse aux problèmes de satisfaction de contraintes binaires en domaines finis. Les méthodes auxquelles nous nous intéressons pour résoudre un CSP sont, les méthodes dites incomplètes : elles font une réparation d'une configuration en parcourant de manière non systématique l'espace des configurations. Dans cette catégorie de méthodes, notre intérêt s'est plus particulièrement tourné vers les Algorithmes Evolutionnistes. Ce sont des méthodes générales d'optimisation combinatoire qui sont inspirées de la théorie de l'évolution. Dans un CSP classique, on recherche une solution, sans avoir à optimiser de fonction. Pour entrer dans le cadre des Algorithmes Évolutionnistes, on se doit de définir une fonction d'évaluation pour les CSP qui prend ses valeurs minimales sur les solutions du problème. Cette fonction pourrait être utilisée par toutes méthodes incomplètes, telles que les techniques min-conflits, GSAT et leurs variantes. Nous montrons dans cette thèse l'application de notre fonction d'évaluation pour la méthode min-conflits ainsi que pour un algorithme évolutionniste. D'un autre côté, dans le contexte plus spécifique des algorithmes génétiques, nous souhaitons guider l'évolution (i.e. recherche d'une solution), en faisant des transformations sur la population plus orientées vers le problème de satisfaction de contraintes. Nous définissons ainsi des opérateurs de mutation et de croisement spécialisés pour les CSP qui sont basés sur la structure du graphe de contraintes. Ensuite, nous incorporons le concept d'adaptation dans l'opérateur de croisement, afin d'améliorer la recherche de l'algorithme. Dans ce mémoire, nous décrivons et justifions les algorithmes mis en oeuvre, en illustrant les techniques implémentées par la résolution de problèmes de coloriage de graphe avec trois couleurs, et de CSP générés aléatoirement.
8
Vion, Julien. "Contributions à la résolution générique des problèmes de satisfaction de contraintes." Phd thesis, Université d'Artois, 2007. http://tel.archives-ouvertes.fr/tel-00262080.
Full textAbstract:
Nous proposons plusieurs techniques visant à résoudre en pratique le problème NP-complet de satisfaction de contraintes de manière générique. Nous distinguons deux grands axes de techniques de résolution de CSP : l'infrence et la recherche. Nous avons contribué l'amélioration des techniques d'inférence en nous concentrant sur la propriété centrale qu'est la consistance d'arc : optimisations des algorithmes de consistance d'arc, comportement de plusieurs algorithmes d'inférence aux bornes de domaines discrets, et enfin une alternative intéressante à la consistance de chemin : la consistance duale. Cette propriété nous a amené à concevoir des algorithmes de consistance de chemin forte très efficaces. La variante conservative de cette consistance est de plus plus forte que la consistance de chemin conservative, tout en restant plus rapide à établir en pratique.Par ailleurs, nous avons également cherché à améliorer MGAC, tout d'abord en équipant celui-ci d'heuristiques de choix de valeurs. Nous nous sommes pour cela basés sur l'heuristique de Jeroslow-Wang, issue du problème SAT. En utilisant deux techniques de conversion de CSP vers SAT, nous montrons comment cette heuristique se comporterait sur un CSP. Enfin, nous avons cherché à utiliser une hybridation entre un algorithme de recherche locale basé sur la pondération des contraintes et un algorithme MGAC équipé de l'heuristique dom/wdeg, en exploitant les possibilités d'apprentissage de l'un et l'autre algorithmes.
De manière transversale, l'ensemble des techniques développées dans le cadre de cette thèse a amené à la réalisation d'une API pour le langage Java, capable de résoudre un CSP au sein d'une application Java quelconque. Cette API a été développée dans l'optique "boîte noire" : le moins de paramètres et d'expertise possibles sont demandés à l'utilisateur. Un prouveur basé sur CSP4J a concouru lors les compétitions internationales de prouveurs CSP avec des résultats encourageants.
9
Fargier, Hélène. "Problèmes de satisfaction de contraintes flexibles. Application à l'ordonnancement de production." Toulouse 3, 1994. http://www.theses.fr/1994TOU30099.
Full textAbstract:
L'approche csp (constraint satisfaction problems) proposee par l'intelligence artificielle offre un cadre de representation general et rigoureux, permettant de formuler simplement de nombreux types de problemes combinatoires, et une palette de techniques de resolution de ces problemes. En particulier, on peut etablir que la modelisation de problemes de raisonnement temporel symbolique avec les algebres d'instants ou d'intervalles est formellement une approche de type csp et que les graphes non-conjonctifs utilises pour la resolution de problemes d'ordonnancement sont des csp. Une comparaison entre regles d'analyse sous contraintes et methodes de filtrage des csp permet non seulement d'interpreter les premieres en termes de consistance locale, mais aussi de decouvrir de nouvelles regles. Cependant, le cadre formel fourni par les csp est encore trop restrictif: en particulier, il interdit la prise en compte des caracteristiques flexibles ou incertaines de certains problemes ou une formulation sous forme de contraintes parait interessante. C'est pourquoi nous avons defini un nouveau formalisme qui generalise l'approche csp, tant au niveau theorique qu'algorithmique. Etant fonde sur la theorie des ensembles flous et la theorie des possibilites, le modele fcsp (fuzzy contraint satisfaction problems) autorise le traitement de contraintes souples ou a priorite, de contraintes incertaines ainsi que la prise en compte de parametres non-controlables. Ce modele a ensuite ete specialise aux problemes d'ordonnancement de production de type job-shop. Il permet de representer des dates de disponibilite, d'echeance et des durees d'operations flexibles ou imprecises. Les regles classiques d'analyse sous contraintes, les procedures de propagation de date et de construction incrementale d'ordonnancement ont facilement ete etendues a ce nouveau formalisme. Les outils de resolution issus de ce travail ont ete experimentes: il apparait que la prise en compte de la flexibilite d'un probleme de job-shop n'augmente pas le temps moyen de resolution, et peut dans certains cas le diminuer
10
Butaru, Mihaela. "Problèmes de satisfaction de contraintes n-aires : résolution séquentielle et parallèle." Metz, 2005. http://www.theses.fr/2005METZA001.
Full textAbstract:
Les problèmes de satisfaction de contraintes (CSP) constituent un cadre de formalisation puissant des problèmes d'Intelligence Artificielle. De nombreuses méthodes ont été définies pour les résoudre. Les travaux présentés dans cette thèse s'intéressent aux méthodes complètes, i. E. Qui permettent toujours de trouver une solution. Les plus performantes méthodes complètes de résolution de CSP utilisent un mécanisme de recherche de type forward-checking. Afin d'améliorer l'efficacité des algorithmes de résolution, de diverses techniques de filtrage ont été proposées, appliquées avant et / ou pendant la recherche. Cependant, les contraintes n-aires ont été peu étudiées. Nous proposons un solveur non-binaire composé d'une famille d'algorithmes résolution de type Forward Checking n-aire (nFC) et une famille d'algorithmes d'arc-consistance n-aire (nAC) qui comporte plusieurs versions. Comme la résolution séquentielle des CSP n-aires peut s'avérer coûteuse (probèmes NP-complets), le parallélisme permet de réduire le temps de calcul. Pour cela, nous exploitons essentiellement une méthode de parallélisation en mémoire partagée, basée sur la division de l'arbre de recherche en utilisant OpenMP. Nous appliquons et spécialisons les algorithmes proposés pour la résolution de problèmes académiques et de problèmes aléatoires non-binaires, ainsi que pour la résolution du problème du car-sequencing dans une formulation de CSP n-aire.
11
Ghédira, Khaled. "Masc : une approche multi-agents des problèmes de satisfaction de contraintes." Toulouse, ENSAE, 1993. http://www.theses.fr/1993ESAE0027.
Full textAbstract:
L'approche multi-agent, domaine de l'intelligence artificielle distribuée, ouvre une nouvelle voie pour appréhender de façon naturelle les problèmes de satisfaction de contraintes (Constraint Satisfaction Problems, CSP) souvent abordes par des systèmes centralises et des modèles d'exécution séquentiels. Cette approche a d'abord été utilisée dans le cadre de problèmes d'allocation de ressources (voir annexes). Sous le nom de MASC (approche Multi-Agent des problèmes de Satisfaction de Contraintes), elle a ensuite été étendue au cadre général CSP. MASC est une méthode par déplacements au sein de l'espace d'état, guides par des réparations locales stochastiques. Celles-ci sont basées sur un outil d'optimisation, le recuit simulé, dont l'objectif est d'atteindre un état optimal qui satisfasse le maximum de contraintes. Des résultats théoriques sont établis et discutes. Le problème de l'implémentation sur une architecture parallèle est également soulève et une solution est apportée. Outre cet aspect statique, MASC traite l'aspect dynamique des CSPs par l'intégration d'un mécanisme de réactivations. Ce mécanisme, tout en gardant l'objectif d'optimalité, vise à retrouver une solution proche de la solution de départ. Aussi bien pour l'aspect statique que pour l'aspect dynamique, des résultats expérimentaux sont exhibes et discutes
12
Johannsen, Schnoor Ilka. "La méthode des bases faibles pour les problèmes de satisfaction de contraintes." Aix-Marseille 2, 2007. http://www.theses.fr/2007AIX22109.
Full textAbstract:
Les problèmes de satisfaction de contraintes constituent une classe de problèmes importante en théorie de la compléxité. La compléxité algorithmique des problèmes de satisfaction de contrainte booléennes fut étudiée en premier lieu par Schaefer en 1978. Des outils algébriques, qui font intervenir une correspondance de Galois fournissent une méthode pour obtenir des classifications en compléxité de problèmes algorithmiques liés à la satisfaction de contraintes. Cependant, pour un certain nombre d'objectifs algorithmiques, ces outils ne s'appliquent pas. Nous développons une méthode qui met en jeu une correspondance de Galois plus sophistiquée et permet d'obtenir des classifications de la compléxité pour une grande diversité de tels problèmes. Nous démontrons l'efficacité de notre méthode en étudiant deux types de problèmes de contraintes booléennes issus de contextes très différents. Dans un premier temps nous considérons le problème de satisfaisabilité équilibrée, il s'agit là de satisfaire toutes les contraintes données en entrée (qui sont des contraintes locales) en vérifiant de plus une contrainte globale de cardinalité. Dans un second temps nous nous tournons vers les logiques non monotones et étudions la compléxité du raisonnement en logique des défauts restreinte aux formules composées de contraintes. Finalement nous étudions le problème de l'énumération des solutions d'une conjonction de contraintes définies sur des domaines finis arbitraires. Nous exhibons des classes de problèmes pour lesquels nous développons de nouveaux algorithmes d'énumération efficacesConstraint satisfaction problems are an important class of problems in complexity theory. The computational complexity of all boolean constraint satisfaction problems was completely classified by Schaefer in 1978 using algebraic tools involving a Galois correspondance. However, for many problems related to constraint satisfaction these tools cannot be applied. We develop a method that allows to use a refined Galois correspondence to obtain complexity classifications for those problems. We demonstrate our new method by completely classifying two constraint problems from different contexts: first we consider the balanced satisfiability problem, where we require the solutions to satisfy a global condition additionally to the local constraints given in the constraint instance. Then we turn to nonmonotonic logics and study the complexity of reasoning in default logic restricted to constraint formulas. Finally we study the problem of enumerating all solutions of given constraint instances over arbitrary finite domains and present a template for new efficient enumeration algorithms
13
Prcovic, Nicolas. "Recherche arborescente parallèle et séquentielle pour les problèmes de satisfaction de contraintes." Marne-la-vallée, ENPC, 1998. http://www.theses.fr/1998ENPC9812.
Full textAbstract:
Cette thèse traite de la recherche arborescente parallèle pour résoudre les problèmes de satisfaction de contraintes (CSP), notamment des changements qu'elle produit naturellement sur l'ordre de visite des noeuds de l'arbre de recherche par rapport à sa version séquentielle. Dans les cas où ces changements s'avèrent préjudiciables en terme de temps de résolution, on donne des moyens de rétablir, au moins partiellement, l'ordre originel de visite des feuilles. Lorsque ces changements sont profitables, on propose de les appliquer directement à la recherche séquentielle. Après avoir rapidement rappelé quelques notions utiles sur les CSP (chapitre 1) et le parallélisme (chapitre 2), nous présentons un algorithme parallèle destiné à trouver toutes les solutions d'un CSP (chapitre 3). Puis la recherche d'une seule solution ou de la meilleure est abordée en étudiant notamment les conditions qui font qu'une recherche parallèle puisse conduire à une accélération superlinéaire ou sublinéaire (chapitre 4). Enfin nous traitons de la transformation des algorithmes d'optimisation séquentiels en algorithmes parallèles de facon plus générale, en l'illustrant par l'intégration du parallélisme dans une bibliothèque générique de classes C++ destinées à la modélisation et la résolution de problèmes d'optimisation. Dans la deuxième partie, nous exploitons le phénomène d'accélération superlinéaire pour traiter des possibles améliorations de parcours d'arbre par rapport au Backtrack chronologique. Nous présentons un algorithme séquentiel récent basé sur le phénomène de superlinéarité étudié dans le chapitre 4 ainsi que d'autres méthodes de recherche arborescente apparues ces dernières années. Leur point commun est de parcourir les noeuds de l'arbre de recherche dans un ordre différent de celui de la recherche classique en profondeur d'abord. Toutes ces méthodes sont comparées entre elles suivant la pertinence de l'ordre de visite des feuilles de l'arbre qu'elles suivent (chapitre 6). Finalement, nous proposons toute une série d'algorithmes qui sont des variations des algorithmes présentés dans le chapitre précédent. Ils exploitent les caractéristiques des CSP pour améliorer encore l'ordre de visite des feuilles ou diminuer le nombre de noeuds générés.
14
Amilhastre, Jerome. "Représentation par automate d'ensemble de solutions de problèmes de satisfaction de contraintes." Montpellier 2, 1999. http://www.theses.fr/1999MON20027.
Full textAbstract:
L'utilisation des problemes de satisfaction de contraintes (csp) dans certaines applications a mis en evidence la necessite d'etendre aussi bien le formalisme que le champ des questions traitees. Le calcul et la representation de l'ensemble des solutions est une reponse possible a ces nouveaux besoins. Nous proposons une representation par automates d'etats finis (fa) non deterministes qui generalise la representation par fa deterministes due a vempaty. Nous nous interessons a la minimisation des fa non deterministes, probleme qui reste np-difficile sur la classe des langages associes aux ensembles de solutions de csp : langages finis composes de mots de meme longueur. Nous etudions le probleme de recouvrement minimum par bicliques de graphes bipartis qui est equivalent au probleme de minimisation de fa reconnaissant uniquement des mots de longueur 2. Nous proposons une nouvelle classe polynomiale pour ce probleme et exhibons une propriete combinatoire qui pourrait impliquer la polynomialite des differentes classes polynomiale connues. En utilisant le lien existant entre minimisation de fa et recouvrement de bipartis, nous proposons un processus general de minimisation de fa qui repose sur le calcul d'une serie de recouvrements de graphes bipartis issus du fa. Les proprietes generales de ce processus sont etudiees et trois heuristiques differentes sont proposees. Les experimentations effectuees montrent un gain significatif par rapport a un codage par mdfa. L'influence de l'ordre choisi sur les variables sur la taille du mdfa representant un csp est etudiee : nous proposons une borne sur la taille du plus petit mdfa representant un csp ainsi qu'une etude experimentale d'heuristiques d'ordonnancement des variables. Nous proposons des algorithmes specifiques a nos automates pour la realisation des differentes etapes necessaires a la construction d'un petit fa reconnaissant l'ensemble des solutions d'un csp.
15
Castro, Carlos. "Une approche déductive de la résolution de problèmes de satisfaction de contraintes." Nancy 1, 1998. http://docnum.univ-lorraine.fr/public/SCD_T_1998_0236_CASTRO.pdf.
Full textAbstract:
Dans cette thèse, nous modélisons la résolution de problèmes de satisfaction de contraintes (csps) comme un processus de déduction. Nous formalisons les techniques de résolution de csps sur des domaines finis en utilisant des règles de réécriture et des stratégies. Les règles expriment les transformations réalisées par ces techniques sur les contraintes et les stratégies contrôlent l'application de ces règles. Cette approche nous permet de vérifier facilement des propriétés telles que la correction, la complétude et la terminaison d'un solveur. L'utilisation d'un langage de stratégies puissant nous permet de décrire les heuristiques d'une manière très abstraite et flexible. En utilisant cette approche déductive, nous pouvons prouver l'existence ou l'inexistence d'une solution : il nous suffit de regarder le terme de preuve pour reconstruire exactement une preuve du calcul réalisé. Afin de valider notre approche, nous avons implanté le système colette dans le langage elan. Nous étudions tout d'abord le problème de la résolution d'un ensemble de contraintes élémentaires qui sont combinées par des operateurs de conjonction. Nous nous intéressons ensuite à la résolution de problèmes d'optimisation en utilisant des techniques de résolution de csps. Nous abordons l'extension du langage de contraintes afin de considérer la combinaison des contraintes élémentaires avec les connecteurs logiques de disjonction, d'implication et d'équivalence. Le traitement des contraintes disjonctives est décrit en détail. Finalement, nous étudions la coopération de solveurs. En utilisant les operateurs de stratégies concurrents du langage elan, nous décrivons d'une manière abstraite des schémas de coopération séquentiels et concurrents. Pour d'autres types de coopération, nous utilisons des primitives de bas niveau qui sont disponibles dans elan pour la communication entre processus.
16
David, Philippe. "Prise en compte de la sémantique dans les problèmes de satisfaction de contraintes : étude des contraintes fonctionnelles." Montpellier 2, 1994. http://www.theses.fr/1994MON20038.
Full textAbstract:
Diverses techniques ont ete developpees pour resoudre les problemes de satisfaction de contraintes, mais peu d'entre elles prenaient en compte la semantique des contraintes. L'objet de cette these est de tirer profit des proprietes semantiques des contraintes fonctionnelles pour accroitre l'efficacite de resolution des csp en contenant. Nous etudions tout d'abord les proprietes d'un csp fonctionnel verifiant les consistances d'arc et de chemin, les deux consistances partielles les plus utilisees ; nous exposons alors des conditions sous lesquelles une instanciation peut se prolonger en une solution sans retour arriere, puis presentons une methode reduisant la complexite de resolution. Nous introduisons ensuite une nouvelle consistance partielle, la consistance de pivot, de moindre cout que la consistance de chemin, et montrons que les resultats precedemment obtenus gardent leur validite. Nous etendons enfin cette consistance suivant deux axes: csp n-aires et csp dynamiques
17
Berger, Nicolas. "Modélisation et résolution en programmation par contraintes de problèmes mixtes continu/discret de satisfaction de contraintes et d'optimisation." Phd thesis, Université de Nantes, 2010. http://tel.archives-ouvertes.fr/tel-00560963.
Full textAbstract:
Les contraintes sont un moyen générique de représenter les règles qui gouvernent notre monde. Étant donné un ensemble de contraintes, une question centrale est de savoir s'il existe une possibilité de toutes les satisfaire simultanément. Cette problématique est au cœur de la programmation par contraintes, un paradigme puissant pour résoudre efficacement des problèmes qui apparaissent dans de nombreux domaines de l'activité humaine. Initialement dédiée, dans les années 1980, à la résolution de problèmes d'intelligence artificielle à variables entières, c'est dans les années 1990 que la programmation par contraintes a été employée à la résolution de problèmes à variables réelles. Cependant, les problèmes mixtes —utilisant à la fois variables entières et réelles— n'ont été que très peu considérés jusqu'ici par la programmation par contraintes. Dans cette thèse, nous nous plaçons du point de vue de la résolution de problèmes continus. Nous proposons et mettons en oeuvre différentes améliorations de ce cadre de résolution : • Intégration de la notion de recherche rigoureuse d'optimum au cadre classique de résolution sans objectif, afin de modéliser et résoudre un problème de conception en robotique ; • Collaboration de deux solveurs, l'un discret l'autre continu, plus efficace que chacun des outils pour résoudre les problèmes utilisant contraintes continues et contraintes discrètes ; • Comparaison des différentes modélisations et filtrages possibles de la contrainte globale discrète alldifferent, permettant de l'utiliser dans un solveur dédié au continu ; • Spécialisation des techniques de filtrage basées sur l'arithmétique des intervalles, augmentant la puissance de filtrage des contraintes arithmétiques discrètes et mixtes.
18
Madeline, Blaise. "Algorithmes évolutionnaires et résolution de problèmes de satisfaction de contraintes en domaines finis." Phd thesis, Université de Nice Sophia-Antipolis, 2002. http://tel.archives-ouvertes.fr/tel-00505450.
Full textAbstract:
Cette thèse traite de l'utilisation des algorithmes évolutionnaires (AE) pour résoudre des problèmes de satisfaction de contrainte (CSP) en domaines finis sans spécialisation ni hybridation particulière. Après avoir présenté les CSP et les méthodes couramment utilisées pour les résoudre (chapitres 1 et 2), nous présentons le paradigme évolutionnaire et ses applications (chapitres 3 et 4). Ensuite, nous proposons une comparaison entre les méthodes de recherche arborescente et les métaheuristiques sur des coloriages de graphe sur-contraints, dans un contexte de réglage des paramètres minimal (chapitre 5). Nous étudions le paysage de recherche pour comprendre les raisons des différences d'efficacité des méthodes. Enfin, nous proposons de nouveaux opérateurs génétiques (croisement, mutation, diversification) dont le paramétrage est moins fastidieux qu'avec les opérateurs classiques (chapitre 6). Nous concluons sur l'intérêt d'exploration des réseaux de neutralité.
19
Hadjadj, Aoul Lamia. "Sur des généralisations des graphes triangulés : application aux problèmes de satisfaction de contraintes." Aix-Marseille 1, 2003. http://www.theses.fr/2003AIX11025.
Full textAbstract:
Le cadre de cette thèse est de caractériser certaines classes de graphes ayant de bonnes propriétés pour la résolution de systèmes de contraintes. En effet, nous étudions ici les propriétés et algorithmes de certaines classes de graphes qui se trouvent être des généralisations des graphes triangulés. En particulier, nous étudions dans le détail les graphes CSGk, qui définissent une hiérarchie de classes de graphes dont le second niveau, les graphes CSG1 sont exactement les graphes triangulés. Dans cette étude, nous essayons de voir si les résultats classiques des graphes triangulés peuvent ou non être généralisés, en particulier aux graphes CSG2. Nous étudierons notamment le théorème de Dirac ainsi que la définition par sous-graphes exclus. Dans la dernière partie, nous étudions les aspects algorithmiques relatifs aux graphes CSG2 pour trois questions. Tout d'abord leur reconnaissance, puis le calcul des cliques maximales, et enfin, l'opération qui consiste à ajouter des arêtes dans un graphe quelconque afin de construire un graphe CSG2 ; nous nommerons cette opération "2-triangulation". Il s'agit là d'outils algorithmiques qui trouvent leur justification notamment pour la généralisation de la méthode de décomposition de domaines par triangulation. La dernière contribution de cette thèse repose sur deux généralisations de classes polynomiales du problème de la clique : les graphes faiblement triangulés et les graphes de comparabilité. Ces généralisations sont construites sur le même principe que celui des graphes CSGk, à savoir une définition en termes de hiérarchie de classes de graphes. Aussi les différentes preuves s'appuient-elles sur le même type de schéma que pour les graphes CSG2, et les résultats que nous obtenons sont très similaires à ceux produits avec les graphes CSG2 en rapport principalement avec le problème de la clique.
20
Terrioux, Cyril. "Approches structurelles et coopératives pour la résolution des problèmes de satisfaction de contraintes." Aix-Marseille 1, 2002. http://www.theses.fr/2002AIX11051.
Full textAbstract:
Cette thèse porte sur des méthodes de résolution du problème de satisfaction de contraintes (CSP) qui exploitent des informations explicitées durant la recherche. D'abord, nous définissons la méthode énumérative BTD qui produit et exploite des goods et nogoods structurels. Un good (resp. Nogood) structurel est une affectation consistante qui peut (resp. Ne peut pas) être étendue de façon consistante sur une partie bien définie du problème. BTD bénéficie de l'efficacité pratique de l'énumération tout en garantissant des bornes de complexité identiques à celles des meilleures méthodes structurelles. BTD est ensuite étendu au cadre des CSP valués. Ensuite, nous étudions l'apport de la coopération à une méthode concurrente, la coopération reposant sur l'échange de nogoods classiques (i. E. Des affections consistantes qui ne peuvent être étendues en une solution). Cette approche obtenant de bons résultats en pratique, nous l'étendons aux goods et nogoods structurels, puis aux CSP valués.
21
Gouachi, Idir. "Liresne : Un système de Résolution de problèmes de satisfaction de contraintes en nombres entiers." Paris 13, 1998. http://www.theses.fr/1998PA132023.
Full textAbstract:
Dans cette these nous proposons un systeme de resolution de problemes de satisfaction de contraintes en nombres entiers. Ce systeme nomme liresne (langage pour interpreter et resoudre des systemes en nombres entiers) est compose de solveurs bases sur des algorithmes hybrides combinant les outils de l'intelligence artificielle (techniques de consistance, retour arriere intelligent) et de la recherche operationnelle (optimisation, recherche tabou, relaxation lagrangienne). Notre systeme est particulierement constitue : d'un interpreteur qui offre un langage declaratif pour enoncer les problemes et les traduit en une structure interne ; d'un solveur principal destine aux problemes de satisfaction de contraintes en nombres entiers non specifiques ; d'un solveur dedie aux problemes d'ordonnancement, auquel nous avons injecte des outils specifiques a ces problemes et dont l'algorithme de construction de l'arbre de recherche suit une nouvelle demarche ; et d'un solveur pour le probleme de satisfiabilite (sat) et (sat incremental) dont les performances, sur les instances traitees, sont meilleures que celles de la methode classique de davis-putnam-loveland et de sa version incrementale.
22
Merchez, Sylvain. "Problèmes de satisfaction de contraintes : étude de mécanismes d'abstraction et de construction de hiérarchies." Artois, 2000. http://www.theses.fr/2000ARTO0405.
Full textAbstract:
De nombreux problèmes issus de l'intelligence artificielle et de la recherche opérationnelle peuvent s'exprimer naturellement sous forme de contraintes. Cette thèse est une étude de deux aspects importants concernant les problèmes de satisfaction de contraintes (ou CSP pour constraint satisfaction problem). Dans une première partie, nous nous sommes intérssés à la définition d'un cadre formel permettant de construire des abstractions de CSPS. Notre principal objectif a été de rendre aussi générale que possible notre proposition. Cela se traduit par la possibilité d'intégrer aussi bien les formes classiques d'abstraction de csps (introduites dans la littérature), que des formes originales identifiées dans cette thèse. Ces dernières correspondent à la notion de regroupement dit général de valeurs et de variables. L'origine de la généralité du cadre est liée à l'utilisation de relations d'approximation comme liens d'abstraction. Afin de prouver expérimentalement l'intérêt des formes originales d'abstraction, nous avons développé le prototype abscon. Dans une seconde partie, nous nous sommes intéressés à la modélisation de csps prenant en compte des préférences (ou priorités). Nous proposons à cet effet un modèle de hiérarchie flexible qui permet d'évaluer et de classer l'ensemble des instanciations possibles (ou solutions potentielles). Nous calculons une évaluation globale qui intègre pour chaque niveau de la hiérarchie un degré de satisfaction et un degré de tolérance. Le degré de tolérance d'un niveau permet de prendre plus ou moins en compte les niveaux suivants de la hiérarchie. Le modèle que nous proposons est directement construit à partir de l'expression des contraintes, ce qui le rend naturellement déclaratif. Nous illustrons notre approche à l'aide d'une application réelle: la détermination du profil de réseaux d'assainissement.
23
Lagniez, Jean-Marie. "Satisfiabilité propositionnelle et raisonnement par contraintes : modèles et algorithmes." Thesis, Artois, 2011. http://www.theses.fr/2011ARTO0404/document.
Full textAbstract:
La thèse porte sur la résolution des problèmes de satisfiabilité propositionnelle (SAT) et des problèmesde satisfaction de contraintes (CSP). Ces deux modèles déclaratifs sont largement utilisés pour résoudredes problèmes combinatoires de première importance comme la vérification formelle de matérielset de logiciels, la bioinformatique, la cryptographie, la planification et l’ordonnancement de tâches.Plusieurs contributions sont apportées dans cette thèse. Elles vont de la proposition de schémas d’hybridationdes méthodes complètes et incomplètes, répondant ainsi à un challenge ouvert depuis 1998, àla résolution parallèle sur architecture multi-coeurs, en passant par l’amélioration des stratégies de résolution.Cette dernière contribution a été primée à la dernière conférence internationale du domaine (prixdu meilleur papier). Ce travail de thèse a donné lieu à plusieurs outils (open sources) de résolution desproblèmes SAT et CSP, compétitifs au niveau internationalThis thesis deals with propositional satisfiability (SAT) and constraint satisfaction problems(CSP). These two declarative models are widely used for solving several combinatorial problems (e.g.formal verification of hardware and software, bioinformatics, cryptography, planning, scheduling, etc.).The first contribution of this thesis concerns the proposition of hybridization schemes of complete andincomplete methods, giving rise to an original answer to a well-known challenge open since 1998. Secondly,a new and efficient multi-core parallel approach is proposed. In the third contribution, a novelapproach for improving clause learning management database is designed. This contribution allows spatialcomplexity reduction of the resolution-based component of SAT solvers while maintaining relevantconstraints. This contribution was awarded at the last international SAT conference (best paper award).This work has led to several open sources solving tools for both propositional satisfiability and constraintssatisfaction problems
24
Cervoni, Laurent. "Méthodologies et techniques de résolution de problèmes avec contraintes. Application en programmation logique avec objets : cooxi." Rouen, 1994. http://www.theses.fr/1994ROUES032.
Full textAbstract:
Cette thèse se présente tout d'abord comme une étude exploratoire des techniques, des méthodes et des systèmes de résolution de problèmes avec contraintes, basée sur un retour d'expérience industriel. Devant l'émergence, ces dernières années, de nouvelles techniques ou outils pour résoudre les problèmes fortement combinatoires, ce document se propose de restituer plus précisément le contexte de la résolution de ces problèmes complexes en : passant en revue les approches disponibles, collectant le maximum de techniques, les comparant ; précisant les liens entre recherche opérationnelle et programmation par contraintes. Une méthodologie répondant de manière efficace à ces problèmes complexes (dits avec contraintes) est alors suggérée. Enfin, la dernière partie étudie les perspectives de quelques techniques au travers d'une structure d'accueil en programmation logique
25
Karoui, Wafa. "Méthodes à divergences pour la résolution de problèmes de satisfaction de contraintes et d'optimisation combinatoire." Thesis, Toulouse, INSA, 2010. http://www.theses.fr/2010ISAT0021/document.
Full textAbstract:
Le formalisme « Problème de Satisfaction de Contraintes » (ou CSP pour Constraint Satisfaction Problem) peut être considéré comme un langage de représentation formelle qui couvre l'ensemble des problèmes dont la modélisation fait intervenir des contraintes. L'intérêt de ce formalisme réside dans l'exploitation de la généricité d'algorithmes de résolution puissants mais également dans la performance d'algorithmes dédiés à des problèmes particuliers.Dans ce travail de thèse, nous étudions la résolution de CSP par des méthodes de recherche arborescente basées sur la notion de « divergence » (une divergence est relative à la contradiction d’une décision proposée par une heuristique de référence). Dans ce cadre, nous proposons de nouveaux mécanismes d'amélioration des méthodes de recherche générales qui exploitent les échecs rencontrés pendant la résolution, en adoptant des heuristiques de pondération des variables et des valeurs. Nous proposons également d'autres techniques spécifiques aux méthodes à base de divergences qui conditionnent l’exploration de l’arbre de recherche développé, notamment la restriction des divergences, les différents modes de comptage ainsi que le positionnement des divergences. Ces propositions sont validées par des expérimentations numériques menées sur des problèmes de satisfaction de contraintes réels et aléatoires. Des comparaisons sont effectuées entre variantes de méthodes à divergences intégrant différentes combinaisons des améliorations et d’autres méthodes connues pour leur performance.Dans une seconde partie, nous étendons nos propositions à un contexte d'optimisation en considérant la résolution de problèmes d'ordonnancement avec contraintes de délais (time lags). Nous traitons l'adaptation d'une méthode de « recherche par montée de divergences » (Climbing Discrepancy Search) pour la résolution de ces problèmes. Nous validons les performances de certaines variantes de cette méthode intégrant les mécanismes proposés dans ce travail sur des problèmes-test de la littératureThe CSP (Constraint Satisfaction Problem) formalism can be considered as a simple example of a formal representation language covering all problems including constraints. The advantage of this formalism consists in the fact that it allows powerful general-purpose algorithms as much as useful specific algorithms.In this PhD thesis, we study several tree search methods for solving CSPs and focus on ones based on the discrepancy concept (a discrepancy is a deviation from the first choice of the heuristic). In this context, we propose improving mechanisms for general methods. These mechanisms take benefits from conflicts and guide the search by weighting the variables and the values. We propose also special mechanisms for methods based on discrepancies as the discrepancies restriction, the discrepancies counting, and the discrepancies positions. All propositions are validated by experiments done on real and random CSPs. We compare variants of methods based on discrepancies integrating several combinations of improvements and other methods known for their efficiency.In a second part, we extend our propositions to an optimisation context considering scheduling problems with time lags. In this purpose, we adapt a discrepancy-based method, Climbing Discrepancy Search, to solve these problems. Efficiency of some improved variants of this method is tested on known benchmarks
26
Karaoui, Wafa. "Méthodes à divergences pour la résolution de problèmes de satisfaction de contraintes et d'optimisation combinatoire." Phd thesis, INSA de Toulouse, 2010. http://tel.archives-ouvertes.fr/tel-00538672.
Full textAbstract:
Le formalisme " Problème de Satisfaction de Contraintes " (ou CSP pour Constraint Satisfaction Problem) peut être considéré comme un langage de représentation formelle qui couvre l'ensemble des problèmes dont la modélisation fait intervenir des contraintes. L'intérêt de ce formalisme réside dans l'exploitation de la généricité d'algorithmes de résolution puissants mais également dans la performance d'algorithmes dédiés à des problèmes particuliers. Dans ce travail de thèse, nous étudions la résolution de CSP par des méthodes de recherche arborescente basées sur la notion de " divergence ". Dans ce cadre, nous proposons de nouveaux mécanismes d'amélioration des méthodes de recherche générales qui exploitent les échecs rencontrés pendant la résolution, en adoptant des heuristiques de pondération des variables et des valeurs. Nous proposons également d'autres techniques spécifiques aux méthodes à base de divergences qui conditionnent l'exploration de l'arbre de recherche développé, notamment la restriction des divergences, les différents modes de comptage ainsi que le positionnement des divergences. Ces propositions sont validées par des expérimentations numériques menées sur des problèmes de satisfaction de contraintes aléatoires (tirés de contextes réels) ainsi que des problèmes d'optimisation. Des comparaisons sont effectuées entre variantes de méthodes à divergences intégrant différentes combinaisons parmi les améliorations étudiées et d'autres méthodes connues pour leur performance.
27
Jégou, Philippe. "Contribution à l'étude des problèmes de satisfaction de contraintes : algorithmes de propagation et de résolution : propagation de contraintes dans les réseaux dynamiques." Montpellier 2, 1991. http://www.theses.fr/1991MON20015.
Full textAbstract:
Nous presentons une etude sur la resolution de problemes de satisfaction de contraintes (au sens csp). Si la litterature concernant les csp binaires (contraintes limitees a deux variables) est particulierement fournie, celle relative au cas general (contraintes d'arite quelconque) est assez limitee. Aussi, apres un rappel exhaustif sur les techniques de propagation et de satisfaction de contraintes, nous proposons des resultats theoriques et pratiques relatifs a la problematique generale. Ces resultats concernent notamment la representation de csp n-aires par des csp binaires, les techniques de filtrage par propagation de contraintes et les methodes de resolution de problemes par decomposition. Dans une seconde partie, nous etudions un formalisme issu des csp: les csp dynamiques. Ce modele impose la gestion d'ensembles de contraintes evolutifs dans un cadre de resolution. Si les techniques classiques sont applicables dans certains cas, les particularites du modele imposent le developpement de methodes specifiques adaptees a son aspect dynamique. Nous proposons ainsi une methode de maintien de consistance partielle dans un reseau de contraintes dont l'objectif concerne egalement le calcul d'informations supplementaires permettant l'explication des causes de propagations
28
Mérel, Pierre-Paul. "Les problèmes de satisfaction de contraintes : recherche n-aire et parallélisme : application au placement en CAO." Metz, 1998. http://docnum.univ-lorraine.fr/public/UPV-M/Theses/1998/Merel.Pierre_Paul.SMZ9806.pdf.
Full textAbstract:
Les problèmes de satisfaction de contraintes (CSP) constituent un cadre de formalisation puissant des problèmes d'intelligence artificielle. Un CSP est la donnée d'un ensemble de variables définies sur certains domaines, et d'un ensemble de contraintes reliant ces variables. De nombreuses méthodes ont été définies pour les résoudre. Nous nous intéressons dans ce document, aux méthodes complètes, i. E. Qui permettent toujours de trouver une solution. Les méthodes complètes de résolution les plus performantes pour les csp utilisent un mécanisme de recherche par vérification de consistance "en avant", c-à-d. En filtrant les valeurs incompatibles dans les domaines non instancies lorsqu'une nouvelle instanciation est testée (forward-checking). Cependant, ces méthodes ne sont définies que pour des contraintes binaires. Nous étendons ces méthodes en définissant une notion de consistance n-aire généralisée : la relationnelle-(I,J)-consistance. Nos expérimentation montrent que la résolution n-aire directe est plus rapide que la résolution sur un CSP binaire obtenu apres transformation. Comme la recherche séquentielle est particulièrement couteuse (NP-complete), le parallélisme permet de réduire le temps de calcul. Pour cela, nous definissons un algorithme générique qui permet d'hybrider aussi bien les différentes techniques de recherche séquentielles que les méthodes de parallélisation. Le principe de la recherche reprend le schéma " OU-parallèle". Si la plupart des techniques parallèles classiques restent utilisables pour les CSP, nous définissons différentes techniques destinées à mieux s'adapter aux spécificités des CSP. Ainsi, nous proposons une méthode de répartition initiale de charge, une méthode de division adaptée à la taille des contextes de recherche et une fonction de détermination de la divisibilité d'une tâche. Nous appliquons et spécialisons les algorithmes définis pour la résolution de problèmes de bordereau de coupe en confection, i. E. Le placement de formes quelconques sur une surface restreinteConstraint satisfaction problems (CSP) are a powerfull framework in formalization of artificial intelligence problems. A CSP is given by a set of variables defined on specific domains, and a set of constraints on these variables. Many technics had been defined to solve them. We are interested in this document, in complete methods, i. E. Enabling to find a solution in every case. The most powefull complete solving methods for CSP use a search mecanism with forward checking consistency, i. E. In filtering incompatible values in not yet instantiated domains when a new instantiation is tested. However, these methods are defined only for binary constraints. We extend them in defining a generalized notion of n-ary consistency : relationnal-(I,J)-consistency. Our experimentations show direct n-ary search is faster than search on binary CSP sfter transformation. As sequential search is rather costly (NP-complete), parallelism enables to reduce computation time. To achieve this, we define a generic algorithm allowing to mix different sequential search and parallelization methods. Global principle of resolution is based on “OR-parallel” search. If most of classical parallel technics are usable for CSP, we define different technics to follow CSP specificities. Thus, we propose a load sharing method, a splitting technics adapted for the size of search contexts and a function to evaluate the divisibility of a task. We apply and specialize our algorithms in solving the problem of cutting plan, i. E. Position asignement for random pieces on a restricted area
29
Trojet, Mariem. "Planification d'une chaîne logistique : approche par satisfaction de contraintes dynamiques." Phd thesis, INSA de Toulouse, 2014. http://tel.archives-ouvertes.fr/tel-00996957.
Full textAbstract:
Le sujet de thèse porte sur la planification tactique et opérationnelle d'une chaîne logistique dans un contexte dynamique. Nous proposons un modèle de planification basé sur une structure décisionnelle à deux niveaux. Adoptant un processus dynamique permettant d'actualiser les données à chaque étape de planification, le premier niveau planifie la production en recherchant le meilleur compromis entre les leviers décisionnels disponibles liés aux aspects capacité et coût de production. Le deuxième niveau établit un ordonnancement agrégé des opérations de fabrication en minimisant les en-cours. Le recours à une structure décisionnelle intégrée nous a conduit à établir une interaction entre les niveaux supérieur et inférieur de décision, mise en oeuvre par des contraintes dites de conservation d'énergie. Notre approche est modélisée sous la forme d'un problème de satisfaction de contraintes (CSP, Constraint Satisfaction Problem) et évaluée par simulation dans un contexte de données incertaines. Nous avons mené différentes expérimentations portant sur la variation de la demande, la variation de la capacité et la re-planification de la demande. Toutes les expérimentations sont réalisées par deux méthodes de résolution différentes : une méthode basée sur un CSP statique et une méthode basée sur un CSP dynamique. La performance d'une solution de planification/ordonnancement est renseignée par l'ensemble des mesures de la stabilité et de la robustesse. Les expérimentations réalisées offrent une démonstration de la performance de la méthode de résolution basée sur un CSP dynamique par rapport à la méthode statique.
30
Rochon, du Verdier Franck. "Résolution de problèmes d'aménagement spatial fondée sur la satisfaction de contraintes : validation sur l'implantation d'équipements électroniques hyperfréquences." Lyon 1, 1992. http://www.theses.fr/1992LYO10141.
Full textAbstract:
Face aux multiples applications industrielles, en electronique, mecanique, architecture, urbanisme, l'automatisation du processus d'amenagement spatial suscite un interet considerable. Dans cette these, nous abordons les problemes de placement dans le plan d'objets de forme quelconque lies par des relations locales et de nature diverses. Nous proposons d'associer des techniques de satisfaction de contraintes a une modelisation des espaces de configurations permettant de representer les positions et orientations candidates des objets a placer. En outre, notre approche prend en compte les aspects evolutif, conflictuel et combinatoire du probleme: des algorithmes de consistance dynamique autorisent la resolution des problemes dont les specifications sont mises a jour au cours du processus de resolution par ajout et/ou retrait de contraintes; une methode generique de traitement d'echecs effectue des substitutions des contraintes conflictuelles en minimisant une mesure de frustration: une technique de resolution a precision variable permet une recherche plus efficace en faisant varier la precision geometrique de la solution. Ces principes sont mis en uvre dans le systeme atlas, experimente sur une application de conception d'equipements electroniques hyperfrequences
31
Richoux, Florian. "Toward a complexity classification of CSP through kernel widthVers une caractérisation de la complexité des CSP à travers la largeur des kernels." Palaiseau, Ecole polytechnique, 2009. http://pastel.paristech.org/5564/01/memoire_submitted.pdf.
Full textAbstract:
Constraint Satisfaction Problems (CSP) constitute a universal formalism allowing to modelize a huge number of algorithmical and combinatorial problems, such as problems over graphs, databases, artificial intelligence, …This thesis is in line with the study of the computational complexity of CSP. It is a very active research domain for which there exists dedicated sessions in some highest conferences in algorithmic, logic and artificial intelligennce such as IJCAI and AAAI. The starting point of this thesis was to study some restrictions of CSP and to fully characterize the computational complexity of these sub-problems. This goal has been reached with the complete characterization of monotone CSP over finite domains of an arbitrary cardinality and over infinite countable domains. These results lead to two international and one national publications. This thesis also describes a complete characterization of homogeneous co-Boolean CSP and gives a first approach of a complete characterization for general co-Boolean CSP. Most of all, this thesis develops a new method based on the kernel width which seems to be very promissing to characterize the computational complexity of the general CSP problem, and starts to give some firsts innovating results on the complexity.
32
Daoudi, Abderrazak. "Acquisition de contraintes par apprentissage de structures." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT316/document.
Full textAbstract:
La Programmation par contraintes est un cadre général utilisé pour modéliser et résoudre des problèmes combinatoires complexes. Cependant, la modélisation d'un problème sous forme d’un réseau de contraintes nécessite une bonne expertise dans le domaine. Ce niveau d'expertise est un obstacle majeur pour une large diffusion de la programmation de contraintes. Pour remédier à ce problème, plusieurs systèmes d'acquisition de contraintes ont été proposés pour aider l'utilisateur dans la tâche de modélisation. Dans ces systèmes, l'utilisateur ne répond qu'à des questions très simples. L'inconvénient est que lorsqu'aucune connaissance de base n’est fournie, l'utilisateur peut avoir besoin de répondre à un grand nombre de questions pour apprendre toutes les contraintes. Dans cette thèse, nous montrons que l'utilisation de la structure du problème peut améliorer considérablement le processus d'acquisition. Pour ce faire, nous proposons plusieurs techniques. Tout d'abord, nous introduisons le concept de requête de généralisation basée sur une agrégation de variables sous forme detypes. Deuxièmement, pour faire face aux requêtes de généralisation, nous proposons un algorithme de généralisation de contraintes, nommé GENACQ, ainsi que plusieurs stratégies. Troisièmement, pour rendre la construction de requêtes de généralisation totalement indépendante de l'utilisateur, nous proposons l'algorithme MINE&ASK, qui est en mesure d'apprendre la structure au cours du processus d'acquisition de contraintes, et d'utiliser la structure apprise pour générer des requêtes de généralisation. Quatrièmement, pour aller vers un concept générique de requête, nous introduisons la requête de recommandation basée sur la prédiction de liens dans le graphe de contraintes apprises jusqu’à présent. Cinquièmement, nous proposons un algorithme de recommandation de contraintes, ppelé PREDICT&ASK, qui demande à l’utilisateur de classifier des requêtes de recommandation chaque fois que la structure du graphe courant a été modifiée. Enfin, nous intégrons toutes ces nouvelles techniques dans l’algorithme QUACQ, menant à trois nouvelles versions, à savoir G-QUACQ, M- QUACQ, et P-QUACQ. Pour évaluer toutes ces techniques, nous avons fait des expérimentations sur plusieurs jeux de données. Les résultats montrent que les versions étendues améliorent considérablement le QUACQ de baseConstraint Programming is a general framework used to model and solve complex combinatorial problems.However, modeling a problem as a constraint network requires significant expertise in the field.Such level of expertise is a bottleneck to the broader uptake of the constraint technology.To alleviate this issue, several constraint acquisition systems have been proposed to assist thenon-expert user in the modeling task. Nevertheless, in these systems the user is only asked to answervery basic questions. The drawback is that when no background knowledge is provided,the user may need to answer a large number of such questions to learn all the constraints.In this thesis, we show that using the structure of the problem under consideration may improvethe acquisition process a lot. To this aim, we propose several techniques.Firstly, we introduce the concept of generalization query based on an aggregation of variables into types.Secondly, to deal with generalization queries, we propose a constraint generalization algorithm, named GENACQ, together with several strategies. Thirdly, to make the build of generalization queries totally independent of the user, we propose the algorithm MINE&ASK, which is able to learn the structure, during the constraint acquisition process, and to use the learned structure to generate generalization queries. Fourthly, toward a generic concept of query, we introduce the recommendation query based on the link prediction on the current constraint graph. Fifthly, we propose a constraint recommender algorithm, called PREDICT&ASK, that asks recommendation queries, each time the structure of the current graph has been modified. Finally, we incorporate all these new generic techniques into QUACQ algorithm leading to three boosted versions, G-QUACQ, M- QUACQ, and P-QUACQ. To evaluate all these techniques, we have made experiments on several benchmarks. The results show that the extended versions improve drastically the basic QUACQ
33
Arsouze, Julien. "Une formalisation de la résolution des problèmes de satisfaction de contraintes : application à la vision grammaticale de CLP." Orléans, 2004. http://www.theses.fr/2004ORLE2073.
Full textAbstract:
Résoudre un Problème de Satisfaction de Contraintes (CSP) consiste à trouver une affectation pour chaque variable du problème parmi un ensemble de valeurs appartenant à un domaine qui satisfasse toutes les contraintes. Pour cela, les solveurs utilisent des méthodes de propagation de contraintes issues des notions de consistance locale. Les itérations chaotiques d'opérateurs corrects, monotones et contractants modélisent la sémantique opérationnelle de ces solveurs. Nous présentons ici les -itérations chaotiques qui permettent d'obtenir une abstraction plus fine des algorithmes de résolution. Pour obtenir une affectation satisfaisant toutes les contraintes, il est nécessaire d'utiliser également des algorithmes de recherche qui sont aussi pris en compte dans notre formalisme. Nous proposons d'utiliser ce dernier en considérant la construction des squelettes d'arbres de preuves de la Programmation Logique avec Contraintes (CLP) comme la résolution d'un CSP particulier.
34
Dago, Pierre. "Extension d'algorithmes dans le cadre des problèmes de satisfaction de contraintes valués : application à l'ordonnancement de systèmes satellitaires." Toulouse, ENSAE, 1997. http://www.theses.fr/1997ESAE0006.
Full textAbstract:
Dans cette étude, nous nous intéressons à la résolution des "Problèmes de Satisfaction de Contraintes valués" (CSP valués). Cette modélisation extrèmement simple, intuitive et riche s'adapte facilement à une grande variété de problèmes d'optimisation. De nombreux travaux ont par ailleurs fourni toute une bibliothèque d'algorithmes de résolution. Dans le cadre classique de la satisfaction des CSP, l'efficacité de ces méthodes n'est plus à démontrer et leur domaine d'application est assez bien connu. L'introduction d'une valuation des contraintes dans le modèle CSP, qui donne naissance aux CSP valués, est cependant trop récente pour que les possibilités et les limites d'efficacité soient clairement identifiées. L'ordonnancement des satellites d'observation de la Terre fait partie des CSP valués à la frontière des compétences actuelles en matière d'optimisation. Cette application est pour nous un prétexte au développement d'outils de résolution nouveaux étendant le champ des CSP valués accessibles. Notre travail est centré sur la notion de "contrainte induite", largement utilisée dans le cadre classique, et dont l'extension difficile aux CSP valués limite actuellement l'amélioration des algorithmes de recherche complets. Afin de dépasser ces difficultés, directement liées à la non-idempotence de l'agrégation des valuations des contraintes, nous proposons un formalisme minimal pour les contraintes induites. Nous montrons ensuite comment il peut être mis en oeuvre pour étendre l'essentiel des algotithmes développés dans le cadre classqiue. Enfin, l'utilité de ces nouveaux outils est illustré sur les problèmes d'ordonnancement du satellite SPOT 5.
35
Lobjois, Lionel. "Problèmes d'optimisation combinatoire sous contraintes : vers la conception automatique de méthodes de résolution adaptées à chaque instance." Toulouse, ENSAE, 1999. http://www.theses.fr/1999ESAE0025.
Full textAbstract:
Nous étudions dans cette thèse deux voies pour résoudre plus efficacement les problèmes d'optimisation combinatoire exprimés dans le cadre génétique VCSP (Valued Constraint Satisfaction Problem), extension du cadre CSP (Constraint Satisfaction Problem) pour l'optimisation. La première voie concerne la recherche de nouvelles méthodes globalement plus performantes par la coopération entre méthodes complètes et méthodes incomplètes. Nous proposons en particulier une nouvelle méthode hybride dédiée à la résolution de VCSP en contexte interruptible et la comparons aux recherches locales standards. La seconde voie concerne la recherche d'outil d'aide à la décison permettant d'utiliser une méthode adaptée à chaque situation, c'est-à-dire adaptée à l'instance à résoudre et au temps imparti à la résolution de cette instance. Nous proposons tout d'abord une adaptation de la méthode proposée par Knuth en 1975 afin d'estimer le temps de résolution des méthodes complètes de type séparation et évaluation. Nous envisageons ensuite une série d'application potentielles pour cet estimateur. Nous proposons notamment la méthode SPP (algorithm Selection by Performance Prediction) capable de sélectionner, instance par instance, l'algorithme le plus performant parmi une base d'algorithmes complets. Nous terminons ce mémoire par quelques voies permettant d'étendre cette méthode à une construction automatique d'algorithmes complets "optimisés" pour chaque instance.
36
Kueviakoe, Kangni. "Localisation multi-capteurs garantie : résolution d'un problème de satisfaction de contraintes." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112241/document.
Full textAbstract:
Cette thèse traite de la localisation de véhicule. Plusieurs méthodes sont utilisées pour résoudre ce type de problème. Elles peuvent être classées en deux grandes catégories d’approches : les approches probabilistes et les approches déterministes.Ce travail aborde les approches déterministes et plus précisément l'approche ensembliste basée sur l'analyse par intervalles. Les travaux ont été conduits sur des jeux de données réelles collectées en environnements d'extérieur comprenant des capteurs proprioceptifs et extéroceptifs.Lorsque l'on met en jeu plusieurs capteurs fournissant des informations complémentaires ou redondantes, il est important de fusionner les données afin d'améliorer la pose estimée. L'approche détaillée dans ce document utilise les méthodes intervalles et présente le problème de la localisation sous la forme d'un problème de satisfaction de contraintes.La résolution se fait à l'aide d’un solveur à intervalles. Plusieurs algorithmes ont été comparés. Un constat s'est dégagé : les algorithmes de consistance locale ne corrigent pas l'incertitude sur l’orientation. Cette thèse propose une méthode de localisation utilisable dans des applications temps réel et qui corrige l'incertitude sur le cap du véhicule. Nous avons comparé nos résultats à ceux du filtre de Kalman étendu (méthode probabiliste de référence) et mis en avant un des intérêts de notre méthode : l'assurance d'une consistance de la pose (position et orientation du mobile).Cette thèse propose deux contributions. La première est d'ordre méthodologique. Dans l'état de l'art tous les travaux affirment la nécessité (voire l'obligation) d'une décomposition préalable des contraintes du problème avant l'étape de résolution. Nos travaux permettent de prouver le contraire. La deuxième contribution concerne la réduction du domaine de l'incertitude en orientation en couplant la propagation de contraintes et une approche de bissectionThis thesis deals with the vehicle locationand addresses the problem of SLAM (simultaneous localization and mapping). Several methods are used to solve this kind of problem. They can be classified into two broad categories of approaches: probabilistic approach and deterministic approaches. This work addresses the deterministic approaches and more precisely the approach based on interval analysis. The work has been conducted on real data sets collected in outdoor environments with proprioceptive and exteroceptive sensors.When multiple sensors providing complementary or redundant information are put into play, it is important to merge the data to improve the estimated pose. The approach detailed in this document uses the intervals methods and presents the localization problem as a constraint satisfaction problem.The resolution is done using a solver interval. Several solvers were compared. One thing is clear: local consistency algorithms do not address the uncertainty of the orientation. This thesis proposes a method of locating usable in real time applications and corrects the uncertainty in the heading of the vehicle. We compared our results with those of the extended Kalman filter (probabilistic reference method) and highlighted one of the interests of our method: the assurance of consistency of the pose (position and orientation of the mobile).This thesis proposes two contributions. The first is methodological. In the state of the art all works affirm the need (or obligation) to pre-decompose the constraints of the problem before the resolution step. Our work allows to prove otherwise. The second contribution relates to the reduction of the orientation uncertainty by combining constraint propagation and a bisection approach
37
Naanaa, Wady. "Résolution de problèmes de satisfaction de contraintes intégrant la flexibilité et la symétrie : application à la génération de structures moléculaires." Lyon 1, 1996. http://www.theses.fr/1996LYO10320.
Full textAbstract:
Dans ce memoire, nous introduisons une procedure systematique pour la resolution de problemes de satisfaction de contraintes binaires (csps). Cette procedure integre deux strategies de recherche. Nous proposons des extensions au formalisme csp standard. Ces extensions permettent la relaxation des csps surcontraints et la resolution de csps ayant une structure ambigue. Nous proposons egalement une methode, pour le traitement de la symetrie inherente aux csps. Cette methode s'appuie sur les automorphismes de graphe simple. Nous validons les methodes et procedures proposees sur le probleme de l'identification des structures moleculaires qui est un probleme central en chimie analytique.
38
Vautard, Jérémie. "Modélisation et résolution de problèmes de décision et d'optimisation hiérarchiques en utilisant des contraintes quantifiées." Phd thesis, Université d'Orléans, 2010. http://tel.archives-ouvertes.fr/tel-00486721.
Full textAbstract:
Cette thèse s'inscrit dans le cadre de la programmation par contraintes quantifiées, un formalisme étendantla programmation par contraintes classique en ajoutant aux variables des quantificateurs existentiels ouuniversels, ce qui apporte en théorie une expressivité suffisante pour modéliser des problèmes avec adversaireou incertitude sur certains paramètres sous forme de problèmes appelés QCSP (Quantified Constraintsatisfaction Problem).Nous commençons par apporter une réponse aux difficultés de modélisation de problèmes réels dont estfrappée la programmation par contraintes quantifiées en introduisant une extension aux QCSP permettantd'expliciter les actions possibles de l'agent principal et de son adversaire. Puis, nous décrivons différentproblèmes grâce à ce formalisme, et discutons de la place de cette extension parmi les formalismes voisins créésen réponse à cette même difficulté de modélisation. Enfin, nous nous intéressons à la notion d'optimisationdans le cas des contraintes quantifiées, et apportons un formalisme d'optimisation de contraintes quantifiéespermettant d'exprimer des problèmes multi-niveaux non linéaires.
39
Budzynski, Louise. "Algorithmic barriers in random constraint satisfaction problems." Thesis, Université Paris sciences et lettres, 2020. http://www.theses.fr/2020UPSLE013.
Full textAbstract:
La complexité typique des Problèmes de Satisfaction de Contraintes (CSP) peut être étudiée à l'aide d'ensembles aléatoires de contraintes. On observe un phénomène de seuil quand la densité de contraintes augmente. En particulier à la transition de clustering, l'ensemble des solutions typiques se fracture en groupes de solutions séparés les uns des autres. Dans cette thèse nous introduisons un biais qui brise l'uniformité entre les solutions d'une instance de CSP, et nous étudions son effet sur la valeur du seuil de clustering. Nous étudions en particulier le problème de bicoloriage de k-hypergraphes. Pour de petites valeurs de k, nous montrons que ce biais peut augmenter la valeur du seuil clustering, et que cela a un effet positif sur les performances de l'algorithme de Simulated Annealing pour la recherche de solutions d'une instance du problème de bicoloriage. Dans la limite où k tend vers l'infini, nous calculons le développement asymptotique du seuil de clustering pour la mesure uniforme et pour une mesure biaisée. Nous évaluons le gain obtenu avec cette implémentation du biaisThe typical complexity of Constraint Satisfaction Problems (CSP) can be studied using random ensembles of instances. One observes threshold phenomena when the density of constraints increases, in particular a clustering phase transition at which typical solutions shatter into disconnected components. In this PhD, we introduce a bias that breaks the uniformity among solutions of a given instance of CSP, and look at the evolution of the clustering threshold under this bias, focusing on the bicoloring of k-uniform random hypergraphs. For small values of k, we show that this bias can delay the clustering transition to higher densities of constraints, and that it has a positive impact on the performances of Simulated Annealing algorithm to find a solution for a given instance of the bicoloring problem. In the large k limit, we compute the asymptotic expansion of the clustering threshold for the uniform and the biased measure, and characterize the gain obtained with our implementation of the bias
40
Escamocher, Guillaume. "Forbidden patterns in constraint satisfaction problems." Toulouse 3, 2014. http://thesesups.ups-tlse.fr/2283/.
Full textAbstract:
Le problème de satisfaction de contraintes (CSP) est NP-complet, même dans le cas où toutes les contraintes sont binaires. Cependant, certaines classes d'instances CSP sont traitables. Récemment, une nouvelle méthode pour définir de telles classes aémergée. Cette approche est centrée autour des motifs interdits, ou l'absence locale de certaines conditions. Elle est l'objet de ma thèse. Nous définissons formellement ce que sont les motifs interdits, présentons les propriétés qu'ils détiennent, et finalement les utilisons afin d'établir plusieurs résultats de complexité importants. En utilisant différentes versions de motifs, toutes basées sur le même concept de base, nous énumérons un nombre important de nouvelles classes traitables, ainsi que certaines NP-completes. Nous combinons ces résultats pour révéler plusieurs dichotomies, chacune englobant une large gamme de classes d'instances CSP. Nous montrons aussi que les motifs interdits représentent un outil intéressant pour la simplification d'instances CSPs. Nous donnons plusieurs nouveaux moyens de réduire la taille des instances CSP, que ce soit en éliminant des variables ou en fusionnant les domaines, et montrons comment ces méthodes sont activées par l'absence locale de certains modèles. Comme les conditions de leurutilisation sont entièrement locales, nos opérations peuvent être utilisés sur un large éventail de problèmesThe Constraint Satisfaction Problem (CSP) is NP-Complete, even in the case where all constraints are binary. However, some classes of CSP instances are tractable. Recently, a new method for defining such classes has emerged. This approach is centered around forbidden patterns, or the local absence of some conditions. It is the focus of my thesis. We formally define what forbidden patterns are, exhibit the properties they hold, and eventually put them to use in order to establish several important tractability results. Using different versions of patterns, all based on the same core concept, we list a significant number of new tractable classes, as well as some NP-Complete ones. We combine these results to reveal several dichotomies, each one encompassing a large range of classes of CSP instances. We also show how useful a tool forbidden patterns can be in the field of CSP instance simplification. We give multiple new ways of decreasing the size of CSP instances, whether by eliminating variables or fusioning domains, and prove how all these methods are enabled by the local absence of some patterns. Since the conditions for their use are entirely local, our operations can be used on a wide array of problems
41
Bennaceur, Hachemi. "Le Problème de satisfaction de contraintes : synthèse et méthode exacte de résolution." Paris 13, 1989. http://www.theses.fr/1989PA132025.
Full textAbstract:
Le problème de satisfaction de contraintes consiste à exhiber une ou plusieurs solutions d'un système diophantien ou à démontrer la vacuité du domaine associé. La synthèse des differentes implications de ce problème dans le domaine de l'informatique (intelligence artificielle, vectorisation de programmes, vérification de codes, équations sur les mots. . . ) a permis de mettre en évidence les différents modèles typiques de ces applications. L'analyse des techniques de résolution utilisées jusqu'à présent dans le domaine de la vectorisation de programmes a démontré tout l'intérêt de concevoir une nouvelle méthode permettant de trouver efficacement une solution quelque soit l'instance traitée. Cette méthode efficace et robuste appelée fas3t repond aux deux objectifs : preuve de la vacuité du domaine ou de l'existence d'une solution. Les applications à la vectorisation automatique de programmes et au fameux problème de satisfaction d'une expression logique demontrent la rapidité de la méthode fas3t
42
Verdret, Philippe. "L'expertise en conception de programme : Approche à partir de la notion de satisfaction de contraintes." Rouen, 1989. http://www.theses.fr/1989ROUEL082.
Full textAbstract:
Pour caractériser l'expertise en conception de programme quatre programmeurs expérimentés, dont un expert, ont été observés lors de la conception d'un script Shell (programme construit à base des commandes UNIX). La conception de script a été analysée comme un processus de gestion de contraintes. Ce processus consiste à identifier et à satisfaire des contraintes. Diverses stratégies de gestion des contraintes sont mises en évidence et analysées: le relâchement, l'isolement, la hiérarchisation et l'intégration dans des structures des diverses contraintes de la conception. Le processus de conception d'un script se décompose en trois phases: la compréhension du problème proposé, la planification d'une solution et la mise en œuvre de cette solution. Cette décomposition est d'autant plus nette que le programmeur est plus expert. L'étude de la planification permet de mettre en évidence deux modalités d'élaboration d'une solution. L'expert dispose de structures de connaissance qui intègrent d'emblée de nombreuses contraintes. Pour l'élaboration de leur solution les autres programmeurs procèdent par intégration des contraintes qui sont progressivement identifiées. Dans la mise en œuvre l'expert utilise des techniques qui lui permettent d'isoler les contraintes et d'éviter ainsi les interactions. La construction du script se fait à partir d'unités de construction qui constituent des gabarits de scripts qui sont au travers de phases d’édition exécution progressivement ajustes au contexte d'utilisation. Les prolongements théoriques et pratiques sont brièvement évoquésTo characterize expertise in Shell program design, one expert and three experienced programmers were observed while designing a "script", i. E. A program written with the UNIX Shell command language. Script design was analyzed as a constraint-management process. The process consists of identifying design constraints. Constraints are especially criteria to be satisfied by the design produc (i. E. The script). Various constraint-management strategies were identified. They are: relaxing, isolating, hierarchizing, and integrating constraint structures. The shell design process revealed three successive steps: understanding the problem, planning the solution, and implementing the solution. This breaking down is all the more apparent since the programmer is expert. The study of planning brought to light two modalities of solution elaborating. While experienced programmers integrate constraints identified progressively, expert programmer integrates a lot of constraints straightaway thanks to language-related knowledge structures representing procedure abstractions. The study of implementation showed that the expert uses a set of techniques which allows him to isolate constraints and to avoid interactions conquently. Expert script design is made from design units which constitute script templates. Templates satisfy more constraints than the only constraints of script operationality which were rather considered by experienced programmers. The templates are progressively fitted to context of use through editing executing phrases. In conclusion, theoretical and practical implications of the study are briefly considered
43
Lamontagne, Éric. "Le problème de décision CSP : Homomorphismes et espace logarithmique." Thesis, Université Laval, 2012. http://www.theses.ulaval.ca/2012/29292/29292.pdf.
Full text
44
Saad, Belaïd. "Intégration des problèmes de satisfaction de contraintes distribués et sécurisés dans les systèmes d'aide à la décision à base de connaissances." Thesis, Metz, 2010. http://www.theses.fr/2010METZ012S/document.
Full textAbstract:
Une large gamme de problèmes pratiques nécessite une diversité de représentation et de modélisation des données et de développer des modèles dans lesquels les différentes données peuvent être représentées. Dans cette thèse, nous nous intéressons à l'hybridation de deux modèles : le modèle des Systèmes Experts (SE) et le modèle des Problèmes de Satisfaction de Contraintes (CSP). L'objectif de notre travail est de proposer un système distribué et sécurisé pour intégrer des contraintes dans un moteur d'inférence. Pour ce faire, nous avons d'une part développé un outil de communication qui facilite la collaboration entre SE et CSP. D'autre part, nous avons conçu un algorithme qui permet la communication entre plusieurs agents situés dans un environnement distribué. Enfin, un de nos buts, et non des moindres, est d'assurer la protection des données privées de chaque entité. La thèse est donc constituée de trois axes principaux : Le premier axe vise l'élaboration d'une méthode de communication entre les deux modèles. Tout d'abord, nous décrivons une procédure de transformation automatique entre un système expert à base de règles vers un nouveau modèle de CSP dynamique nommé DDCSP (Dynamic Domain CSP) que nous avons au préalable défini. Cette procédure de transformation automatique permettra l'injection des résultats de l'un des deux modèles en entrée de l'autre. Cette procédure joue donc un rôle essentiel pour assurer la collaboration qui s'appuie sur l'échange d'informations. Le deuxième axe est consacré à la prise en compte de la distribution d'un problème CSP sur plusieurs sites. Nous proposons un algorithme basé sur la notion de coopération et de parallélisme qui assure une résolution distribuée entre plusieurs agents. Notre approche consiste à construire un anneau d'agents autonomes, responsable chacun d'une partie des variables et des contraintes du problème. Chacun de ces agents va initier un processus qui explore une branche différente de l'arbre de recherche. Des heuristiques sont proposées pour garantir une diversification des explorations, en d'autres termes pour éviter que les branches explorées ne se recouvrent. Enfin, nous présentons une technique de sécurisation de cet algorithme dans l'environnement distribué basée sur l'utilisation judicieuse des propriétés de cryptographie asymétrique pour préserver la confidentialité des instanciations. Afin d'effectuer une validation expérimentale de nos travaux, une implémentation dans les langages de programmation C/C++ ou Java est décrite dans chacun de ces trois axesA wide range of practical problems requires diversity of data representation and to develop models in which different data can be represented. In this thesis, we focus on the hybridization of two models: Expert System (ES) and Constraint Satisfaction Problem (CSP).The aim of our work is to propose a secure distributed system that allows integrating constraints in an inference engine.To reach this goal, on one hand we developed a communication tool that facilitates collaboration between ES and CSP. On the other hand, we designed an algorithm that allows communication between multiple entities in a distributed environment. Finally, one of our goals, not the least, is to protect private data of each entity. The thesis is composed of three main axes.The first priority is to develop a method of communication between the two models. First, we describe an automatic transformation procedure of the rule based expert system into the new dynamic CSP model called DDCSP (Dynamic Domain CSP) that we have designed. This procedure will automatically transform and inject the result of one of the two models as input to the other one. This process plays an essential role for collaboration based on the exchange of information.Our second axe proposes an algorithm based on the concept of cooperation and parallelism which provides a resolution distributed among several entities. Our approach is to build a ring of autonomous agents, each responsible for some of the variables and constraints of the problem. Each of these agents will initiate a process that explores a different branch of the search tree. Heuristics are proposed to ensure a diversification of exploration, in other words to prevent overlapping of the explored branches.Finally, we present a technique for securing this distributed algorithm based on a judicious use of the properties of asymmetric encryption to protect the confidentiality of instantiations. To perform an experimental validation of our work, an implementation in the programming languages C/C++ or Java is described in each of these three axes
45
Paris, Nicolas. "Intégration de techniques CSP pour la résolution du problème WCSP." Thesis, Artois, 2014. http://www.theses.fr/2014ARTO0405/document.
Full textAbstract:
Cette thèse se situe dans le contexte de la programmation par contraintes (CP). Plus précisément, nous nous sommes intéressés au problème de satisfaction de contraintes pondérées (WCSP). De nombreuses approches ont été proposées pour traiter ce problème d’optimisation. Les méthodes les plus efficaces utilisent des cohérences locales souples sophistiquées comme par exemple la cohérence d’arc directionnelle complète FDAC∗, la cohérence d’arc directionnelle existentielle EDAC∗, etc. Établies grâce à des opérations de transferts de coût préservant l’équivalence des réseaux, l’utilisation de ces cohérences permet généralement d’accélérer la résolution en réduisant l’espace de recherche via la suppression de valeurs et le calcul de bornes inférieures utiles en pratique. Cependant, l’utilisation de ces méthodes pose un problème lorsque l’arité des contraintes augmente de manière significative. L’efficacité des techniques du cadre du problème de satisfaction de contraintes (CSP) étant avérée, nous pensons que l’intégration de techniques CSP peut être très utile à la résolution d’instances WCSP. Dans cette thèse, nous proposons tout d’abord un algorithme de filtrage établissant la cohérence d’arc souple généralisée GAC∗ sur des contraintes tables souples de grande arité. Cette approche combine la technique de réduction tabulaire simple (STR), issue du cadre CSP, et le principe de transfert de coûts. Notre approche qui est polynomiale calcule efficacement pour chaque valeur les coûts minimaux dans les tuples explicites et implicites des contraintes tables souples. Ces coûts minimaux sont ensuite utilisés pour transférer les coûts afin d’établir GAC∗. Dans un second temps, nous proposons une approche alternative aux méthodes de résolution habituelles du problème WCSP. Elle consiste à résoudre une instance WCSP en résolvant une séquence d’instances CSP classiques obtenues depuis cette instance WCSP. À partir d’une instance CSP dans laquelle toutes les contraintes de l’instanceWCSP d’origine sont durcies au maximum, les instances CSP suivantes correspondent à un relâchement progressif de contraintes de l’instance WCSP déterminées par l’extraction de noyaux insatisfaisables minimaux (MUC) depuis les réseaux insatisfaisables de la séquence. Nos résultats expérimentaux montrent que notre première approche est compétitive avec l’état de l’art, tandis que la deuxième représente une approche alternative aux méthodes de résolutionhabituelles d’instances WCSPThis thesis is in the context of constraint programming (CP). Specifically, we are interested in the Weighted Constraint Satisfaction Problem (WCSP). Many approaches have been proposed to handle this optimization problem. The most effective methods use sophisticated soft local consistencies such as, for example, full directional arc consistency FDAC∗, existential directional arc consistency EDAC∗, etc. Established by equivalence preserving transformations (cost transfer operations), the use of these consistencies generally allows both to accelerate the resolution by reducing the search space through the elimination of values and to compute lower bounds useful in practice. However, these methods reach theirlimits when the arity of constraints increases significantly. The techniques of the Constraint Satisfaction Problem framework (CSP) having proved efficienty, we believe that the integration of CSP techniques can be very useful for solving WCSP instances. In this thesis, we first propose a filtering algorithm to enforce a soft version of generalized arc consistency (GAC∗) on soft table constraints of large arity. This approach combines the techniques of simple tabular reduction (STR), from the CSP framework, with the techniques of cost transfer. Our approach, proved polynomial, efficiently calculates for each value the minimum cost of the explicit and implicit tuples from soft table constraints. The minimum costs are thenused to transfer costs to establish GAC∗. In a second step, we propose an alternative approach to the usual techniques to solve WCSP. The principle is to solve a WCSP instance by solving a sequence of classical CSP instances obtained from this WCSP instance. From a CSP instance containing all the constraints hardened to the maximum from the WCSP instance, the next CSP instances correspond to a progressive relaxation of constraints defined by extraction of minimal unsatisfiable cores (MUC) from unsatisfiable networks of the sequence. Our experimental results show that our first approach is competitive with the state-of-the-art, whereas the second one represents an alternative approach to the usual methods to solve WCSP instances
46
Gharbi, Nebras. "On compressing and parallelizing constraint satisfaction problems." Thesis, Artois, 2015. http://www.theses.fr/2015ARTO0406/document.
Full textAbstract:
La programmation par contraintes est un cadre puissant utilisé pour modéliser et résoudre des problèmes combinatoires, employant des techniques d'intelligence artificielle, de la recherche opérationnelle, de théorie des graphes,..., etc. L'idée de base de la programmation par contraintes est que l'utilisateur exprime ses contraintes et qu'un solveur de contraintes cherche une ou plusieurs solutions.Les problèmes de satisfaction de contraintes (CSP), sont au cœur de la programmation par contraintes. Ce sont des problèmes de décision où nous recherchons des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Ces problèmes de décision revoient vrai, si le problème admet une solution, faux, sinon. Les problèmes de satisfaction de contraintes sont le sujet de recherche intense tant en recherche opérationnelle qu'en intelligence artificielle. Beaucoup de CSPs exigent la combinaison d'heuristiques et de méthode d'inférences combinatoires pour les résoudre dans un temps raisonnable.Avec l'amélioration des ordinateurs, la résolution de plus grands problèmes devient plus facile. Bien qu'il y ait plus de capacités offertes par la nouvelle génération de machines, les problèmes industriels deviennent de plus en plus grand ce qui implique un espace _norme pour les stocker et aussi plus de temps pour les résoudre.Cette thèse s'articule autour des techniques d'optimisation de la résolution des CSPs en raisonnant sur plusieurs axes.Dans la première partie, nous traitons la compression des contraintes table. Nous proposons deux méthodes différentes pour la compression des contraintes de table. Les deux approches sont basées sur la recherche des motifs fréquents pour éviter la redondance. Cependant, la façon de définir un motif, la détection des motifs fréquents et la nouvelle représentation compacte diffère significativement. Nous présentons pour chacune des approches un algorithme de filtrage.La seconde partie est consacrée à une autre façon d'optimiser la résolution de CSP qui est l'utilisation d'une architecture parallèle. Nous proposons une méthode où nous utilisons une architecture parallèle pour améliorer le processus de résolution en établissant des cohérences parallèles. En fait, les esclaves envoient à leur maître le résultat obtenu après avoir établi la cohérence partielle en tant que nouveaux faits. Le maître, à son tour essaye de profiter d'eux en enlevant les valeurs correspondantesConstraint Programming (CP) is a powerful paradigm used for modelling and solving combinatorial constraint problems that relies on a wide range of techniques coming from artificial intelligence, operational research, graph theory,..., etc. The basic idea of constraint programming is that the user expresses its constraints and a constraint solver seeks a solution. Constraint Satisfaction Problems (CSP), is a framework at the heart of CP problems. They correspond to decision problems where we seek for states or objects satisfying a number of constraints or criteria. These decision problems have two answers to the question they encode: true, if the problem admits a solution, false, otherwise. CSPs are the subject of intense research in both artificial intelligence and operations research. Many CSPs require the combination of heuristics and combinatorial optimization methods to solve them in a reasonable time.With the improvement of computers, larger and larger problems can be solved. However, the size of industrial problems grow faster which requires a vast amount of memory space to store them and entail great difficulties to solve them. In this thesis, our contributions can be divided into two main parts. In the first part, we deal with the most used kind of constraints, which are table constraints. We proposed two compressed forms of table constraints. Both of them are based on frequent patterns search in order to avoid redundancy. However, the manner of defining pattern, the patterns-detecting process and the new compact representation differ significantly. For each form, we propose a filtering algorithm. In the second part, we explore another way to optimize CSP solving which is the use of a parallel architecture. In fact, we enhance the solving process by establishing parallel consistencies. Different workers send to their master the result of establishing partial consistencies as new discovered facts. The master, in its turns tries to benefit from them by removing corresponding values
47
Thierry, Caroline. "Planification et ordonnancement multi-site : une approche par satisfaction de contraintes." Toulouse, ENSAE, 1994. http://www.theses.fr/1994ESAE0025.
Full textAbstract:
Ce travail concerne la gestion et la coordination d'un ensemble d'unités de production réparties en différents sites et entre lesquelles s'échangent des flux de produits. Le problème consiste à trouver comment répartir dans le temps les productions correspondant à des commandes de produits entre les différentes unités de production, certains produits ou composants pouvant être produits dans plusieurs de ces unités de production. Cette répartition est faite en tenant compte des capacités de production des différents sites, avec des objectifs de minimisation de critères globaux. Ce problème est modélisé comme un problème de satisfaction de contraintes (CSP). Un langage de programmation par contraintes mettant en œuvre des méthodes nouvelles issues des recherches dans le domaine des CSP est utilisé pour la résolution. Différentes stratégies de recherche de solutions sont proposées et classées. L’ajout de périodes de taille variables permet de limiter la combinatoire du problème et de respecter la précision des données (commandes à plus ou moins long terme). La prise en compte au niveau planification de certaines contraintes du niveau ordonnancement est effectuée grâce à une approche intégrée planification et ordonnancement multi-site. L’intégration des résultats et du logiciel issus de ce travail a été effectuée sur un logiciel a vocation industrielle dans le cadre d'un projet européen.
48
Janssen, Philippe. "Aide à la conception : une approche basée sur la satisfaction de contraintes." Montpellier 2, 1990. http://www.theses.fr/1990MON20039.
Full textAbstract:
Nous nous interessons a la conception d'objets pertinents sous contraintes. Ces objets sont definis par un ensemble de variables connues a priori et par un ensemble de contraintes de deux types: les contraintes de validite definissant les objets admissibles et les contraintes de preference exprimant les qualites des objets recherches. Nous proposons un formalisme issu des problemes de satisfaction de contraintes (csp): les csp dynamiques. Ce modele est a la base d'une approche interactive d'aide a la conception. Les mecanismes developpes pour cette approche reposent sur les resultats obtenus en satisfaction de contraintes. Une illutration du modele est fournie pour le probleme de la conception de plans de synthese peptidique
49
Givry, Simon de. "Algorithmes d'optimisation sous contraintes étudiés dans un cadre temps réel." Toulouse, ENSAE, 1998. http://www.theses.fr/1998ESAE0002.
Full textAbstract:
Les systèmes temps réels intelligents, c'est-à-dire capables de prendre des décisions en temps contraint, constituent un nouveau défi. La nouveauté provient de la nature des tâches à ordonnancer sur le processeur : une prise de décision n'est pas vue comme un résultat complet, optimum, obtenu en temps borné ; elle correspond plutôt à un résultat approché, de qualité croissante en fonction du temps alloué. Le système ne vise plus seulement à garantir les échéances temporelles d'un ensemble de tâches ; il essaie aussi de maximiser la qualité en sortie du système. Nous avons choisi comme problèmes de décision la classe des problèmes de minimisation de la violation de contraintes. Un formalisme novateur, appelé problèmes de satisfaction de contraintes valuées, permet de modéliser ces problèmes d'optimisation. Pour un problème donné, il est difficile de prédire l'évolution de la qualité, afin de l'ordonnancer au mieux vis-à-vis des autres tâches gérées par le système. Notre approche pragmatique consiste à encadrer progressivement l'optimum lors de la résolution d'un problème. Cet encadrement est une information exacte de l'état d'avancement d'une tâche et un critère important pour répartir les efforts de calcul pour un ensemble de tâches d'optimisation. Concrétement, pour des problèmes de minimisation, l'encadrement est obtenu par coopération de méthodes incomplètes permettant de produire des majorants et de méthodes complètes permettant de produire des minorants. Nos travaux portent sur la production de minorants. Nous décrivons plusieurs méthodes originales et génériques pour simplifier soit la structure d'un problème, soit l'objectif, soit la procédure de recherche. Ces techniques sont expérimentées sur des problèmes générés aléatoirement, ainsi que sur des problèmes réels : planification des prises de vue du satellite Spot5, allocation de fréquences à des liens radio (CELAR).
50
Anglada, Alexis. "Introduction de mécanisme de flexibilité dans la programmation par contraintes sur les domaines continus." Paris 6, 2005. http://www.theses.fr/2005PA066261.
Full text