De nombreux problèmes de la vie réelle sont exprimés sous la forme de décisions à prendre à l’aide de l’information accessible dans le but d’atteindre certains objectifs. La programmation numérique a prouvé être un outil efficace pour modéliser et résoudre une grande variété de problèmes de ce type. Cependant, de nombreux problèmes en apparence faciles sont encore durs à résoudre. Et même des problèmes faciles de programmation linéaire deviennent durs avec l’incertitude de l’information disponible. Motivés par un problème de télécommunication où l’on doit associer des machines virtuelles à des serveurs tout en minimisant les coûts, nous avons employé plusieurs outils de programmation mathématique dans le but de résoudre efficacement le problème, et développé de nouveaux outils pour des problèmes plus généraux. Dans l’ensemble, résumons les principaux résultats de cette thèse comme suit. Une formulation exacte et plusieurs reformulations pour le problème d’affectation de machines virtuelles dans le cloud sont données. Nous utilisons plusieurs inégalités valides pour renforcer la formulation exacte, accélérant ainsi l’algorithme de résolution de manière significative. Nous donnons en outre un résultat géométrique sur la qualité de la borne lagrangienne montrant qu’elle est généralement beaucoup plus forte que la borne de la relaxation continue. Une hiérarchie de relaxation est également proposée en considérant une séquence de couverture de l’ensemble de la demande. Ensuite, nous introduisons une nouvelle formulation induite par les symétries du problème. Cette formulation permet de réduire considérablement le nombre de termes bilinéaires dans le modèle, et comme prévu, semble plus efficace que les modèles précédents. Deux approches sont développées pour la construction d’enveloppes convexes et concaves pour l’optimisation bilinéaire sur un hypercube. Nous établissons plusieurs connexions théoriques entre différentes techniques et nous discutons d’autres extensions possibles. Nous montrons que deux variantes de formulations pour approcher l’enveloppe convexe des fonctions bilinéaires sont équivalentes. Nous introduisons un nouveau paradigme sur les problèmes linéaires généraux avec des paramètres incertains. Nous proposons une hiérarchie convergente de problèmes d’optimisation robuste – approche robuste multipolaire, qui généralise les notions de robustesse statique, de robustesse d’affinement ajustable, et de robustesse entièrement ajustable. En outre, nous montrons que l’approche multipolaire peut générer une séquence de bornes supérieures et une séquence de bornes inférieures en même temps et les deux séquences convergent vers la valeur robuste des FARC sous certaines hypothèses modérées / Many real life problems are characterized by making decisions with current information to achieve certain objectives. Mathematical programming has been developed as a successful tool to model and solve a wide range of such problems. However, many seemingly easy problems remain challenging. And some easy problems such as linear programs can be difficult in the face of uncertainty. Motivated by a telecommunication problem where assignment decisions have to be made such that the cloud virtual machines are assigned to servers in a minimum-cost way, we employ several mathematical programming tools to solve the problem efficiently and develop new tools for general theoretical problems. In brief, our work can be summarized as follows. We provide an exact formulation and several reformulations on the cloud virtual machine assignment problem. Then several valid inequalities are used to strengthen the exact formulation, thereby accelerating the solution procedure significantly. In addition, an effective Lagrangian decomposition is proposed. We show that, the bounds providedby the proposed Lagrangian decomposition is strong, both theoretically and numerically. Finally, a symmetry-induced model is proposed which may reduce a large number of bilinear terms in some special cases. Motivated by the virtual machine assignment problem, we also investigate a couple of general methods on the approximation of convex and concave envelopes for bilinear optimization over a hypercube. We establish several theoretical connections between different techniques and prove the equivalence of two seeming different relaxed formulations. An interesting research direction is also discussed. To address issues of uncertainty, a novel paradigm on general linear problems with uncertain parameters are proposed. This paradigm, termed as multipolar robust optimization, generalizes notions of static robustness, affinely adjustable robustness, fully adjustable robustness and fills the gaps in-between. As consequences of this new paradigms, several known results are implied. Further, we prove that the multipolar approach can generate a sequence of upper bounds and a sequence of lower bounds at the same time and both sequences converge to the robust value of fully adjustable robust counterpart under some mild assumptions

Ce mémoire est consacré à trois modèles classiques de géométrie aléatoire : les mosaïques, les enveloppes convexes et le modèle booléen. Dans la première partie, on étudie les mosaïques poissonniennes d'hyperplans isotropes et plus particulièrement leur zéro-cellule qui est un polyèdre convexe aléatoire de l'espace euclidien. Deux cas particuliers de zéro-cellules sont la cellule typique de Poisson-Voronoi et la cellule de Crofton. On donne une formule explicite pour la loi du nombre de côtés d'une zéro-cellule en dimension deux. On s'intéresse au comportement asymptotique de cette loi et on fait le lien avec le problème de Sylvester des points en position convexe. On décrit ensuite la loi du rayon circonscrit ainsi que le comportement asymptotique du polyèdre à grand rayon inscrit au moyen de théorèmes limites. De cette manière et aussi par l'utilisation de la fréquence fondamentale, on apporte des précisions à l'énoncé de la conjecture de D. G. Kendall. La seconde partie a pour objet les enveloppes convexes de processus ponctuels de Poisson isotropes dans la boule-unité. On établit un résultat de type grandes déviations pour le nombre de sommets. On montre ensuite la convergence de la frontière de l'enveloppe après changement d'échelle et on en déduit des résultats de valeurs extrêmes, estimations de variance, théorèmes centraux limites et principes d'invariance pour certaines caractéristiques. Dans la troisième partie, on s'intéresse enfin aux modèles de recouvrement de type booléen de l'espace euclidien. Dans un premier travail, on applique une variante du modèle sans interpénétration des objets à la modélisation d'un phénomène de fissuration. On étudie ensuite la convergence de la composante connexe de l'origine d'un modèle booléen vers la cellule de Crofton en dimension deux. On s'intéresse enfin à la fonction de visibilité de cette composante connexe pour laquelle on obtient une estimée de la queue de distribution et des résultats de valeurs extrêmes.