Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes / The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem

Le paradigme de l’Internet Physique a été introduit il y a quelques années pour transformer globalement la manière dont les objets physiques seront manipulés, entreposés et transportés dans le cadre d’une logistique durable. L’une des caractéristiques importante de l’Internet Physique est liée à l’encapsulation des marchandises dans des conteneurs modulaires standardisés. Le modèle de fonctionnement proposé de l’Internet Physique, s’il rationnalise les transports, engendre des manutentions plus nombreuses, en particulier au sein des PI-hubs, où les opérations de routage, de déchargement et (re)chargement des conteneurs nécessitent une organisation et une gestion rationnelle. La multiplicité et la diversité des opérations (automatisées ou non) à mettre en œuvre simultanément ne peut être conduite de manière efficiente qu’en cas de parfaite synchronisation entre la réalité du système physique et de celle du système informationnel. Les propositions de cette thèse adressent cette problématique applicative et constituent à ce titre une contribution au concept de l’Internet Physique. Elles visent à l’obtention, en temps réel, d’une image ou d’un modèle spatial des PI-conteneurs, qui disposent chacun d’un nœud WSN. L’assemblage de ces différents conteneurs au sein d’un conteneur de plus haut niveau (ou conteneur composite) permet de constituer alors un réseau de capteurs ad-hoc. Ces conteneurs deviennent ainsi des éléments actifs de l’automatisation de la chaine logistique. A partir des seules informations de proximité issues de cette instrumentation, nous montrons dans cette thèse qu’il est possible de construire le modèle spatial des PI-conteneurs / The Physical Internet paradigm was introduced few years ago to transform globally how physical objects will be handled, stored and transported as part of a sustainable logistics. One of the important characteristics of the Physical Internet is the encapsulation of goods in standardized modular containers. Although the Physical Internet rationalizes transport, it generates more frequent handling, particularly within PI-hubs, where the operations of routing, unloading and (re) loading containers require an efficient organization and management. The multiplicity and the diversity of operations (automated or not) to be implemented simultaneously can only be carried out efficiently in the case of perfect synchronization between the reality of the physical system and that of the information system. The proposals of this thesis address this problem and constitute a contribution to the concept of the Physical Internet. They aim to obtain in real time, the spatial distribution (or layout) of the PI-containers when they are stacked in a higher-level container, so called composite container. To do this, we propose to exploit the intelligence and the activeness concepts of each PI container which is equipped with wireless sensor node. Hence, the composition of a composite PI containers constitutes an adhoc network of sensor nodes. From neighborhood relationships between these nodes, we show in this thesis that it is possible to construct the spatial 3D layout of the PI-containers and control at any time and at any place the effective compliance between the real composition and the data stored in the information system

Ce travail est centré sur la mise au point d'une méthodologie d'exploitation de photographies aériennes prises en période de crue pour en extraire, au moment de la prise de vue, la cote de l'eau en tout point de la plaine. Cette méthodologie, appelée "approche-photo", comporte une phase de traitement de télédétection, une phase d'analyse spatiale et de structuration de l'information dans un SIG, et une phase novatrice et originale de fusion et mise en cohérence de l'ensemble des données extraites (développement d'un algorithme de mise en cohérence inspiré de l'hydraulique et de techniques empruntées au domaine de l'intelligence artificielle). La méthode a été testée sur trois sites d'étude, couvrant un panel très large de contextes. Un travail important de validation et d'analyse de sensibilité a permis de montrer que la précision des estimations de la cote de l'eau, produites sous forme de fourchette [Min, Max], était de l'ordre décimétrique, résultat tout à fait compatible avec les exigences hydrauliques. "L'approche-photo" constitue donc une valorisation quantitative des archives photographiques concernant les crues historiques. Une première retombée provient de la structuration de ces résultats au sein d'un SIG, ce qui les rend facilement mobilisables pour toutes les étapes de la gestion du risque d'inondation. Une seconde retombée, bien plus importante, résulte de la complémentarité de "l'approche-photo" avec les approches traditionnelles. Celle avec la modélisation hydraulique a été approfondie par la mise en œuvre d'un modèle 2D sur la basse vallée de l'Hérault. Une confrontation des résultats a permis de mettre en avant les apports réciproques : "l'approche-photo" comme aide à la structuration, au calage et à la validation de la modélisation et, à l'inverse, la modélisation hydraulique comme aide à la validation de "l'approche-photo".Cette thèse se veut une illustration de l'intérêt d'une démarche multidisciplinaire.

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.

Le test à base de modèles des systèmes réactifs est le processus de vérifier si un système sous test (SUT) est conforme à sa spécification. Il consiste à gérer à la fois la génération des données de test et le calcul de verdicts en utilisant des modèles. Nous spécifions le comportement des systèmes réactifs à l'aide des systèmes de transitions symboliques temporisées à entrée-sortie (TIOSTS). Quand les TIOSTSs sont utilisés pour tester des systèmes avec une interface centralisée, l'utilisateur peut ordonner complètement les événements (i.e., les entrées envoyées au système et les sorties produites). Les interactions entre le testeur et le SUT consistent en des séquences d'entrées et de sortie nommées traces, pouvant être séparées par des durées dans le cadre du test temporisé, pour former ce que l'on appelle des traces temporisées. Les systèmes distribués sont des collections de composants locaux communiquant entre eux et interagissant avec leur environnement via des interfaces physiquement distribuées. Différents événements survenant à ces différentes interfaces ne peuvent plus être ordonnés. Cette thèse concerne le test de conformité des systèmes distribués où un testeur est placé à chaque interface localisée et peut observer ce qui se passe à cette interface. Nous supposons qu'il n'y a pas d’horloge commune mais seulement des horloges locales pour chaque interface. La sémantique de tels systèmes est définie comme des tuples de traces temporisées. Nous considérons une approche du test dans le contexte de la relation de conformité distribuée dtioco. La conformité globale peut être testée dans une architecture de test en utilisant des testeurs locaux sans communication entre eux. Nous proposons un algorithme pour vérifier la communication pour un tuple de traces temporisées en formulant le problème de message-passing en un problème de satisfaction de contraintes (CSP). Nous avons mis en œuvre le calcul des verdicts de test en orchestrant à la fois les algorithmes du test centralisé off-line de chacun des composants et la vérification des communications par le biais d'un solveur de contraintes. Nous avons validé notre approche sur un cas étude de taille significative. / Model-based testing of reactive systems is the process of checking if a System Under Test (SUT) conforms to its model. It consists of handling both test data generation and verdict computation by using models. We specify the behaviour of reactive systems using Timed Input Output Symbolic Transition Systems (TIOSTS) that are timed automata enriched with symbolic mechanisms to handle data. When TIOSTSs are used to test systems with a centralized interface, the user may completely order events occurring at this interface (i.e., inputs sent to the system and outputs produced from it). Interactions between the tester and the SUT are sequences of inputs and outputs named traces, separated by delays in the timed framework, to form so-called timed traces. Distributed systems are collections of communicating local components which interact with their environment at physically distributed interfaces. Interacting with such a distributed system requires exchanging values with it by means of several interfaces in the same testing process. Different events occurring at different interfaces cannot be ordered any more. This thesis focuses on conformance testing for distributed systems where a separate tester is placed at each localized interface and may only observe what happens at this interface. We assume that there is no global clock but only local clocks for each localized interface. The semantics of such systems can be seen as tuples of timed traces. We consider a framework for distributed testing from TIOSTS along with corresponding test hypotheses and a distributed conformance relation called dtioco. Global conformance can be tested in a distributed testing architecture using only local testers without any communication between them. We propose an algorithm to check communication policy for a tuple of timed traces by formulating the verification of message passing in terms of Constraint Satisfaction Problem (CSP). Hence, we were able to implement the computation of test verdicts by orchestrating both localised off-line testing algorithms and the verification of constraints defined by message passing that can be supported by a constraint solver. Lastly, we validated our approach on a real case study of a telecommunications distributed system.