Cette thèse développe les deux approches locales et globales basées sur la programmation DC et DCA pour l'optimisation combinatoire en variables mixtes 0-1 et leurs applications à la résolution de nombreux problèmes en planification opérationnelle. Plus particulièrement, cette thèse adresse à: l'amélioration de l'algorithme d'approximation extérieure basée sur DCA (appelé DCACUT) introduit par Nguyen V.V. et Le Thi pour la programmation linéaire en variables mixtes 0-1, les combinaisons des algorithmes globaux et DCA et l'étude numérique comparative de ces approches pour la programmation linéaire en variables mixtes 0-1, l'utilisation de DCA à la résolution de la programmation DC en variables mixtes 0-1 en utilisant la pénalité exacte, la mise en œuvre des algorithmes développés à la résolution des problèmes de grande taille en planification opérationnelle comme les problèmes dans le réseau de télécommunication sans fils, les problèmes d’ordonnancement ainsi que le problème d'affectation de tâches des véhicules aériens non pilotés ou bien le problème des tournées de véhicules dans une chaîne d'approvisionnement / This thesis develops two local and global approaches based on DC programming and DCA for mixed 0-1 combinatorial optimization and their applications to many problems in operational planning. More particularly, this thesis consists of: the improvement of the outer approximation algorithm based on DCA (called DCACUT) introduced by Nguyen V.V and Le Thi for mixed 0-1 linear programming, the combinations of global algorithms and DCA and the comparative numerical study of these approaches for mixed 0-1 linear programming, the use of DCA for solving mixed 0-1 programming via an exact penalty technique, the implementation of the algorithms developed for solving large scale problems in operational planning: two problems in wireless telecommunication network, two scheduling problems, an UAV task assignment problem and an inventory routing problem in supply chains

L'informatique moderne n'est plus uniquement composée de machines personnelles et de super calculateurs. De nombreux supports de calcul sont maintenant disponibles et chacun pose des contraintes particulières amenant à de nombreux objectifs. Ainsi, la notion de performance d'une application est devenue multi-dimensionnelle. Par exemple, ordonnancer optimalement (en temps) une application sur une grille de calcul est inutile si elle ne fournit pas de résultat parce qu'une machine tombe en panne. Fournir une solution à ces problèmes est un défi algorithmique actuel. Dans ce manuscrit, nous étudions l'ordonnancement multi-objectif à l'aide des outils de la théorie de l'approximation. Nous traitons ainsi quatre problèmes. Les deux premiers sont inspirés des systèmes embarqués, tandis que les deux derniers sont inspirés des problématiques que l'on retrouve sur les grilles et les \textit{clusters}. Le premier problème étudié est l'optimisation des performances d'une application sur une machine disposant de peu de mémoire de stockage. Nous montrons que l'utilisation de l'optimisation multi-objectif permet de fournir une solution et des informations sur le problème que la théorie mono-objectif de l'approximation ne pouvait pas obtenir. Les deux problèmes suivants concernent l'optimisation des performances d'une application lorsque les machines ne sont pas entièrement fiables. Les différents modèles de défaillances amènent à des problèmes d'optimisation radicalement différents. C'est pourquoi le deuxième problème traite de la sûreté de fonctionnement des systèmes embarqués alors que le troisième considère la fiabilité des grilles et \textit{clusters}. Le dernier problème concerne l'utilisation simultanée d'une plate-forme de calcul parallèle par de nombreux utilisateurs. Nous montrons comment l'utilisation de l'optimisation multi-objectif peut permettre de prendre en compte les besoins utilisateurs au sein du processus d'optimisation.

Les travaux effectués dans ma thèse portent sur la discrétisation de processus dans un domaine et sur les méthodes numériques probabilistes pour les EDP paraboliques quasilinéaires. En ce qui concerne le premier sujet, nous avons d'abord montré un résultat d'encadrement de l'erreur faible associée à un processus de diffusion hypoelliptique tué approché par son schéma d'Euler tué à temps discret, cf. Chapitre 1. Ensuite, dans le cadre non markovien des processus d'Itô, nous avons obtenu une borne pour l'erreur faible associée à la discrétisation du temps de sortie à l'aide de techniques originales de martingales, cf. Chapitre 2. Nous avons enfin, dans le cas particulier du mouvement Brownien dans un orthant, obtenu un développement de l'erreur et une méthode d'accélération de la convergence basée sur une correction adéquate du domaine, cf. Chapitre 3. Par rapport au deuxième sujet, nous avons proposé un algorithme probabiliste simple à implémenter pour approcher la solution d'EDP paraboliques quasilinéaires et nous avons établi sa vitesse de convergence. Cette méthode consiste à discrétiser l'équation différentielle stochastique progressive rétrograde (EDSPR) qui permet de donner une représentation probabiliste de l'EDP, cf. Chapitre 4.

L'objectif de cette thèse est d'appliquer les méthodes d'approximations stochastiques à l'estimation de la densité et de la régression. Dans le premier chapitre, nous construisons un algorithme stochastique à pas simple qui définit toute une famille d'estimateurs récursifs à noyau d'une densité de probabilité. Nous étudions les différentes propriétés de cet algorithme. En particulier, nous identifions deux classes d'estimateurs; la première correspond à un choix de pas qui permet d'obtenir un risque minimal, la seconde une variance minimale. Dans le deuxième chapitre, nous nous intéressons à l'estimateur proposé par Révész (1973, 1977) pour estimer une fonction de régression r:x-> E[Y|X=x]. Son estimateur r_n, construit à l'aide d'un algorithme stochastique à pas simple, a un gros inconvénient: les hypothèses sur la densité marginale de X nécessaires pour établir la vitesse de convergence de r_n sont beaucoup plus fortes que celles habituellement requises pour étudier le comportement asymptotique d'un estimateur d'une fonction de régression. Nous montrons comment l'application du principe de moyennisation des algorithmes stochastiques permet, tout d'abord en généralisant la définition de l'estimateur de Révész, puis en moyennisant cet estimateur généralisé, de construire un estimateur récursif br_n qui possède de bonnes propriétés asymptotiques. Dans le troisième chapitre, nous appliquons à nouveau les méthodes d'approximation stochastique à l'estimation d'une fonction de régression. Mais cette fois, plutôt que d'utiliser des algorithmes stochastiques à pas simple, nous montrons comment les algorithmes stochastiques à pas doubles permettent de construire toute une classe d'estimateurs récursifs d'une fonction de régression, et nous étudions les propriétés asymptotiques de ces estimateurs. Cette approche est beaucoup plus simple que celle du deuxième chapitre: les estimateurs construits à l'aide des algorithmes à pas doubles n'ont pas besoin d'être moyennisés pour avoir les bonnes propriétés asymptotiques.

Cette thèse comporte cinq chapitres.<br /><br />Chapitre 1 : Schémas de discrétisation anticipatifs et estimation du paramètre de dérive d'une diffusion. <br />Pour estimer le paramètre de dérive d'une diffusion unidimensionnelle ergodique observée à pas d>0 et fixé, on construit des contrastes basés sur des schémas d'approximation anticipatifs (schéma du trapèze et de Simpson) couplés à la méthode d'estimation des moments généralisés. Les estimateurs obtenus présentent des biais d'estimation en d**2 pour le schéma du trapèze et en d**4 pour le schéma de Simpson. L'efficacité asymptotique est par ailleurs préservée à un facteur (1+O(d)) près.<br /><br />Chapitre 2 : Schéma d'approximation adapté à l'ordre p et estimation de la dérive d'une diffusion.<br />Pour estimer le paramètre de dérive d'une diffusion ergodique observée à pas d, nous approximons la vraisemblance exacte de l'échantillon par celle d'un processus gaussien dont l'espérance conditionnelle est approchée à l'ordre d**p. L'estimateur obtenu est asymptotiquement biaisé. Ce biais est explicite et est de l'ordre de d**p. L'efficacité asymptotique est par ailleurs préservée à un facteur près. <br /><br />Chapitre 3 : Estimation du paramètre de dérive d'une diffusion sous des conditions d'irrégularité de la dérive.<br />Le problème étudié est l'analogue de celui étudié par Chan pour les AR à seuil (Threshold, Ann. Stat. 1993). Ici, le temps n'est plus discret mais continu. La dérive de la diffusion est continue, mais à dérivées discontinues en un seuil r. Le problème étudié est celui de l'estimation de ce seuil r. Si le pas d'observation d_n tend vers 0 et si T=n*d_n tend vers l'infini, l'estimateur des Moindres carrés (associé au schéma d'Euler ) de r est consistant. Si de plus n*(d_n)**3 tend vers 0, il y a normalité asymptotique à une vitesse standard. <br /><br />Chapitre 4 : Estimation d'un CAR(p) incomplètement observé à partir des équations de Yule-Walker.<br />Un travail de Hyndman (JTSA, 93) présente les équations de Yule-Walker pour un CAR(p), X, (qui est aussi une diffusion p-dimensionnelle, Y=(X, X(1),...,X(p-1))) et l'estimation des paramètres déduite sur la base de ces équations et de l'observation complète de Y (temps continu et observation des p-composantes de Y). Adoptant une méthodologie identique, nous étudions ce problème d'estimation lorsque l'on ne dispose que de l'observation de X, la première composante de Y, et ceci à des instants discrets (au pas d). Nous proposons <br />un estimateur convergent des paramètres à un biais près de l'ordre de d.<br /><br />Chapitre 5 : Precision of systematic sampling and transitive methods.<br />Nous proposons une méthode d'estimation dérivée des méthodes transitives utilisées notamment dans le domaine de la stéréologie. Cette méthode permet d'estimer l'écart quadratique moyen d'estimateurs empiriques construits à partir d'un échantillonnage systématique.

L'analyse des techniques d'approximation est centrale en géométrie algorithmique, pour des raisons pratiques comme théoriques. Dans cette thèse nous traitons de l'échantillonnage des structures géométriques et des algorithmes d'approximation géométriques en optimisation combinatoire. La première partie est consacrée à la combinatoire des hypergraphes. Nous débutons par les problèmes de packing, dont des extensions d'un lemme de Haussler, particulièrement le lemme dit de Shallow packing, pour lequel nous donnons aussi un minorant optimal, conjecturé mais pas établi dans les travaux antérieurs. Puis nous appliquons ledit lemme, avec la méthode de partition polynomiale récemment introduite, à l'étude d'un analogue combinatoire des régions de Macbeath de la géométrie convexe : les M-réseaux, pour lesquels nous unifions les résultats d'existence et majorations existants, et donnons aussi quelques minorants. Nous illustrons leur relation aux epsilon-réseaux, structures incontournables en géométrie combinatoire et algorithmique, notamment en observant que les majorants de Chan et al. (SODA 2012) ou Varadarajan (STOC 2010) pour les epsilon-réseaux (uniformes) découlent directement de nos résultats sur les M-réseaux. La deuxième partie traite des techniques de recherche locale appliquées aux restrictions géométriques de problèmes classiques d'optimisation combinatoire. En dix ans, ces techniques ont produit les premiers schémas d'approximation en temps polynomial pour divers problèmes tels que celui de calculer un plus petit ensemble intersectant pour un ensemble de disques donnés en entrée parmi un ensemble de points donnés en entrée. En fait, il a été montré que pour de nombreux tels problèmes, la recherche locale de rayon Θ (1/epsilon²) donne une (1 + epsilon)-approximation en temps n^{O(1/epsilon²)}. Savoir si l'exposant de n pouvait être ramené à o (1/epsilon²) demeurait une question ouverte. Nous répondons par la négative : la garantie d'approximation de la recherche locale n'est améliorable pour aucun desdits problèmes / The analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimization. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of classical combinatorial optimization problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/epsilon²) gives a (1 + epsilon)-approximation with running time n^{O(1/epsilon²)}. However the question of whether the exponent of n could be decreased to o(1/epsilon²) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results

Un objet multiboîte est composé de plusieurs parties identiques qui doivent être rangées dans des boîtes différentes. La hauteur d'une boîte est alors la somme des hauteurs des objets qu'elle contient. Ce concept généralise et englobe de nombreux problèmes de la littérature de la recherche opérationnelle.<br /><br />Une classification de ces modèles est proposée. Les bases théoriques sont posées. En particulier, la complexité pour les principaux types d'objets et objectifs est déterminée.<br /><br />Une étude détaillée est effectuée lorsque les objets ont des largeurs constantes et que l'on veut minimiser la hauteur de la boîte la plus haute. Des bornes inférieures, des heuristiques avec de très bonnes garanties de performance et un algorithme génétique sont proposés pour résoudre ce modèle. Leurs comportements théoriques et expérimentaux sont analysés.

L'implicitisation d'une surface algébrique rationnelle, c'est-à-dire le passage de la paramétrisation à une représentation implicite, est un<br />problème géométrique classique. Dans ce travail de thèse, nous utilisons la théorie des syzygies pour représenter implicitement une surface par une matrice dont les mineurs de taille maximale ont l'équation implicite comme plus grand diviseur commun. Dans les deux premiers chapitres, nous traitons deux classes de surfaces spéciales pour lesquelles il est toujours possible de construire une matrice carrée qui correspond au résultant d'une μ-base : les surfaces réglées et les surfaces canales. Dans les chapitres suivants, le cas général de surfaces rationnelles paramétrées sur une variété torique de dimension 2 est étudié. Nous montrons qu'une telle matrice peut être construite en n'utilisant que des syzygies linéaires et nous décrivons un algorithme simple et efficace pour son calcul.

Ce mémoire traite d'aspects de la dynamique nucléaire autour de la barrière. Il est montré que pour une réaction de fusion, le champ Coulombien couple le mouvement relatif des noyaux à la rotation d'un projectile déformé, et ce indépendamment de l'énergie et de la charge des noyaux. Une étude expérimentale de la réaction 6He+190Os via la spectroscopie gamma des noyaux produits a montré quant à elle que la cassure de l'6He se couplait aussi au mouvement relatif, réduisant considérablement la fusion au dessus et au voisinage de la barrière de fusion. Le chemin vers la fusion après le passage de la barrière et notamment l'équilibration des charges ont été étudiés dans le cadre de la théorie TDHF via la GDR de prééquilibre excitée dans les réactions de fusion asymétrique en N/Z. Une application à la formation de super-lourds est proposée. Enfin, des couplages entre protons et neutrons ont été mis en évidence en champ moyen avec pour principal effet une émission de protons sous-Coulombiens.

Le thème général de cette thèse est celui de la construction de modèles permettantd'approximer une fonction f lorsque la valeur de f(x) est connue pour un certainnombre de points x. Les modèles considérés ici, souvent appelés modèles de krigeage,peuvent être abordés suivant deux points de vue : celui de l'approximation dans les espacesde Hilbert à noyaux reproduisants ou celui du conditionnement de processus gaussiens.Lorsque l'on souhaite modéliser une fonction dépendant d'une dizaine de variables, lenombre de points nécessaires pour la construction du modèle devient très important etles modèles obtenus sont difficilement interprétables. A partir de ce constat, nous avonscherché à construire des modèles simplifié en travaillant sur un objet clef des modèles dekrigeage : le noyau. Plus précisement, les approches suivantes sont étudiées : l'utilisation denoyaux additifs pour la construction de modèles additifs et la décomposition des noyauxusuels en sous-noyaux pour la construction de modèles parcimonieux. Pour finir, nousproposons une classe de noyaux qui est naturellement adaptée à la représentation ANOVAdes modèles associés et à l'analyse de sensibilité globale.