No description available.

Cette thèse traite de l'adaptation du niveau de cohérence locale au cours de la résolution d'un problème de satisfaction de contraintes (CSP). En particulier, nous nous intéressons à l'utilisation des propriétés de cohérence locale plus fortes que la cohérence d'arc (AC) pour gagner en efficacité de résolution d'un CSP. Les cohérences plus fortes que AC sont généralement coûteuses à maintenir dans un réseau de contraintes. Par conséquent, elles sont rarement utilisées en pratique. Cette thèse apporte plusieurs contributions qui permettent de bénéficier de la puissance de filtrage de ces cohérences fortes tout en évitant le coût élevé de les maintenir dans tout le réseau de contraintes. Premièrement, nous introduisons la cohérence locale paramétrée (p-LC), une approche originale qui permet de définir des niveaux de cohérence intermédiaires entre AC et une de cohérence locale LC, plus forte que AC. Puis, nous présentons l'instanciation de cette approche à maxRPC et SAC, deux cohérences plus fortes que AC. Il en découle deux cohérences paramétrées, à savoir p-maxRPC et p-SAC. Ensuite, nous présentons l'algorithme p-maxRPC3, qui réalise p-maxRPC et l'algorithme p-SAC1, pour réaliser p-SAC dans un réseau de contraintes. Deuxièmement, nous montrons expérimentalement que maintenir un niveau de cohérence intermédiaire p-LC, peut donner un bon compromis entre puissance de filtrage et coût de calcul nécessaire pour maintenir ce niveau de cohérence. En outre, nous montrons que pour chaque instance de CSP il est possible de trouver un paramètre adéquat qui donne ce bon compromis. L'approche de cohérence paramétrée ne précise pas comment le paramètre peut être choisi a priori. Nous proposons donc deux techniques qui permettent d'ajuster automatiquement le niveau de cohérence paramétrée p-LC. Ces deux techniques utilisent plusieurs paramètres à la fois. Chaque paramètre est associé à une partie du problème et s'adapte automatiquement et localement au cours de la résolution. Finalement, nous proposons POAC1, le premier algorithme pour établir partition-one-AC (POAC) dans un réseau de contraintes. Puis, en comparant POAC à SAC nous constatons que POAC converge au point fixe plus rapidement que SAC. Sur la base de ce constat, nous proposons APOAC, une version adaptative de POAC qui contrôle le nombre de variables sur lesquelles POAC est appliqué. / This thesis deals with adapting the level of consistency during solving a constraint satisfaction problem (CSP). It focuses on the use of local consistency properties stronger than arc consistency (AC) to improve the CSP solving efficiency. Local consistency properties stronger than arc consistency are generally expensive to maintain in a constraint network. Therefore, these local consistencies are seldom used in practice. This thesis gives several contributions to benefit from the filtering power of local consistencies stronger than AC while avoiding the high cost of maintaining them in the whole constraint network and throughout the search. First, we introduce the parameterized local consistency (p-LC), an original approach that allows us to define intermediate levels of consistency between AC and a local consistency LC stronger than AC. Then, we present the instantiation of the parameterized local consistency approach to maxRPC and SAC, two consistencies stronger than AC. This leads to two parameterized consistencies, namely p-maxRPC and p-SAC. After giving the definitions of p-maxRPC and p-SAC, we present the algorithm p-maxRPC3, that achieves p-maxRPC and the algorithm p-SAC1, for achieving p-SAC in a constraint network. We show experimentally that maintaining an intermediate level of consistency p-LC, can give a good compromise between filtering power and the computational cost of maintaining this level of consistency. We also show that for each instance of CSP we can find a parameter that gives this good compromise. The parameterized local consistency approach does not specify how the parameter can be chosen a priori. Hence, we propose two techniques to automatically adjust the parameter p. In fact, both techniques don't use a single parameter, but several parameters. Each parameter is mapped to a part of the problem and it is automatically and locally adjusted during search. Finally, we propose POAC1, the first algorithm achieving partition-one-AC (POAC) in a constraint network. We compare POAC to SAC and we found that POAC converges faster than SAC to the fixed point due to its ability to prune values from all variable domains when being enforced on a given variable. Based on this observation, we proposed APOAC, an adaptive version of POAC, that monitors the number of variables on which to enforce POAC.

No description available.

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.