Hiérarchie de contraintes : quelques approches de résolution
Résumé
The goal of this work is to propose some approaches that solve functional constraint hierarchies. First, we define the role and the interesting features of a constraint hierarchy. A constraint hierarchy allows to represent and solve over-constrained problems. Second, we have conceived a new solver that solves and maintains solutions of a functional constraint hierarchy, in order to obtain solutions of a better quality than the existing solvers. The algorithmic approach used by this solver is the "best first search". This solver considers different error combination modes at each level of the hierarchy and uses a global lexicographic aggregation on the values of these combinations. The global combination modes integrated in this solver are : the number of unsatisfied constraints, a combination where the weights represent priorities between the constraints in order to handle replacement constraints and the sum of the weights of unsatisfied constraints. Third, we propose an algorithm based on the previous solver and on the extended notion of comparators for comparisons between the hierarchies that anse from alternate rule choices in the program. This algorithm is more promising than a branch and bound algorithm and can be incorporated in hierarchical constraint logic programing languages. This algorithm allows to achieve the inter-hierarchies comparison and to eliminate the hierarchies such that these hierarchies may lead to undesirable solutions. Finally, we propose a model of a second solver. It treats a single system where different types of constraints are unified. This solver supports constraints with multi-output variables. If constraints don't need to be solved simultaneously then this solver divides them as much as possible into subsets of constraints and solves each subset by invoking a specific subsolver.
L'objectif de ce travail est de proposer quelques approches pour la résolution de hiérarchies de contraintes fonctionnelles. Dans un premier temps, le rôle et les qualités d'une hiérarchie de contraintes sont définis. Une hiérarchie de contraintes permet de résoudre des problèmes sur-contraints en répartissant les contraintes dans une hiérarchie (de niveaux) suivant leur importance. Dans un deuxième temps, un nouveau résolveur de maintien de solutions pour les hiérarchies de contraintes fonctionnelles a été conçu afin d'obtenir des solutions de meilleure qualité. Ce résolveur est basé sur l'utilisation d'un algorithme du type "meilleur d'abord" et prend en compte différents modes de combinaison des erreurs par niveau et utilise une agrégation globale de type lexicographique sur les valeurs de ces combinaisons. Les modes de combinaison globale intégrés dans ce résolveur sont : le nombre de contraintes non satisfaites, une combinaison où les poids représentent des priorités pour considérer des contraintes de remplacement et enfin la somme des poids des contraintes non satisfaites. Dans un troisième temps, nous proposons une procédure utilisant le résolveur précédent. Cette dernière est plus prometteuse qu'un algorithme du type séparation et évaluation. Elle peut être incorporée dans les langages de Programmation Logique par Hiérarchie de Contraintes afin de réaliser la comparaison inter-hiérarchies et donc de pouvoir éliminer les hiérarchies telles que leurs résolutions produiraient des solutions non désirables. Enfin, nous avons modélisé un résolveur pour la résolution de hiérarchies de contraintes où Ses modes de combinaison peuvent varier selon les niveaux. Ce dernier prend en compte des contraintes possédant des méthodes recalculant plusieurs variables à la fois et établit un plan de coopération entre des résolveurs spécifiques. Ces résolveurs spécifiques doivent être conçus selon les modes de combinaison utilisés.
Loading...