Cette thèse apporte une généralisation du principe de recommandation des systèmes de recommandation. Au lieu de considérer une recommandation comme un item, elle est considérée comme une combinaison constituée de plusieurs items suivant un pattern donné. Une recommandation d'un seul item est alors un cas particulier de ce type de recommandation. L’architecture de système de recommandation proposé se base sur une architecture dérivée des travaux en systèmes hypermédia adaptatifs. Trois couches sont définies : une couche sémantique, une couche utilisateur et une couche intelligence. La couche sémantique est constituée de deux sous-couches, une sous-couche modélisant le contenu suivant la connaissance générale du domaine et une sous-couche modélisant le contenu suivant la connaissance spécifique à l'application, plus précisément spécifique aux possibles contraintes des utilisateurs dans l'application. Cette deuxième partie permet de prendre en compte le savoir-faire du fournisseur de l’offre dans les propositions du système de recommandation. La couche utilisateur modélise l’utilisateur au sein du système de recommandation et la couche intelligence contient le processus de recommandation. Nous proposons de décomposer ce dernier en deux sous-processus principaux, un processus dit de projection des individus du domaine sur les profils utilisateurs et un processus de recherche combinatoire. Le premier apporte une pondération, appelée note dans la plupart des systèmes de recommandation, donnant les intérêts probables des utilisateurs pour les différents items. Le processus de recherche combinatoire recherche parmi la multitude de combinaisons possibles, une solution convenable (optimale si possible) à proposer à l'utilisateur. Cette architecture de système de recommandation combinatoire est appliquée au domaine touristique pour l'entreprise Côte-d'Or Tourisme impliquée dans le contrat de recherche. Le but de cette application est de proposer à l'utilisateur un ensemble d'offres touristiques sous forme de séjour. Ce problème touristique amène à la définition formelle d'un problème d'optimisation combinatoire qui est une variante d'un sous-problème du problème de sac à dos. Pour résoudre ce genre de problème, il est nécessaire d'utiliser une métaheuristique afin de tendre vers une bonne solution en un temps raisonnable. Nous présentons un algorithme basé sur le recuit simulé et un algorithme multi-objectif pour la résolution de ce problème. L’instanciation de chaque couche de l’architecture pour le système touristique est décrite en détail. Enfin, cette thèse présente une application mobile faisant office d’interface utilisateur avec le système de recommandation touristique et elle présente les développements techniques nécessaires à ce projet, étant donné son contexte industriel. / This thesis gives a generalization of the recommendation principle of recommender systems. Instead of considering a recommendation as an item, it is considered as a combination of several items following a given pattern. A recommendation of a unique item is then a particular case of this type of recommendation. The proposed recommender system framework is based on an architecture derived from work in adaptive hypermedia systems. Three layers are defined: a semantic layer, a user layer and an intelligence layer. The semantic layer consists of two sub-layers, a sub-layer modeling the content according to the general knowledge of the domain and a sub-layer modeling the content according to the specific knowledge of the application. This second sub-layer allows taking into account the expertise of the offer’s supplier for the proposals of the recommender system. The user layer models the user into the recommender system and the intelligence layer contains recommendation process. We propose to decompose the adaptation into two main processes, a process called projection of domain’s individuals on user profiles and a combinatorial research process. The first brings a weight, called the note in most recommender systems, giving probable users’ interests on the different items. The combinatorial research process searches among the many possible combinations a suitable solution (optimal if possible) to propose to the user. This framework of combinatory recommender systems is applied to the domain of tourism for the company Côte-d'Or Tourisme implied in the research contract. The purpose of this application is to offer the user a set of tourism offers in the form of journey. This tourism problem leads to the formal definition of a combinatory optimization problem which is a variant of the knapsack problem. To resolve this kind of problem, it is necessary to use a metaheuristic to tend toward a good solution in a reasonable time. We present an algorithm based on simulated annealing and a multi-objective algorithm to solve this problem. The instantiation of each layer of the framework for the tourism system is described in detail. Finally, this thesis presents a mobile application serving as a user with the tourism recommender system and it presents the technical developments for this project.

Cette thèse, s’intéresse aux pratiques de calcul au sein des PME, aux facteurs pouvant influencer l’utilisation des pratiques de calcul des coûts les plus développées ainsi qu’à la contribution opérationnelle et stratégique de l’utilisation de ces pratiques au sein des PME tout en faisant une comparaison avec les caractéristiques des entreprises de taille intermédiaire. Nous avons fait recours à la théorie de contingence pour fonder notre travail de recherche. Nous avons contacté 8 entreprises par des entretiens en face à face et 70 entreprises par un questionnaire. Nous avons trouvé que les caractéristiques des PME en matière de calcul des coûts sont différentes. Cette différenciation peut être expliquée par trois facteurs: la taille de l’organisation, la diversité des produits et la structure décentralisée de l’entreprise. Également, nous avons trouvé que l’utilité opérationnelle de l’utilisation des instruments de calcul des coûts est perçue comme étant plus élevée par les entreprises qui utilisent les nouvelles méthodes que par les entreprises qui ne les utilisent pas. Cependant, la perception de l’utilité stratégique ne diffère pas entre les utilisateurs et les non-utilisateurs des nouvelles méthodes. / This thesis is interested in accounting practices within SMEs, factors that are able to influence the use of accounting practices, the most developed costs as well as the operational and strategic contribution of these practices within the SMEs while making a comparison with the characteristics of midsize companies. We resorted to the contingency theory to set up our research. We contacted eight companies through several face- to -face interviews, and seventy companies through questioning. We found out that the SMEs characteristics as regards accounting of costs are different. This difference can be explained by three factors: the organization’s size, the product's diversity, and the decentralized structure of the company. Equally, we found out that the operational utility of instruments of accounting costs is looked as the most mannered one by companies that do not use them. However, the perception of the strategic utility do not differ between users and non-users of new methods

La chaine d’approvisionnement énergétique a fortement évolué aux cours des 20 dernières années. La libéralisation des marchés de l’électricité et les nouvelles technologies ont fortement influencé la manière d’envisager la production et la transmission d’électricité. Les modèles mathématiques classiques utilisés dans les problèmes lié à l’énergie ont besoin d’être revus pour intégrer les contraintes pratiques modernes.Un problème classique pour un Compagnie Génératrice (CG) est le problème de Unit Commitment (UC) qui consiste à établir un plan de production pour une demande en électricité connue. Lorsque ce problème fut considéré, le prix de l’électricité et la demande étaient relativement simple à estimer comme une seule CG nationale avait le monopole du marché. Ce problème a été étudié de manière extensive en utilisant de la Programmation Mathématique (PM). Aujourd’hui, le prix de l’électricité est relativement volatile à cause de l’introduction de marchés dérégulés et la demande du marché est répartie entre plusieurs CGs en compétition sur divers marchés. Une CG ne peut se limiter à considérer un problème de UC seul pour envisager sa production. Il y a un besoin d’intégrer les incertitudes liées au marché de l’électricité et aux quantités à produire aux modèles utilisés pour qu’une CG puisse établir un plan de production rentable.La technologie a aussi permis d’envisager de nouveaux concept tel que les Micro-Grilles (MGs). Une MG est composée d’un ensemble de consommateurs reliés à travers un réseau de transmission, possédant des générateurs d’électricité et optimisant leur consommation interne. Ce concept est possible grâce à l’utilisation croissante d’énergies renouvelables locales ainsi que l’utilisant croissante d’appareils interconnectés. Cependant, étant donné que les énergies renouvelables ont un faible rendement, sont intermittentes et que les appareils de stockage d’énergie sont encore peu efficaces, les MGs ne peuvent pas envisager d’être pleinement autonome en électricité. Il y a donc une nécessité d’avoir un fournisseur d’électricité externe pour avoir suffisamment d’électricité disponible à tout moment. Une CG jouant le rôle de fournisseur auprès d’une MG fait face énormément d’incertitude concernant la demande à cause de la gestion interne de la MG sur laquelle elle n’a pas de contrôle.Dans cette thèse, des problèmes d’optimisation intégrant de nouvelles contraintes modernes liés à l’approvisionnement énergétique sont étudiés via la PM. Plusieurs problèmes considèrant des interactions entre plusieurs acteurs sont modélisés via des formulations bi-niveau. Nous illustrons comment les difficultés liées aux contraintes modernes peuvent être exploitées pour obtenir des propriétés permettant de reformuler les problèmes étudiés en formulation linéaire en nombre entiers. Des heuristiques performantes sont obtenus à partir des formulations exactes dont certaines sont applicables à des problèmes plus généraux. Une analyse extensive de la performance des méthodes de résolution ainsi que de l’influence des contraintes modernes sont présentées dans diverses expériences numériques. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Dans le contexte de l’augmentation de la part de la production énergétique provenant de sources renouvelables imprévisibles, les prix de l’électricité sont plus volatiles que jamais. Cette volatilité rend la prévision des prix plus difficile mais en même temps de plus grande valeur. Dans cette recherche, une analyse comparative de 8 modèles de prévision est effectuée sur la tâche de prédire les prix de gros de l’électricité du lendemain en France, en Allemagne, en Belgique et aux Pays-Bas. La méthodologie utilisée pour produire les prévisions est expliquée en détail. Les différences de précision des prévisions entre les modèles sont testées pour leur signification statistique. La méthode de gradient boosting a produit les prévisions les plus précises, suivi de près par une méthode d’ensemble. / In the context of the increase in the fraction of power generation coming from unpredictable renewable sources, electricity prices are as volatile as ever. This volatility makes forecasting future prices more difficult yet more valuable. In this research, a benchmark of 8 forecasting models is conducted on the task of predicting day-ahead wholesale electricity prices in France, Germany, Belgium and the Netherlands. The methodology used to produce the forecasts is explained in detail. The differences in forecast accuracy between the models are tested for statistical significance. Gradient boosting produced the most accurate forecasts, closely followed by an ensemble method.

Chaque année en Europe, quelques 70.000 nouveaux patients requièrent un traitement permanent dans le cadre d'une insuffisance rénale terminale. Dans le même temps, on réalise environ 20.000 greffes, laissant quantité de patients en dialyse. Le taux de survie en dialyse est médiocre (2/3 à 3/4 moindre que chez les sujets non dialysés des mêmes âges) ce qui rend le problème de la disponibilité des greffons parfaitement criant. La pénurie de greffons est directement liée à leur survie limitée: 10 ans en valeur médiane et en l'absence de censure pour la mort des patients, ou bien 15 ans si l'on se limite à regarder les pertes de greffes liées à des causes intrinsèques. Plus de 60% des greffons sont perdus des suites de lésions de rejet chronique. Dans ce contexte, nous avons choisi de nous intéresser à de très rares patients, découverts fortuitement, qui en dépit de l'arrêt de leurs immunosuppresseurs pour diverses raisons, maintiennent pendant une durée prolongée d'au moins 1 an, une bonne fonction de leur greffon. Ces patients, tout en étant bien portants, semblent être devenus sélectivement incapables de monter une réaction inflammatoire, à tout le moins destructrice, à l'encontre de leur greffon. On dit qu'ils sont "opérationnellement tolérants". En pratique, ils disposent d'un rein allogénique qu'ils ne rejettent pas mais sans avoir à subir les conséquences néfastes et redoutables des immunosuppresseurs (infections, cancers, diabète, hypertension artérielle, ). Comprendre et maîtriser la tolérance opérationnelle ouvrirait la voie à des transplantations plus durables et plus sûres. Plusieurs études transcriptomiques, mécanistiques et épigénétiques laissent penser que la tolérance opérationnelle repose sur l'expansion de populations cellulaires régulatrices au sein des répertoires alloréactifs, aux dépends des cellules effectrices. Ces équilibresfins seraient maintenus grâce à une série de modifications épigénétiques (microARN, méthylations) assurant une stabilité relative au phénotype. Malgré notre meilleure compréhension des mécanismes responsables de l'homéostasie de la tolérance, ses mécanismes causaux restent à ce jour inconnus.Nous avons émis l'hypothèse que la tolérance requerrait une prédisposition génétique pour pouvoir s'installer, concrètement: que les patients tolérants se distinguent du reste de la population par un excès de variants à haute pénétrance localisés dans les exons de gènes jouant un rôle critique dans le développement de la dite tolérance.Pour valider cette thèse, nous avons, dans un premier temps:- contribué à montrer, au travers de la première étude pangénomique d'association ("GWAS") validée sur le rejet aigu d'allogreffe rénale que le génome des receveurs influençait les réponses alloimmunes, hors du système HLA.- réuni la plus grande cohorte de patients tolérants sur le territoire européen à ce jour composée de 22 patients de la biocollection l'université de Nantes et de 18 patients identifiés prospectivement dans le cadre d'une étude dédiée; TOMOGRAM,- montré que la tolérance était associée à une survie prolongée des greffons,- montré qu'il s'agissait d'une découverte rare, identifiée par les cliniciens chez seulement 0.03% de leurs patients greffés et sans condition prédisposante patente.Dans un second temps, nous avons- séquencé les exomes de 40 patients tolérants et les avons comparés à ceux de 209 contrôles in-house,- filtré nos données selon notre hypothèse de travail et circonscrit un ensemble de variants exoniques moyennement à hautement pathogènes (au total 84.643, répartis dans 16.343 gènes),- comparé les distributions de variants (par gène; par variant) chez les cas et chez les contrôles, à l'aide du test aSKAT-O; un test basé sur une analyse de la variance et ajusté pour les petits échantillons.Nos résultats immédiats ont été soumis à 3 contrôles: une correction pour les hypothèses multiples (FDR 0.05); des interventions pour repérer d'éventuelles stratifications (notamment d'après une analyse en composantes principales ou PCA) et enfin; l'examen soigneux des variants retenus dans les fichiers post-alignement (BAM).Au terme de ce processus, nous n'avons pas pu identifier de variant ou de gène ségréguant avec la tolérance. Nous concluons que la prédisposition à la tolérance repose peu vraisemblablement sur une hérédité monogénique simple et homogène ("mendélienne"). D'autres données, en ce compris nos propres travaux sur les déterminants génétiques du rejet aigu de greffe, nous encouragent à rechercher des causes génétiques plus complexes. De nouvelles études d'association tirant parti du séquençage génome-entier et exploitant des cohortes plus larges sont requises. / Doctorat en Sciences médicales (Médecine) / info:eu-repo/semantics/nonPublished

Ce travail présente une architecture logicielle concrète dédiée aux besoins et caractéristiques des systèmes d'Intelligence Ambiante (AmI). Le modèle comportemental proposé, appelé Higher-order Agent (HoA), capture simultanément l'évolution de l'état mental de l'agent ainsi que l'état de son plan d'actions. Les expressions du plan sont écrites et composées en utilisant un langage algébrique formel, nommé AgLOTOS. Les plans sont construits automatiquement et à la volée, comme un système de processus concurrents, déduits des intentions de l'agent et de ses préférences d'exécution. Basé sur une sémantique de plans et d'actions concurrentes, un service de guidance est aussi proposé afin d'assister l'agent dans le choix de ses prochaines exécutions. Cette guidance permet d'améliorer la satisfaction des intentions de l'agent au regard des plans concurrents possibles et en fonction du contexte actuel de l'agent. La "localité" et le "temps" étant considérés comme des informations contextuelles clés dans l'activité de l'agent, nous les prenons en compte au travers de deux fonctions utilitaires originales conçues à partir des expériences des exécutions d'action et pouvant être combinées suivant les préférences stratégiques de l'agent. La structure compositionnelle des expressions AgLOTOS est mise à profit pour permettre des révisions ciblées du plan de l'agent, Les révisions des sous-plans sont donc réalisées automatiquement en fonction des mises à jour apportées aux intentions, tout en maintenant la consistance du comportement de l'agent. Un cas d'étude est développé afin de montrer comment l'agent peut agir, même s'il subit des changements inattendus de son contexte, en fonction de ses expériences passées qui révèlent certains cas de d'échecs. / This work presents a concrete software architecture dedicated to ambient intelligence (AmI) features and requirements. The proposed behavioral model, called Higher-order Agent (HoA) captures the evolution of the mental representation of the agent and the one of its plan simultaneously. Plan expressions are written and composed using a formal algebraic language, namely AgLOTOS, so that plans are built automatically and on the fly, as a system of concurrent processes. Due to the compositional structure of AgLOTOS expressions, the updates of sub-plans are realized automatically accordingly to the revising of intentions, hence maintaining the consistency of the agent. Based on a specific semantics, a guidance service is also proposed to assist the agent in its execution. This guidance allows to improve the satisfaction of the agent's intentions with respect to the possible concurrent plans and the current context of the agent. Adopting the idea that "location" and "time" are key stones information in the activity of the agent, we show how to enforce guidance by ordering the different possible plans. As a major contribution, we demonstrate two original utility functions that are designed from the past-experiences of the action executions, and that can be combined accordingly to the current balance policy of the agent. A use case scenario is developed to show how the agent can act, even if it suffers from unexpected changes of contexts, it does not have many experiences and whose past experiences reveals some failure cases.

Ce travail de thèse de doctorat est dédié à l'étude d'un problème de placement de tâches dans le domaine de la compilation d'applications pour des architectures massivement parallèles. Ce problème vient en réponse à certains besoins industriels tels que l'économie d'énergie, la demande de performances pour les applications de type flots de données synchrones. Ce problème de placement doit être résolu dans le respect de trois critères: les algorithmes doivent être capable de traiter des applications de tailles variables, ils doivent répondre aux contraintes de capacités des processeurs et prendre en compte la topologie des architectures cibles. Dans cette thèse, les tâches sont organisées en réseaux de communication, modélisés sous forme de graphes. Pour évaluer la qualité des solutions produites par les algorithmes, les placements obtenus sont comparés avec un placement aléatoire. Cette comparaison sert de métrique d'évaluation des placements des différentes méthodes proposées. Afin de résoudre à ce problème, deux algorithmes de placement de réseaux de tâches de grande taille sur des architectures clusterisées de processeurs de type many-coeurs ont été développés. Ils s'appliquent dans des cas où les poids des tâches et des arêtes sont unitaires. Le premier algorithme, nommé Task-wise Placement, place les tâches une par une en se servant d'une notion d'affinité entre les tâches. Le second, intitulé Subgraph-wise Placement, rassemble les tâches en groupes puis place les groupes de tâches sur les processeurs en se servant d'une relation d'affinité entre les groupes et les tâches déjà affectées. Ces algorithmes ont été testés sur des graphes, représentants des applications, possédant des topologies de types grilles ou de réseaux de portes logiques. Les résultats des placements sont comparés avec un algorithme de placement, présent dans la littérature qui place des graphes de tailles modérée et ce à l'aide de la métrique définie précédemment. Les cas d'application des algorithmes de placement sont ensuite orientés vers des graphes dans lesquels les poids des tâches et des arêtes sont variables similairement aux valeurs qu'on peut retrouver dans des cas industriels. Une heuristique de construction progressive basée sur la théorie des jeux a été développée. Cet algorithme, nommé Regret Based Approach, place les tâches une par une. Le coût de placement de chaque tâche en fonction des autres tâches déjà placées est calculée. La phase de sélection de la tâche se base sur une notion de regret présente dans la théorie des jeux. La tâche qu'on regrettera le plus de ne pas avoir placée est déterminée et placée en priorité. Afin de vérifier la robustesse de l'algorithme, différents types de graphes de tâches (grilles, logic gate networks, series-parallèles, aléatoires, matrices creuses) de tailles variables ont été générés. Les poids des tâches et des arêtes ont été générés aléatoirement en utilisant une loi bimodale paramétrée de manière à obtenir des valeurs similaires à celles des applications industrielles. Les résultats de l'algorithme ont également été comparés avec l'algorithme Task-Wise Placement, qui a été spécialement adapté pour les valeurs non unitaires. Les résultats sont également évalués en utilisant la métrique de placement aléatoire. / This Ph.D thesis is devoted to the study of the mapping problem related to massively parallel embedded architectures. This problem arises from industrial needs like energy savings, performance demands for synchronous dataflow applications. This problem has to be solved considering three criteria: heuristics should be able to deal with applications with various sizes, they must meet the constraints of capacities of processors and they have to take into account the target architecture topologies. In this thesis, tasks are organized in communication networks, modeled as graphs. In order to determine a way of evaluating the efficiency of the developed heuristics, mappings, obtained by the heuristics, are compared to a random mapping. This comparison is used as an evaluation metric throughout this thesis. The existence of this metric is motivated by the fact that no comparative heuristics can be found in the literature at the time of writing of this thesis. In order to address this problem, two heuristics are proposed. They are able to solve a dataflow process network mapping problem, where a network of communicating tasks is placed into a set of processors with limited resource capacities, while minimizing the overall communication bandwidth between processors. They are applied on task graphs where weights of tasks and edges are unitary set. The first heuristic, denoted as Task-wise Placement, places tasks one after another using a notion of task affinities. The second algorithm, named Subgraph-wise Placement, gathers tasks in small groups then place the different groups on processors using a notion of affinities between groups and processors. These algorithms are tested on tasks graphs with grid or logic gates network topologies. Obtained results are then compared to an algorithm present in the literature. This algorithm maps task graphs with moderated size on massively parallel architectures. In addition, the random based mapping metric is used in order to evaluate results of both heuristics. Then, in a will to address problems that can be found in industrial cases, application cases are widen to tasks graphs with tasks and edges weights values similar to those that can be found in the industry. A progressive construction heuristic named Regret Based Approach, based on game theory, is proposed. This heuristic maps tasks one after another. The costs of mapping tasks according to already mapped tasks are computed. The process of task selection is based on a notion of regret, present in game theory. The task with the highest value of regret for not placing it, is pointed out and is placed in priority. In order to check the strength of the algorithm, many types of task graphs (grids, logic gates networks, series-parallel, random, sparse matrices) with various size are generated. Tasks and edges weights are randomly chosen using a bimodal law parameterized in order to have similar values than industrial applications. Obtained results are compared to the Task Wise placement, especially adapted for non-unitary values. Moreover, results are evaluated using the metric defined above.

L’objectif de cette thèse est de trois ordres. Premièrement, elle vise à examiner la responsabilité municipale à travers le prisme d’une analyse institutionnelle afin de démontrer que les municipalités ne possèdent aucune protection constitutionnelle en vertu de la séparation des pouvoirs et qu’elles peuvent uniquement bénéficier d’une immunité liée à leurs fonctions législatives déléguées, ce qui implique l’exclusion de toute immunité institutionnelle. Deuxièmement, cette thèse vise à analyser l’évolution jurisprudentielle de l’immunité afin de démontrer que la notion de politique publique (policy) qui fonde l’immunité n’a pas de contenu substantiel inhérent et qu’il faut ainsi privilégier une définition formelle reposant sur un processus décisionnel. Troisièmement, cette thèse proposera une nouvelle conception de l’immunité, soit celle "d’immunité proportionnelle variable". Ainsi, contrairement à l’immunité traditionnelle dont l’application est uniforme, cette nouvelle conception permettrait de lever partiellement l’immunité à l’égard de certaines personnes vulnérables et de la faire varier proportionnellement en fonction des effets préjudiciables que pourrait avoir une décision politique sur les droits de ces personnes vulnérables. / This thesis has three objectives. The first one is to examine the liability of municipalities trough an institutional analysis in order to demonstrate that municipalities have no constitutional protection under the separation of powers but rather only enjoy an immunity related to their delegated legislative functions, which implies that they do not have any institutional immunity. The second objective of this thesis is to analyze the evolution of the case law regarding immunity in order to demonstrate that the notion of policy, which is the basis for immunity, has no inherent substantive content. Therefore, we believe that a formal definition of immunity based on a decisional process should be favored. Finally, this thesis will suggest a new concept of immunity that we call "variable proportional immunity". Thus, unlike traditional immunity, which is applied uniformly, pursuant to this new concept, immunity could be partially waived in favour of certain vulnerable people proportionally to the injurious impact that could result from a policy decision on these vulnerable people’s rights.

Depuis une vingtaine d'années, la résolution de problèmes d'optimisation globale non convexes avec contraintes a connu un formidable essor. Les algorithmes de branch and bound basée sur l'analyse d'intervalles ont su trouver leur place, car ils ont l'avantage de prouver l'optimalité de la solution de façon déterministe, avec un niveau de certitude pouvant aller jusqu'à la précision machine. Cependant, la complexité exponentielle en temps et en mémoire de ces algorithmes induit une limite intrinsèque, c'est pourquoi il est toujours nécessaire d'améliorer les techniques actuelles. - Dans cette thèse, nous avons développé de nouvelles arithmétiques basées sur l'arithmétique d'intervalles et l'arithmétique affine, afin de calculer des minorants et des majorants de meilleure qualité de fonctions explicites sur un intervalle. - Nous avons ensuite développé une nouvelle méthode automatique de construction de relaxations linéaires. Cette construction est basée sur l'arithmétique affine et procède par surcharge des opérateurs. Les programmes linéaires ainsi générés ont exactement le même nombre de variables et de contraintes d'inégalité que les problèmes originaux, les contraintes d'égalité étant remplacées par deux inégalités. Cette nouvelle procédure permet de calculer des minorants fiables et des certificats d'infaisabilité pour chaque sous-domaine à chaque itération de notre algorithme de branch and bound par intervalles. De nombreux tests numériques issus du site COCONUT viennent confirmer l'efficacité de cette approche. - Un autre aspect de cette thèse a été l'étude d'une extension de ce type d'algorithmes en introduisant une limite sur mémoire disponible. L'idée principale de cette approche est de proposer un processus inverse de l'optimisation par le biais d'un principe métaheuristique: plutôt que d'améliorer des solutions locales à l'aide de métaheuristiques telles que les algorithmes Taboo ou VNS, nous partons d'une méthode exacte et nous la modifions en une heuristique. De cette façon, la qualité de la solution trouvée peut être évaluée. Une étude de la complexité de ce principe métaheuristique a également été effectuée. - Enfin, pour finir l'étude, nous avons appliqué notre algorithme à la résolution de problème en géométrie plane, ainsi qu'à la résolution d'un problème de dimensionnement de moteur électrique. Les résultats obtenus ont permis de confirmer l'intérêt de ce type d'algorithme, en résolvant des problèmes ouverts sur les polygones convexes et proposant des structures innovantes en génie électrique.

L'étude du domaine récent que constituent les problèmes d'optimisation combinatoires probabilistes (POCPs) forme le sujet de cette thèse. Les POCPs sont des généralisations des problèmes d'optimisation combinatoires classiques dont les formulations contiennent explicitement des éléments probabilistes. Plusieurs motivations ont provoqué cette étude. Deux d'entre elles sont particulièrement importantes. La première correspond au désir de formuler et d'analyser des modèles qui sont plus appropriés pour des problèmes pratiques pour lesquels l'aléatoire est une source constante de préoccupations, les modèles de nature probabiliste sont plus particulièrement attractifs comme abstraction mathématique des systèmes réels. La seconde motivation est d'analyser la stabilité des solutions optimales des problèmes déterministes lorsque les exemplaires sont perturbés : les perturbations sont simulées par la présence ou l'absence de sous-ensembles des données. Notre étude s'appuie sur certains de ces problèmes et en particulier : problème du voyageur de commerce; problème d'ordonnancement des travaux probabiliste et le problème du bin-packing probabiliste. Les questions soulevées et les résultats obtenus sont dans les domaines suivants : complexités des problèmes et analyse d'heuristiques pour les POCPs ; analyse du comportement asymptotique des problèmes lorsque les exemplaires correspondent à des problèmes de grandes tailles ; dégager une méthodologie générale d'étude de la stabilité des solutions des problèmes d'optimisation combinatoires classiques.