Nous observons ces dernières années un besoin grandissant dans l’industrie pour des robots capables d’interagir et de coopérer dans des environnements confinés. Cependant, aujourd’hui encore, la définition de trajectoires sûres pour les robots industriels doit être faite manuellement par l’utilisateur et le logiciel ne dispose que de peu d’autonomie pour réagir aux modifications de l’environnement. Cette thèse vise à produire une structure logicielle innovante pour gérer l’évitement d’obstacles en temps réel pour des robots manipulateurs évoluant dans des environnements dynamiques. Nous avons développé pour cela un algorithme temps réel de génération de trajectoires qui supprime de façon automatique l’étape fastidieuse de définition d’une trajectoire sûre pour le robot.La valeur ajoutée de cette thèse réside dans le fait que nous intégrons le problème de contrôle optimal dans le concept de hiérarchie de tâches pour résoudre un problème d’optimisation non-linéaire efficacement et en temps réel sur un système embarqué aux ressources limitées. Notre approche utilise une commande prédictive (MPC) qui non seulement améliore la réactivité de notre système mais présente aussi l’avantage de pouvoir produire une bonne approximation linéaire des contraintes d’évitement de collision. La stratégie de contrôle présentée dans cette thèse a été validée à l’aide de plusieurs expérimentations en simulations et sur systèmes réels. Les résultats démontrent l’efficacité, la réactivité et la robustesse de cette nouvelle structure de contrôle lorsqu’elle est utilisée dans des environnements dynamiques. / In the field of industrial robots, there is a growing need for having cooperative robots that interact with each other and share work spaces. Currently, industrial robotic systems still rely on hard coded motions with limited ability to react autonomously to dynamic changes in the environment. This thesis focuses on providing a novel framework to deal with real-time collision avoidance for robots performing tasks in a dynamic environment. We develop a reactive trajectory generation algorithm that reacts in real time, removes the fastidious optimization process which is traditionally executed by hand by handling it automatically, and provides a practical way of generating locally time optimal solutions.The novelty in this thesis is in the way we integrate the proposed time optimality problem in a task priority framework to solve a nonlinear optimization problem efficiently in real time using an embedded system with limited resources. Our approach is applied in a Model Predictive Control (MPC) setting, which not only improves reactivity of the system but presents a possibility to obtain accurate local linear approximations of the collision avoidance constraint. The control strategies presented in this thesis have been validated through various simulations and real-world robot experiments. The results demonstrate the effectiveness of the new control structure and its reactivity and robustness when working in dynamic environments.

Les programmes informatiques prennent une place de plus en plus importante dans nos vies. Certains de ces programmes, comme par exemple les systèmes de contrôle de centrales électriques, d'avions ou de systèmes médicaux sont critiques : une panne ou un dysfonctionnement pourraient causer la perte de vies humaines ou des dommages matériels ou environnementaux importants. Les méthodes formelles visent à offrir des moyens de concevoir et vérifier de tels systèmes afin de garantir qu'ils fonctionneront comme prévu. Au fil du temps, ces systèmes deviennent de plus en plus évolués et complexes, ce qui est source de nouveaux défis pour leur vérification. Il devient nécessaire de développer ces systèmes de manière modulaire afin de pouvoir distribuer la tâche d'implémentation à différentes équipes d'ingénieurs. De plus, il est important de pouvoir réutiliser des éléments certifiés et les adapter pour répondre à de nouveaux besoins. Aussi les méthodes formelles doivent évoluer afin de s'adapter à la conception et à la vérification de ces systèmes modulaires de taille toujours croissante. Nous travaillons sur une approche algébrique pour la conception de systèmes corrects par construction. Elle définit un formalisme pour exprimer des spécifications de haut niveau et permet de les raffiner de manière incrémentale en des spécifications plus concrètes tout en préservant leurs propriétés, jusqu'à ce qu'une implémentation soit atteinte. Elle définit également plusieurs opérations permettant de construire des systèmes complexes à partir de composants plus simples en fusionnant différents points de vue d'un même système ou en composant plusieurs sous-systèmes ensemble, ainsi que de décomposer une spécification complexe afin de réutiliser des composants existants et de simplifier la tâche d'implémentation. Le formalisme de spécification que nous utilisons est basé sur des spécifications modales. Intuitivement, une spécification modale est un automate doté de deux types de transitions permettant d'exprimer des comportements optionnels ou obligatoires. Raffiner une spécification modale revient à décider si les parties optionnelles devraient être supprimées ou rendues obligatoires. Cette thèse contient deux principales contributions théoriques basées sur une extension des spécifications modales appelée " spécifications à ensembles d'acceptation ". La première contribution est l'identification d'une sous-classe des spécifications à ensembles d'acceptation, appelée " spécifications à ensembles d'acceptation convexes ", qui permet de définir des opérations bien plus efficaces tout en gardant un haut niveau d'expressivité. La seconde contribution est la définition d'un nouveau formalisme, appelé " spécifications à ensembles d'acceptation marquées ", qui permet d'exprimer des propriétés d'atteignabilité. Ceci peut, par exemple, être utilisé pour s'assurer qu'un système termine ou exprimer une propriété de vivacité dans un système réactif. Les opérations usuelles sont définies sur ce nouveau formalisme et elles garantissent la préservation des propriétés d'atteignabilité. Cette thèse présente également des résultats d'ordre plus pratique. Tous les résultats théoriques sur les spécifications à ensembles d'acceptation convexes ont été prouvés en utilisant l'assistant de preuves Coq. L'outil MAccS a été développé pour implémenter les formalismes et opérations présentés dans cette thèse. Il permet de les tester aisément sur des exemples, ainsi que d'étudier leur efficacité sur des cas concrets. / Software programs are taking a more and more important place in our lives. Some of these programs, like the control systems of power plants, aircraft, or medical devices for instance, are critical: a failure or malfunction could cause loss of human lives, damages to equipments, or environmental harm. Formal methods aim at offering means to design and verify such systems in order to guarantee that they will work as expected. As time passes, these systems grow in scope and size, yielding new challenges. It becomes necessary to develop these systems in a modular fashion to be able to distribute the implementation task to engineering teams. Moreover, being able to reuse some trustworthy parts of the systems and extend them to answer new needs in functionalities is increasingly required. As a consequence, formal methods also have to evolve in order to accommodate both the design and the verification of these larger, modular systems and thus address their scalability challenge. We promote an algebraic approach for the design of correct-by-construction systems. It defines a formalism to express high-level specifications of systems and allows to incrementally refine these specifications into more concrete ones while preserving their properties, until an implementation is reached. It also defines several operations allowing to assemble complex systems from simpler components, by merging several viewpoints of a specific system or composing several subsystems together, as well as decomposing a complex specification in order to reuse existing components and ease the implementation task. The specification formalism we use is based on modal specifications. In essence, a modal specification is an automaton with two kinds of transitions allowing to express mandatory and optional behaviors. Refining a modal specification amounts to deciding whether some optional parts should be removed or made mandatory. This thesis contains two main theoretical contributions, based on an extension of modal specifications called acceptance specifications. The first contribution is the identification of a subclass of acceptance specifications, called convex acceptance specifications, which allows to define much more efficient operations while maintaining a high level of expressiveness. The second contribution is the definition of a new formalism, called marked acceptance specifications, that allows to express some reachability properties. This could be used for example to ensure that a system is terminating or to express a liveness property for a reactive system. Usual operations are defined on this new formalism and guarantee the preservation of the reachability properties as well as independent implementability. This thesis also describes some more practical results. All the theoretical results on convex acceptance specifications have been proved using the Coq proof assistant. The tool MAccS has been developed to implement the formalisms and operations presented in this thesis. It allows to test them easily on some examples, as well as run some experimentations and benchmarks.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-01-02T14:12:29Z No. of bitstreams: 2 Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-03T09:39:46Z (GMT) No. of bitstreams: 2 Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-01-03T09:39:46Z (GMT). No. of bitstreams: 2 Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-12-01 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / From Carathéodory’s theorem arises the definition of the Carathéodory number for graphs. This number is well-known for monophonic and triangle-path convexities. It is limited for some classes of graphs on P3 and geodesic convexities but is known to be unlimited only on P3-convexity. Driven by open questions in geodesic convexity, in this work we study the Carathéodory number in this convexity. For general graphs and cartesian product, we prove that the Carathéodory number is unlimited. We characterize the Carathéodory number for trees, cographs, for the complementary prisms of cographs and simple graphs Kn, Pn and Cn, for the complement and the complementary prism of the graph KnKn and for the cartesian products PnxPm, KnxKm and PnxKm. / Do Teorema de Carathéodory da geometria surge a definição do número de Carathéodory para grafos. Este número é bem determinado na convexidade monofônica e na convexidade de caminho de triângulos. Ele é limitado para algumas classes de grafos nas convexidades P3 e geodésica, mas só foi provado ser ilimitado na convexidade P3. Motivados pelas questões em aberto na convexidade geodosésica, neste trabalho estudamos o número de Carathéodory nesta convexidade. Para grafos gerais e para produtos cartesianos, provamos que o número de Carathéodory é ilimitado. Determinamos o número de Carathéodory para árvores, cografos, para o prisma complementar de cografos e dos grafos simples Kn, Pn e Cn, para o complemento e prisma complementar do grafo KnKn e para os produtos cartesianos PnxPm, KnxKm e PnxKm.

O problema da Satisfazibilidade Probabilística, PSAT, apesar da sua flexibilidade, torna exponencialmente complexa a modelagem de variáveis estatisticamente independentes. Esta tese busca desenvolver algoritmos e propostas de relaxamento para permitir o tratamento eficiente de independência parcial pelo PSAT. Apresentamos uma aplicação do PSAT ao problema da etiquetagem morfossintática que serve tanto de motivação como de demonstração dos conceitos apresentados. / The Probabilistic Satisfiability Problem, PSAT, despite its flexibility, makes it exponentially complicated to model statistically independent variables. This thesis develops algorithms and relaxation proposals that allow an efficient treatment of partial independence with PSAT. We also present an application of PSAT on the Part-of-speech tagging problem to serve both as motivation and showcase of the presented concepts.

La tomographie consiste à reconstruire un objet nD à partir de projections (n-1)D. Cette discipline soulève plusieurs questions auxquelles la recherche essaie d’apporter des réponses. On s’intéresse dans cette thèse à trois aspects de cette problématique : 1) la reconstruction de l’image 2D à partir de projections dans un cadre rarement étudié qui est celui des sources ponctuelles ; 2) l’unicité de cette reconstruction ; 3) l'estimation d’informations concernant un objet sans passer par l'étape de reconstitution de son image. Afin d’aborder le problème de reconstruction pour la classe des ensembles convexes, nous définissons une nouvelle classe d’ensembles ayant des propriétés de convexité qu’on appelle convexité par quadrants pour des sources ponctuelles. Après une étude de cette nouvelle classe d’ensembles, nous montrons qu’elle présente des liens forts avec la classe des ensembles convexes. Nous proposons alors un algorithme de reconstruction d’ensemblesconvexes par quadrants qui, si l’unicité de la reconstruction est garantie, permet de reconstruire des ensembles convexes en un temps polynomial. Nous montrons que si une conjecture, que nous avons proposée, est vraie, les conditions de l’unicité pour les ensembles convexes par quadrants sont les mêmes que celles pour les ensembles convexes. Concernant le troisième aspect étudié dans cette thèse, nous proposons une méthode qui permet d’estimer, à partir d’une seule projection, la surface d’un ensemble 2D. Concernant l’estimation du périmètre d’un ensemble 2D, en considérant les projections par une deuxième source d’un ensemble convexe, nous obtenons deux bornes inférieures et une borne supérieure pour le périmètre de l’objet projeté. / Tomography is about reconstructing an nD object from its (n-1)D projections. This discipline addresses many questions to which research tries to provide answers. In this work, we are interested to three aspects: 1) the 2D image reconstruction from projections in a rarely studies framework that is the point sources; 2) the uniqueness of this reconstruction; 3) estimating information about an object without going through the step of reconstructing its image. To approach the problem of tomographic reconstruction for the class of convex sets, we define a new class of sets having properties of convexity called quadrant convexity for point sources. After a study of this new class of sets, we show that it presents strong links with the class of convex sets. Wepropose a reconstruction algorithm for quadrant-convex sets that, if the uniqueness of the reconstruction is guaranteed, allows the reconstruction of convex sets in polynomial time. We also show that if a conjecture we have proposed is true the conditions of uniqueness for quadrant-convex sets are the same as those for convex sets. Regarding the third aspect studied in this thesis, we focus on two quantitative properties that are the surface and the perimeter. We propose a method to estimate, from only one projection, the surface of a 2D set. We obtain two lower bounds and an upper bound for the perimeter of a projected convexobject by considering the projections from a second point source.

Si µ est une mesure de probabilité à support compact dans uns espace vectoriel ou affine de dimension finie, le barycentre (ou centre de gravité) de µ est un point bien défini de l’espace. Mais des difficultés surgissent lorsque l’espace est remplacé par une variété riemannienne M ; dans ce cas, même en se restreignant aux variétés convexes (c’est-à-dire deux dont points quelconques sont toujours joints par une géodésique et une seule) et aux mesures à support fini, il est en général impossible d'assigner à chaque probabilité un barycentre de façon que, d'une part,pour tous λϵ [0; 1] et x et y dans M, le barycentre de µ = (1- λ ) δˣ+ λ δy soit toujours le point γ(λ), sur la géodésique telle que γ (0) = x et γ (1) = y, et que, d'autre part, soit préservée la propriété d'associativité (pour faire une moyenne, on peut commencer par faire des moyennes partielles). Dés que la mesure µ est portée par au moins trois points non tous situées sur une même géodésique, il y a de multiples façons différentes de définir son barycentre comme barycentre de barycentres partiels de barycentres partiels etc., chaque opération élémentaire ne faisant intervenir que deux points. On obtient ainsi tout un ensemble de points de M, les barycentres itérés de µ . Pour des probabilités plus générales, on appelle barycentre convexe de µ l'ensemble b(µ) des points x de M qui sont limites d'une suite (xn), ou chaque xn est un barycentre itéré d'une probabilité µn à support fini, les mesures µn tendant vers µ. / If μ is a probability measure carried on a small in a finite-dimension vectorial or affine space, the μ- barycenter (center of gravity) is a well-defined point in space. Nevertheless, difficulties arise when space is changed by Riemannian manifold M. In this case, even if we limit to convex manifolds (i.e : when any two points are joined by one geodesic and just one) and to finite-support measures, it’s, in general impossible to attribute a barycenter to each probability, in such a way, on one hand, whetever λϵ [0; 1] and x and y in M, the barycenter of µ = (1- λ ) δˣ+ λ δy will be always the point γ(λ) of the geodesic such that γ (0) = x et γ (1) =y, and on another hand, the associative property will be maintained (to make a mean, we can begin by doing partial means). Once the measure μ is carried by at least three points which are not all localed on the same geodesic, there are different manners to define its barycenter as one of partial barycenters of partial barycenters and so on, in which each elementary operation includes only two points. Thus, we get a whole set of set of points of M, the iterated barycenters of μ. For more general probabilities μ, we call convex barycenter of μ, the set b(μ) of points x of M which are limit of sequence (xn), in which each xn is an iterated barycenter of a finite support probability μn, the measure μn tending to μ.

Ce travail de thèse porte principalement sur deux problématiques différentes mais qui ont pour point commun, la contribution à la modélisation et à la gestion du risque en actuariat. Dans le premier thème de recherche abordé dans cette thèse, on s'intéresse à la modélisation de la dépendance en assurance et en particulier, on propose une extension des modèles à facteurs communs qui sont utilisés en assurance. Dans le deuxième thème de recherche, on considère les distributions discrètes décroissantes et on s'intéresse à l'étude de l'effet de l'ajout de la contrainte de convexité sur les extrema convexes. Des applications en liaison avec la théorie de la ruine motivent notre intérêt pour ce sujet. Dans la première partie de la thèse, on considère un modèle de risque en temps discret dans lequel les variables aléatoires sont dépendantes mais conditionnellement indépendantes par rapport à un facteur commun. Dans ce cadre de dépendance on introduit un nouveau concept pour la modélisation de la dépendance temporelle entre les risques d'un portefeuille d'assurance. En effet, notre modélisation inclut des processus de mémoire non bornée. Plus précisément, le conditionnement se fait par rapport à un vecteur aléatoire de longueur variable au cours du temps. Sous des conditions de mélange du facteur et d'une structure de mélange conditionnel, nous avons obtenu des propriétés de mélanges pour les processus non conditionnels. Avec ces résultats on peut obtenir des propriétés asymptotiques intéressantes. On note que dans notre étude asymptotique c'est plutôt le temps qui tend vers l'infini que le nombre de risques. On donne des résultats asymptotiques pour le processus agrégé, ce qui permet de donner une approximation du risque d'une compagnie d'assurance lorsque le temps tend vers l'infini. La deuxième partie de la thèse porte sur l'effet de la contrainte de convexité sur les extrema convexes dans la classe des distributions discrètes dont les fonctions de masse de probabilité (f.m.p.) sont décroissantes sur un support fini. Les extrema convexes dans cette classe de distributions sont bien connus. Notre but est de souligner comment les contraintes de forme supplémentaires de type convexité modifient ces extrema. Deux cas sont considérés : la f.m.p. est globalement convexe sur N et la f.m.p. est convexe seulement à partir d'un point positif donné. Les extrema convexes correspondants sont calculés en utilisant de simples propriétés de croisement entre deux distributions. Plusieurs illustrations en théorie de la ruine sont présentées / In this thesis we focus on two different problems which have as common point the contribution to the modeling and to the risk management in insurance. In the first research theme, we are interested by the modeling of the dependence in insurance. In particular we propose an extension to model with common factor. In the second research theme we consider the class of nonincreasing discrete distributions and we are interested in studying the effect of additional constraint of convexity on the convex extrema. Some applications in ruin theory motivate our interest to this subject. The first part of this thesis is concerned with factor models for the modeling of the dependency in insurance. An interesting property of these models is that the random variables are conditionally independent with respect to a factor. We propose a new model in which the conditioning is with respect to the entire memory of the factor. In this case we give some mixing properties of risk process under conditions related to the mixing properties of the factor process and to the conditional mixing risk process. The law of the sum of random variables has a great interest in actuarial science. Therefore we give some conditions under which the law of the aggregated process converges to a normal distribution. In the second part of the thesis we consider the class of discrete distributions whose probability mass functions (p.m.f.) are nonincreasing on a finite support. Convex extrema in that class of distributions are well-known. Our purpose is to point out how additional shape constraints of convexity type modify these extrema. Two cases are considered : the p.m.f. is globally convex on N or it is convex only from a given positive point. The corresponding convex extrema are derived by using a simple crossing property between two distributions. Several applications to some ruin problems are presented for illustration

This Master’s thesis deals with the application of cooperative game theory for solving the problems of Cournot's oligopolies. The knowledge of oligopoly theory and game theory has been elaborated to build a model describing the behavior of companies at a market that meets the preconditions of Cournot's oligopoly. The definition of cooperative game is based on the -characteristic function, which takes into account, compared to classical methods, that companies which are not in the coalition are pursuing their own profits, not suppressing coalition positions. The properties of the resulting cooperative games are examined in detail, focusing on monotony and convexity. Several theorems about these properties have been derived and their economic interpretations are given. Also, the question of calculation of the -characteristic function using the best-reply dynamics algorithm is being solved, and its convergence for a given type of games is justified. The model is applied to data from the oil market, which is further characterized by the results of the cooperative game.

La programmation bi-niveau désigne une classe de problèmes d'optimisation emboîtés impliquant deux joueurs.Un joueur meneur annonce une décision à un joueur suiveur qui détermine sa réponse parmi l'ensemble des solutions d'un problème d'optimisation dont les données dépendent de la décision du meneur (problème de niveau bas).La décision optimale du meneur est la solution d'un autre problème d'optimisation dont les données dépendent de la réponse du suiveur (problème de niveau haut).Lorsque la réponse du suiveur n'est pas unique, on distingue les problèmes bi-niveaux optimistes et pessimistes,suivant que la réponse du suiveur soit respectivement la meilleure ou la pire possible pour le meneur.Les problèmes bi-niveaux sont souvent utilisés pour modéliser des problèmes de tarification. Dans les applications étudiées ici, le meneur est un vendeur qui fixe un prix, et le suiveur modélise le comportement d'un grand nombre de clients qui déterminent leur consommation en fonction de ce prix. Le problème de niveau bas est donc de grande dimension.Cependant, la plupart des problèmes bi-niveaux sont NP-difficiles, et en pratique, il n'existe pas de méthodes générales pour résoudre efficacement les problèmes bi-niveaux de grande dimension.Nous introduisons ici une nouvelle approche pour aborder la programmation bi-niveau.Nous supposons que le problème de niveau bas est un programme linéaire, en variables continues ou discrètes,dont la fonction de coût est déterminée par la décision du meneur.Ainsi, la réponse du suiveur correspond aux cellules d'un complexe polyédral particulier,associé à une hypersurface tropicale.Cette interprétation est motivée par des applications récentes de la géométrie tropicale à la modélisation du comportement d'agents économiques.Nous utilisons la dualité entre ce complexe polyédral et une subdivision régulière d'un polytope de Newton associé pour introduire une méthode dedécomposition qui résout une série de sous-problèmes associés aux différentes cellules du complexe.En utilisant des résultats portant sur la combinatoire des subdivisions, nous montrons que cette décomposition mène à un algorithme permettant de résoudre une grande classe de problèmes bi-niveaux en temps polynomial en la dimension du problème de niveau bas lorsque la dimension du problème de niveau haut est fixée.Nous identifions ensuite des structures spéciales de problèmes bi-niveaux pour lesquelles la borne de complexité peut être améliorée.C'est en particulier le cas lorsque la fonction coût du meneur ne dépend que de la réponse du suiveur.Ainsi, nous montrons que la version optimiste du problème bi-niveau peut être résolue en temps polynomial, notammentpour des instancesdans lesquelles les données satisfont certaines propriétés de convexité discrète.Nous montrons également que les solutions de tels problèmes sont des limites d'équilibres compétitifs.Dans la seconde partie de la thèse, nous appliquons cette approche à un problème d'incitation tarifaire dans les réseaux mobiles de télécommunication.Les opérateurs de données mobiles souhaitent utiliser des schémas de tarification pour encourager les différents utilisateurs à décaler leur consommation de données mobiles dans le temps, et par conséquent dans l'espace (à cause de leur mobilité), afin de limiter les pics de congestion.Nous modélisons cela par un problème bi-niveau de grande taille.Nous montrons qu'un cas simplifié peut être résolu en temps polynomial en utilisant la décomposition précédente,ainsi que des résultats de convexité discrète et de théorie des graphes.Nous utilisons ces idées pour développer une heuristique s'appliquant au cas général.Nous implémentons et validons cette méthode sur des données réelles fournies par Orange. / Bilevel programming deals with nested optimization problems involving two players. A leader annouces a decision to a follower, who responds by selecting a solution of an optimization problem whose data depend on this decision (low level problem). The optimal decision of the leader is the solution of another optimization problem whose data depend on the follower's response (high level problem). When the follower's response is not unique, one distinguishes between optimistic and pessimistic bilevel problems, in which the leader takes into account the best or worst possible response of the follower.Bilevel problems are often used to model pricing problems.We are interested in applications in which the leader is a seller who announces a price, and the follower models the behavior of a large number of customers who determine their consumptions depending on this price.Hence, the dimension of the low-level is large. However, most bilevel problems are NP-hard, and in practice, there is no general method to solve efficiently large-scale bilevel problems.In this thesis, we introduce a new approach to tackle bilevel programming. We assume that the low level problem is a linear program, in continuous or discrete variables, whose cost function is determined by the leader. Then, the follower responses correspond to the cells of a special polyhedral complex, associated to a tropical hypersurface. This is motivated by recent applications of tropical geometry to model the behavior of economic agents.We use the duality between this polyhedral complex and a regular subdivision of an associated Newton polytope to introduce a decomposition method, in which one solves a series of subproblems associated to the different cells of the complex. Using results about the combinatorics of subdivisions, we show thatthis leads to an algorithm to solve a wide class of bilevel problemsin a time that is polynomial in the dimension of the low-level problem when the dimension of the high-level problem is fixed.Then, we identify special structures of bilevel problems forwhich this complexity bound can be improved.This is the case when the leader's cost function depends only on the follower's response. Then, we showthe optimistic bilevel problem can be solved in polynomial time.This applies in particular to high dimensional instances in which the datasatisfy certain discrete convexity properties. We also show that the solutions of such bilevel problems are limits of competitive equilibria.In the second part of this thesis, we apply this approach to a price incentive problem in mobile telecommunication networks.The aim for Internet service providers is to use pricing schemes to encourage the different users to shift their data consumption in time(and so, also in space owing to their mobility),in order to reduce the congestion peaks.This can be modeled by a large-scale bilevel problem.We show that a simplified case can be solved in polynomial time by applying the previous decomposition approach together with graph theory and discrete convexity results. We use these ideas to develop an heuristic method which applies to the general case. We implemented and validated this method on real data provided by Orange.

Concrete domains have been introduced in Description Logics (DLs) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. To retain decidability when integrating a concrete domain into a decidable DL, the domain must satisfy quite strong restrictions. In previous work, we have analyzed the most prominent such condition, called w-admissibility, from an algebraic point of view. This provided us with useful algebraic tools for proving w-admissibility, which allowed us to find new examples for concrete domains whose integration leaves the prototypical expressive DL ALC decidable. When integrating concrete domains into lightweight DLs of the EL family, achieving decidability is not enough. One wants reasoning in the resulting DL to be tractable. This can be achieved by using so-called p-admissible concrete domains and restricting the interaction between the DL and the concrete domain. In the present paper, we investigate p-admissibility from an algebraic point of view. Again, this yields strong algebraic tools for demonstrating p-admissibility. In particular, we obtain an expressive numerical padmissible concrete domain based on the rational numbers. Although w-admissibility and p-admissibility are orthogonal conditions that are almost exclusive, our algebraic characterizations of these two properties allow us to locate an infinite class of p-admissible concrete domains whose integration into ALC yields decidable DLs.