Spelling suggestions: "subject:"csp"" "subject:"ccsp""
1 |
La substituabilité et la cohérence de tuples pour les réseaux de contraintes pondérées / The substitutability and the tuples consistency for weighted constraint networksDehani, Djamel-Eddine 13 February 2014 (has links)
Cette thèse se situe dans le domaine de la programmation par contraintes (CP). Plus précisément, nous nous intéressons au problème de satisfaction de contraintes pondérées (WCSP), qui est un problème d'optimisation pour lequel plusieurs formes de cohérences locales souples telles que, par exemple, la cohérence d’arc existentielle directionnelle (EDAC*) et la cohérence d’arc virtuelle (VAC) ont été proposées durant ces dernières années. Dans ce cadre, nous adoptons une perspective différente en revisitant la propriété bien connue de la substituabilité. Tout d’abord, nous précisons les relations existant entre la substituabilité de voisinage souple (SNS) et une propriété appelée pcost qui est basée sur le concept de surcoût de valeurs (par le biais de l'utilisation de paires de surcoût). Nous montrons que sous certaines hypothèses, pcost est équivalent à SNS, mais que dans le cas général, elle est plus faible que SNS prouvée être coNP-difficile. Ensuite, nous montrons que SNS conserve la propriété VAC, mais pas la propriété EDAC. Enfin, nous introduisons un algorithme optimisé et nous montrons sur diverses séries d’instances WCSP l’intérêt pratique du maintien de pcost avec AC*, FDAC* ou EDAC*, au cours de la recherche. Nous introduisons un algorithme optimisé et nous étudions la relation existante entre SNS et les différentes cohérences. Nous présentons aussi un nouveau type de propriétés pour les WCSPs. Il s'agit de la cohérence de tuples (TC) dont l'établissement sur un WCN est effectué grâce à une nouvelle opération appelée TupleProject. Nous proposons également une version optimale de cette propriété, OTC, qui peut être perçue comme une généralisation de OSAC (Optimal Soft Arc Consistency). Enfin, nous étendons la notion de substituabilité souple aux tuples. / This thesis is in the field of constraint programming (CP). More precisely, we focus on the weighted constraint satisfaction problem (WCSP), which is an optimization problem for which many forms of soft local (arc) consistencies have been proposed such as, for example, existential directional arc consistency (EDAC) and virtual arc consistency (VAC) in recent years. In this context, we adopt a different perspective by revisiting the well-known property of (soft) substitutability. First, we provide a clear picture of the relationships existing between soft neighborhood substitutability (SNS) and a tractable property called $pcost$ which allows us to compare the cost of two values (through the use of so-called cost pairs). We prove that under certain assumptions, $pcost$ is equivalent to SNS but weaker than SNS in the general case since we show that SNS is coNP-hard. We also show that SNS preserves the property VAC but not the property EDAC. Finally, we introduce an optimized algorithm and we show on various series of WCSP instances, the practical interest of maintaining $pcost$ together with AC*, FDAC* or EDAC*, during search. We also present a new type of properties for WCSPs called tuples consistency (TC). Enforcing TC is done through a new operation called TupleProject. Moreover, we propose an optimal version of this property, OTC, which can be seen as a generalization of OSAC (Optimal Soft Arc Consistency). Finally, we extend soft substitutability concept to tuples.
|
2 |
Résolution des problèmes (W)CSP et #CSP par approches structurelles : calcul et exploitation dynamique de décompositions arborescentes / Solving (W)CSP and #CSP problems by structural approaches : computation and dynamic exploitation of tree decompositionsKanso, Hélène 20 December 2017 (has links)
L’importance des problèmes CSP, WCSP et #CSP est reflétée par la part considérable des travaux, théoriques et pratiques, dont ils font l’objet en intelligence artificielle et bien au-delà. Leur difficulté est telle qu’ils appartiennent respectivement aux classes NP-complet, NP-difficile et #P-complet. Aussi, les méthodes qui permettent de résoudre efficacement leurs instances ont une complexité en temps exponentielle. Les travaux de recherche de cette thèse se focalisent sur les méthodes de résolution exploitant la notion de décomposition arborescente. Ces méthodes ont suscité un vif intérêt de la part de la communauté scientifique du fait qu’elles soient capables de résoudre en temps polynomial certaines classes d’instances. Cependant, en pratique, elles n’ont pas encore montré toute leur efficacité vu la qualité de la décomposition employée ne prenant en compte qu’un critère purement structurel, sa largeur. Premièrement, nous proposons un nouveau cadre général de calcul de décompositions qui a la vertu de calculer des décompositions qui capturent des paramètres plus pertinents à l’égard de la résolution que la seule largeur de la décomposition. Ensuite, nous proposons une exploitation dynamique de la décomposition pendant la résolution pour les problèmes (W)CSP. Le changement de la décomposition pendant la résolution vise à adapter la décomposition selon la nature de l’instance. Finalement, nous proposons un nouvel algorithme de comptage qui exploite la décomposition d’une façon différente de celle des méthodes standards afin d’éviter des calculs inutiles.L’ensemble des contributions ont été évaluées et validées expérimentalement. / The importance of CSP, WCSP and #CSP problems is reflected by the considerableamount of theoretical and practical work of which they are subject in artificial intelligenceand far beyond. Their difficulty is such that they belong respectively to the NP-complete,NP-hard and #P-complete classes. Hence, the methods that are able to solve efficientlytheir instances have a complexity in exponential time. The research works of this thesisfocus on the solving methods exploiting the notion of tree-decomposition. These methodshave aroused a keen interest from the scientific community because they are able to solvesome classes of instances in polynomial time. Nevertheless, in practice, they have notshown yet their full efficiency given the quality of the used decomposition that takes onlyinto account a purely structural criterion, its width. First, we propose a new generic framework for computing decompositions which has the virtue of computing decompositionsthat capture more relevant parameters in the context of solving than the width. Then,we propose a dynamic exploitation of the decomposition during the solving for (W)CSPproblems. The modification of the decomposition during the solving aims to adapt the decomposition to the nature of the instance. Finally, we propose a new counting algorithmthat exploits the decomposition in a different way than standard methods in order toavoid unnecessary computations. All the contributions have been evaluated and validatedexperimentally.
|
Page generated in 0.037 seconds