Le développement de sources cohérentes de rayons X offre de nouvelles possibilités pour visualiser les structures biologiques à différentes échelles en exploitant la réfraction des rayons X. La cohérence des sources synchrotron de troisième génération permettent des implémentations efficaces des techniques de contraste de phase. Une des premières mesures des variations d'intensité dues au contraste de phase a été réalisée en 1995 à l'Installation Européenne de Rayonnement Synchrotron (ESRF). L'imagerie de phase couplée à l'acquisition tomographique permet une imagerie tridimensionnelle avec une sensibilité accrue par rapport à la tomographie standard basée sur absorption. Cette technique est particulièrement adaptée pour les échantillons faiblement absorbante ou bien présentent des faibles différences d'absorption. Le contraste de phase a ainsi une large gamme d'applications, allant de la science des matériaux, à la paléontologie, en passant par la médecine et par la biologie. Plusieurs techniques de contraste de phase aux rayons X ont été proposées au cours des dernières années. Dans la méthode de contraste de phase basée sur le phénomène de propagation l'intensité est mesurée pour différentes distances de propagation obtenues en déplaçant le détecteur. Bien que l'intensité diffractée puisse être acquise et enregistrée, les informations de phase du signal doivent être "récupérées" à partir seulement du module des données mesurées. L'estimation de la phase est donc un problème inverse non linéaire mal posé et une connaissance a priori est nécessaire pour obtenir des solutions stables. Si la plupart de méthodes d'estimation de phase reposent sur une linéarisation du problème inverse, les traitements non linéaires ont été très peu étudiés. Le but de ce travail était de proposer et d'évaluer des nouveaux algorithmes, prenant en particulier en compte la non linéarité du problème direct. Dans la première partie de ce travail, nous présentons un schéma de type Landweber non linéaire itératif pour résoudre le problème de la récupération de phase. Cette approche utilise l'expression analytique de la dérivée de Fréchet de la relation phase-intensité et de son adjoint. Nous étudions aussi l'effet des opérateurs de projection sur les propriétés de convergence de la méthode. Dans la deuxième partie de cette thèse, nous étudions la résolution du problème inverse linéaire avec un algorithme en coordonnées ondelettes basé sur un seuillage itératif. Par la suite, les deux algorithmes sont combinés et comparés avec une autre approche non linéaire basée sur une régularisation parcimonieuse et un algorithme de point fixe. Les performances des algorithmes sont évaluées sur des données simulées pour différents niveaux de bruit. Enfin, les algorithmes ont été adaptés pour traiter des données réelles acquises en tomographie de phase à l'ESRF à Grenoble.

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

L’énergie apparaît comme un problème public majeur, dans la résolution duquel les pouvoirs publics s’engagent régulièrement. Mais, à l’autre bout de cette chaîne, comment les individus ordinaires s’approprient-ils le problème public de l’énergie ? Dans les mesures classiques de l’opinion publique, les questions énergétiques et environnementales sont souvent loin d’occuper les premières places dans la hiérarchie des priorités. Or, pour réduire la pression engendrée par nos modes de consommation sur les écosystèmes, le changement des comportements et des attitudes de consommation est présenté comme un levier majeur. La question énergétique est-elle alors un enjeu politique pour tous mais un problème pour personne ? Pour répondre à cette question nous nous interrogeons sur la fabrique des opinions ordinaires et nous proposons de considérer ces dernières comme des énoncés discursifs testés dans des situations sociales plus ou moins complexes, conflictuelles et publiques. En amont, bon nombre d'acteurs ayant accès à l'espace public contribue à orienter et promouvoir certaines injonctions normatives pour définir la « bonne » pratique. Mais ces injonctions ne sont ni stables, ni homogènes : elles font l'objet de controverses et donnent lieu à des reformulations discursives parfois dissonantes. Entre enjeux technologiques, économiques, écologiques, sociétaux, etc. l’énergie comme problème public est alors soumise à un cadrage par des ordres normatifs dynamiques définissant certaines déviances et se voit proposer des solutions reconnues comme légitimes sous l’effet, entre autres, de l’action publique. Mais, ce niveau de description fait l’économie de la parole des citoyens « ordinaires », couvrant ainsi un présupposé instrumental commun qui estime que les citoyens dotés de la « bonne » information agissent « correctement ». Ce présupposé est contestable. Certes, une majorité écrasante d’enquêtés souligne son accord de principe aux économies d’énergie, témoignant ainsi de sa connaissance – même partielle – de l’existence d’un « problème public de l’énergie » et d’un engagement – même limité – aux injonctions à la modération en termes de consommation énergétique. Mais cet accord tacite se heurte à d’autres injonctions, à la compétition des problèmes, des pratiques sociales et à la mise en œuvre pratique des solutions. Ni surcompétents, ni incompétents, les citoyens ordinaires construisent donc du sens à travers des ordres normatifs concurrentiels et cherchent à le rendre compatible avec leurs modes de vie. Pour ce faire, la confrontation de leurs opinions et l’ajustement collectif de leurs représentations sont nécessaires. En reprenant certaines notions du pragmatisme, nous interrogeons la manière dont les perceptions du problème de l’énergie varient selon les scènes sociales où il est discuté, leur publicité ou encore le degré de conflictualité qu’il génère, et nous montrons que des communautés locales interprétatives d’un problème – et éventuellement de solutions – peuvent émerger et contribuer à alimenter la légitimité du problème dans l’espace public. Par ce biais, nous soulignons qu’il existe des espaces adossés au politique mais qui ne répondent pas toujours aux critères de conflictualisation et montée en généralité. Ces espaces illustrent l’intérêt de prendre en compte l’ambivalence et la labilité des opinions dans l’appropriation d’un problème public et la normalisation de ses solutions. / Energy appears to be a major public problem, in which the public authorities regularly commit. But at the other end of this chain, how do ordinary individuals appropriate the public problem of energy? In the classical measures of public opinion, energy and environmental issues are often far from the top of the hierarchy of priorities. However, to reduce the pressure generated by our consumption patterns on ecosystems, the change in consumer behavior and attitudes is presented as a major lever. Is the energy issue then a political issue for all but a problem for no one? In order to answer this question, we question the fabric of ordinary opinions and propose to consider them as discursive statements tested in more or less complex, conflicting and public social situations.Upstream, many actors with access to public space help to guide and promote certain normative injunctions to define "good" practice. But these injunctions are neither stable nor homogeneous: they are the subject of controversies and give rise to discursive reformulations, sometimes dissonant. Between technological, economic, ecological, societal, etc. energy as a public problem is then subjected to a framing by dynamic normative orders defining certain deviations and is offered solutions recognized as legitimate under the influence of, inter alia, public action.But this level of description does not take "ordinary" citizens into account, and covers a common instrumental presupposition that citizens with "good" information act "correctly". This presupposition is questionable. Admittedly, an overwhelming majority of respondents stressed their agreement in principle to energy savings, thus demonstrating their knowledge - even partial - of the existence of a "public energy problem" and a commitment - even limited - to injunctions to moderate their energy consumption. But this tacit agreement comes up against other injunctions, competition between problems, social practices and the practical implementation of solutions.Neither overcompetent nor incompetent, ordinary citizens construct meaning through competitive normative norms and seek to make it compatible with their lifestyles. To do this, the confrontation of their opinions and the collective adjustment of their representations are necessary. By taking up some of the notions of pragmatism, we examine how the perceptions of the energy problem vary according to the social scenes in which it is discussed, their publicity or the degree of conflict that they generate, and we show that local communities with a common interpretation of a problem - and possibly solutions - can emerge and help fuel the legitimacy of the problem in public space. In this way, we emphasize that there are more or less public spaces but which do not always meet the criteria of conflictualization and rise in generality. These spaces illustrate the importance of taking into account the ambivalence and the lability of opinions in the appropriation of a public problem and the standardization of its solutions.

Les travaux présentes dans cette thèse s'inscrivent dans le cadre des méthodes d'évacuation des populations. Ils visent à étudier les capacités et modéliser le problème d'évacuation (blessés, sinistrés, enfants, personnes agées, etc.) dans une situation de crise (attentats terroristes, catastrophes naturelles, etc.) et développer des méthodes d'aide à la décision tout en proposant une meilleure planification et des plans optimaux d'évacuation des populations de la zone de crise vers les centres hospitaliers.Notre travail consiste à résoudre le problème d'évacuation de blessés dans des zones de crise avec une nouvelle vision qui consiste à optimiser le temps de transport et par conséquent sauver le maximum des personnes touchées par cette crise d'une façon dynamique, efficace et rapide pour minimiser la perte humaine. / The work presented in this thesis is part of human evacuation methods. It aims to study the capacities, model the evacuation problem (wounded, victims, children, elderly, etc.) in a crisis situation (terrorist attacks, natural disasters, etc.) and to develops methods for decision making while proposing better planning and optimal evacuation plans for populations from the crisis zone to hospitals.Our job is to solve the wounded evacuation problem in crisis zone with a new vision that optimizes the transport time and thus saving the maximum of causalities in a dynamic, efficient and fast way in order to minimize human loss.

Le thème de cette thèse est l'identification de paramètres tels que la conductivité hydraulique, K, pour un problème d'intrusion marine dans un aquifère isotrope et libre. Plus précisément, il s'agit d'estimer la conductivité hydraulique en fonction d'observations ou de mesures sur le terrain faites sur les profondeurs des interfaces (h, h₁), entre l'eau douce et l'eau salée et entre le milieu saturé et la zone insaturée. Le problème d'intrusion marine consiste en un système à dérivée croisée d'edps de type paraboliques décrivant l'évolution de h et de h₁. Le problème inverse est formulé en un problème d'optimisation où la fonction coût minimise l'écart quadratique entre les mesures des profondeurs des interfaces et celles fournies par le modèle. Nous considérons le problème exact comme une contrainte pour le problème d'optimisation et nous introduisons le Lagrangien associé à la fonction coût. Nous démontrons alors que le système d'optimalité a au moins une solution, les princcipales difficultés étant de trouver le bon ensemble pour les paramètres admissibles et de prouver la différentiabilité de l'application qui associe (h(K), h₁(K₁)) à K. Ceci constitue le premier résultat de la thèse. Le second résultat concerne l'implémentation numérique du problème d'optimisation. Notons tout d'abord que, concrètement, nous ne disposons que d'observations ponctuelles (en espace et en temps) correspondant aux nombres de puits de monitoring. Nous approchons donc la fonction coût par une formule de quadrature qui est ensuite minimisée en ultilisant l'algorithme de la variable à mémoire limitée (BLMVM). Par ailleurs, le problème exact et le problème adjoint sont discrétisés en espace par une méthode éléments finis P₁-Lagrange combinée à un schéma semi-implicite en temps. Une analyse de ce schéma nous permet de prouver qu'il est d'ordre 1 en temps et en espace. Certains résultats numériques sont présentés pour illustrer la capacité de la méthode à déterminer les paramètres inconnus. Dans la troisième partie de la thèse, nous considérons la conductivité hydraulique comme un paramètre stochastique. Pour réaliser une étude numérique rigoureuse des effets stochastiques sur le problème d'intrusion marine, nous utilisons les développements de Wiener pour tenir compte des variables aléatoires. Le système initiale est alors transformé en une suite de systèmes déterministes qu'on résout pour chaque coefficient stochastique du développement de Wiener. / This thesis is concerned with the identification, from observations or field measurements, of the hydraulic conductivity K for the saltwater intrusion problem involving a nonhomogeneous, isotropic and free aquifer. The involved PDE model is a coupled system of nonlinear parabolic equations completed by boudary and initial conditions, as well as compatibility conditions on the data. The main unknowns are the saltwater/freshwater interface depth and the elevation of upper surface of the aquifer. The inverse problem is formulated as the optimization problem where the cost function is a least square functional measuring the discrepancy between experimental interfaces depths and those provided by the model. Considering the exact problem as a constraint for the optimization problem and introducing the Lagrangian associated with the cost function, we prove that the optimality system has at least one solution. The main difficulties are to find the set of all eligible parameters and to prove the differentiability of the operator associating to the hydraulic conductivity K, the state variables (h, h₁). This is the first result of the thesis. The second result concerns the numerical implementation of the optimization problem. We first note that concretely, we only have specific observations (in space and in time) corresponding to the number of monitoring wells, we then adapt the previous results to the case of discrete observations data. The gradient of the cost function is computed thanks to an approximate formula in order to take into account the discrete observations data. The cost functions then is minimized by using a method based on BLMVM algorithm. On the other hand, the exact problem and the adjoint problem are discretized in space by a P₁-Lagrange finite element method combined with a semi-implicit time discretization scheme. Some numerical results are presented to illustrate the ability of the method to determine the unknown parameters. In the third part of the thesis we consider the hydraulic conductivity as a stochastic parameter. To perform a rigorous numerical study of stochastic effects on the saltwater intrusion problem, we use the spectral decomposition and the stochastic variational problem is reformulated to a set of deterministic variational problems to be solved for each Wiener polynomial chaos.

Les problèmes d’optimisation combinatoire sont généralement réputés NP-difficiles, donc il n’y a pas d’algorithmes efficaces pour les résoudre. Afin de trouver des solutions optimales locales ou réalisables, on utilise souvent des heuristiques ou des algorithmes approchés. Les dernières décennies ont vu naitre des méthodes approchées connues sous le nom de métaheuristiques, et qui permettent de trouver une solution approchées. Cette thèse propose de résoudre des problèmes d’optimisation déterministe et stochastique à l’aide de métaheuristiques. Nous avons particulièrement étudié la méthode de voisinage variable connue sous le nom de VNS. Nous avons choisi cet algorithme pour résoudre nos problèmes d’optimisation dans la mesure où VNS permet de trouver des solutions de bonne qualité dans un temps CPU raisonnable. Le premier problème que nous avons étudié dans le cadre de cette thèse est le problème déterministe de largeur de bande de matrices creuses. Il s’agit d’un problème combinatoire difficile, notre VNS a permis de trouver des solutions comparables à celles de la littérature en termes de qualité des résultats mais avec temps de calcul plus compétitif. Nous nous sommes intéressés dans un deuxième temps aux problèmes de réseaux mobiles appelés OFDMA-TDMA. Nous avons étudié le problème d’affectation de ressources dans ce type de réseaux, nous avons proposé deux modèles : Le premier modèle est un modèle déterministe qui permet de maximiser la bande passante du canal pour un réseau OFDMA à débit monodirectionnel appelé Uplink sous contraintes d’énergie utilisée par les utilisateurs et des contraintes d’affectation de porteuses. Pour ce problème, VNS donne de très bons résultats et des bornes de bonne qualité. Le deuxième modèle est un problème stochastique de réseaux OFDMA d’affectation de ressources multi-cellules. Pour résoudre ce problème, on utilise le problème déterministe équivalent auquel on applique la méthode VNS qui dans ce cas permet de trouver des solutions avec un saut de dualité très faible. Les problèmes d’allocation de ressources aussi bien dans les réseaux OFDMA ou dans d’autres domaines peuvent aussi être modélisés sous forme de problèmes d’optimisation bi-niveaux appelés aussi problèmes d’optimisation hiérarchique. Le dernier problème étudié dans le cadre de cette thèse porte sur les problèmes bi-niveaux stochastiques. Pour résoudre le problème lié à l’incertitude dans ce problème, nous avons utilisé l’optimisation robuste plus précisément l’approche appelée « distributionnellement robuste ». Cette approche donne de très bons résultats légèrement conservateurs notamment lorsque le nombre de variables du leader est très supérieur à celui du suiveur. Nos expérimentations ont confirmé l’efficacité de nos méthodes pour l’ensemble des problèmes étudiés. / Combinatorial optimization problems are generally NP-hard problems, so they can only rely on heuristic or approximation algorithms to find a local optimum or a feasible solution. During the last decades, more general solving techniques have been proposed, namely metaheuristics which can be applied to many types of combinatorial optimization problems. This PhD thesis proposed to solve the deterministic and stochastic optimization problems with metaheuristics. We studied especially Variable Neighborhood Search (VNS) and choose this algorithm to solve our optimization problems since it is able to find satisfying approximated optimal solutions within a reasonable computation time. Our thesis starts with a relatively simple deterministic combinatorial optimization problem: Bandwidth Minimization Problem. The proposed VNS procedure offers an advantage in terms of CPU time compared to the literature. Then, we focus on resource allocation problems in OFDMA systems, and present two models. The first model aims at maximizing the total bandwidth channel capacity of an uplink OFDMA-TDMA network subject to user power and subcarrier assignment constraints while simultaneously scheduling users in time. For this problem, VNS gives tight bounds. The second model is stochastic resource allocation model for uplink wireless multi-cell OFDMA Networks. After transforming the original model into a deterministic one, the proposed VNS is applied on the deterministic model, and find near optimal solutions. Subsequently, several problems either in OFDMA systems or in many other topics in resource allocation can be modeled as hierarchy problems, e.g., bi-level optimization problems. Thus, we also study stochastic bi-level optimization problems, and use robust optimization framework to deal with uncertainty. The distributionally robust approach can obtain slight conservative solutions when the number of binary variables in the upper level is larger than the number of variables in the lower level. Our numerical results for all the problems studied in this thesis show the performance of our approaches.

Notre objectif dans cette thèse est de proposer des algorithmes efficaces pour résoudre des problèmes d’optimisation combinatoire difficiles. Dans un premier temps, nous établissons le principe de l’énumération ordonnée qui consiste à générer dans un ordre adéquat les solutions d’un problème relâché associé au problème principal jusqu’à l’obtention de la preuve d’optimalité d’une solution. Nous construisons une procédure générique dans le cadre général des problème d’optimisation combinatoire. Dans un second temps nous abordons les applications de notre algorithme sur des problèmes qui admettent le problème d’affectation comme relaxation. Le premier cas particulier que nous étudions est la recherche d’une solution de bon compromis pour le problème d’affectation multiobjectif. La seconde application se rapporte au problème du voyageur de commerce asymétrique qui présente la difficulté de comporter des contraintes qui interdisent les sous-tournées, en plus des contraintes du problème d’affectation. / Our aim in this thesis is to propose efficient algorithms for solving difficult combinatorial optimization problems. Our algorithms are based on a generic method of ordered enumeration. Initially, we describe the principle of ordered enumeration which consists in generating in a specific order solutions of a relaxed problem associated to the difficult main problem, until meeting a proof of the optimality of a feasible solution. We construct a generic procedure in the general context of combinatorial optimization problems. In a second step we discuss applications of our algorithm on some difficult problems which admit the assignment problem as relaxation. The first special case we study is the search for a compromise solution to the multiobjective assignment problem. The second application is the asymmetric travelling salesman problem, which contains sub-tour constraints in addition to the constraints of the assignment problem.

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 WCSP. / This 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.

Ce mémoire contient deux articles que j’ai rédigés au cours de ma maîtrise. Le premier chapitre sert d’introduction à ces articles. Plusieurs concepts de géométrie spectrale y sont présentés dans le contexte du problème de Steklov, en plus des résultats principaux des chapitres subséquents. Le second chapitre porte sur le problème de Steklov paramétrique sur des surfaces lisses. Un développement asymptotique complet des valeurs propres du problème est obtenu à l’aide de méthodes pseudodifférentielles. Celui-ci généralise l’asymptotique spectrale déjà connue du problème de Steklov classique. Nous en déduisons de nouveaux invariants géométriques déterminés par le spectre. Le troisième chapitre porte sur le problème de ballottement sur des prismes à base triangulaire. Le but est de comprendre comment les angles du prisme affectent le deuxième terme du développement asymptotique de la fonction de compte des valeurs propres. En construisant des quasimodes, nous obtenons une expression de ce terme que nous conjecturons comme étant la bonne pour les vraies valeurs propres. Cette conjecture est alors supportée par des expériences numériques. / This thesis contains two articles that I wrote during my M.Sc. studies. The first chapter serves as an introduction to both articles. Some concepts of spectral geometry in the context of the Steklov problem are presented, as well as the main results of the subsequent chapters. The second chapter concerns the parametric Steklov problem on smooth surfaces. We obtain a complete asymptotic expansion of the eigenvalues of the problem by using pseudodifferential techniques. This generalizes the already known spectral asymptotics of the classical Steklov problem. We deduce new geometric invariants determined by the spectrum. The third chapter concerns the sloshing problem on triangular prisms. The goal is to understand how the angles in the prism affect the second term in the asymptotic expansion of the eigenvalue counting function. By constructing quasimodes, we obtain an expression for this term that we conjecture as being correct for the true eigenvalues. This conjecture is then supported by numerical experiments.

Dans cette thèse nous étudierons des problématiques de graphes. Nous proposons deux études théoriques sur la recherche et l'énumération de cliques et quasi-cliques. Ensuite nous proposons une étude appliquée sur la propagation d'information dans un graphe d'entités nommées. Premièrement, nous étudierons la recherche de cliques dans des graphes compressés. Les problèmes MCE et MCP sont des problèmes rencontrés dans l'analyse des graphes. Ce sont des problèmes difficiles, pour lesquels des solutions adaptées doivent être conçues pour les grands graphes. Nous proposons de travailler sur une version compressée du graphe. Nous montrons les bons résultats obtenus par notre méthode pour l'énumération de cliques maximales. Secondement, nous étudierons l'énumération de quasi-cliques maximales. Nous proposons un algorithme distribué qui énumère l'ensemble des quasi-cliques maximales. Nous proposons aussi une heuristique qui liste des quasi-cliques plus rapidement. Nous montrons l'intérêt de l'énumération de ces quasi-cliques par une évaluation des relations en regardant la co-occurrence des noeuds dans l'ensemble des quasi-cliques énumérées. Troisièmement, nous travaillerons sur la diffusion d'événements dans un graphe d'entités nommées. De nombreux modèles existent pour simuler des problèmes de diffusion de rumeurs ou de maladies dans des réseaux sociaux ou des problèmes de propagation de faillites dans les milieux bancaires. Nous proposons de répondre au problème de diffusion d'événements dans des réseaux hétérogènes représentant un environnement économique du monde. Nous proposons un problème de diffusion, nommé problème de classification de l'infection, qui consiste à déterminer quelles entités sont concernées par un événement. Pour ce problème, nous proposons deux modèles inspirés du modèle de seuil linéaire auxquels nous ajoutons différentes fonctionnalités. Finalement, nous testons et validons nos modèles sur un ensemble d'événements / In this thesis we will study graph problems. We will study theoretical problems in pattern research and applied problems in information diffusion. We propose two theoretical studies on the identification/detection and enumeration of dense subgraphs, such as cliques and quasi-cliques. Then we propose an applied study on the propagation of information in a named entities graph. First, we will study the identification/detection of cliques in compressed graphs. The MCE and MCP are problems that are encountered in the analysis of data graphs. These problem are difficult to solve (NP-Hard for MCE and NP-Complete for MCP), and adapted solutions must be found for large graphs. We propose to solve these problems by working on a compressed version of the initial graph. We show the correct results obtained by our method for the enumeration of maximal cliques on compressed graphs. Secondly, we will study the enumeration of maximal quasi-cliques. We propose a distributed algorithm that enumerates the set of maximal quasi-cliques of the graph. We show that this algorithm lists the set of maximal quasi-cliques of the graph. We also propose a heuristic that lists a set of quasi-cliques more quickly. We show the interest of enumerating these quasi-cliques by an evaluation of relations by looking at the co-occurrence of nodes in the set of enumerated quasi-cliques. Finally, we work on the event diffusion in a named entities graph. Many models exist to simulate diffusion problems of rumors or diseases in social networks and bankruptcies in banking networks. We address the issue of significant events diffusion in heterogeneous networks, representing a global economic environment. We propose a diffusion problem, called infection classification problem, which consists to dertemine which entities are concerned by an event. To solve this problem we propose two models inspired by the linear threshold model to which we add different features. Finally, we test and validate our models on a set of events