Étant donné un graphe G = (V U T, E), tel que V U T représente l'ensemble des sommets où T est un ensemble de terminaux, et une fonction poids w associée aux sommets non terminaux, le problème du séparateur de poids minimum consiste à partitionner V U T en k + 1 sous-ensembles {S, V1,..., Vk} tel qu'il n'y a aucune arête entre deux sous-ensembles différents Vi et Vj, chaque Vi contient exactement un terminal et le poids de S est minimum. Dans cette thèse, nous étudions le problème d'un point de vue polyèdral. Nous donnons deux formulations en nombres entiers pour le problème, et pour une de ces formulations, nous étudions le polyèdre associé. Nous présentons plusieurs inégalités valides, et décrivons des conditions de facette. En utilisant ces résultats, nous développons un algorithme de coupes et branchement pour le problème. Nous étudions également le polytope des séparateurs dans les graphes décomposables par sommets d'articulation. Si G est un graphe qui se décompose en G1 et G2, alors nous montrons que le polytope des séparateurs dans G peut être décrit à partir de deux systèmes linéaires liés à G1 et G2. Ceci donne lieu à une technique permettant de caractériser le polytope des séparateurs dans les graphes qui sont récursivement décomposables. Ensuite, nous étudions des formulations étendues pour le problème et proposons des algorithmes de génération de colonnes et branchement ainsi que des algorithmes de génération de colonnes, de coupes et branchement. Pour chaque formulation, nous présentons un algorithme de génération de colonnes, une procedure pour le calcul de la borne duale ainsi qu'une règle de branchement. De plus, nous présentons quatre variantes du problème du séparateur. Nous montrons que celles-ci sont NP-difficiles, et pour chacune d'elles nous donnons une formulation en nombres entiers et présentons certaines classes d'inégalités valides. / Given a graph G = (V U T, E) with V U T the set of vertices, where T is a set of terminals, and a weight function w, associated with the nonterminal nodes, the multi-terminal vertex separator problem consists in partitioning V U T into k + 1 subsets {S, V1,..., Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one terminal and the weight of S is minimum. In this thesis, we consider the problem from a polyhedral point of view. We give two integer programming formulations for the problem, for one of them, we investigate the related polyhedron. We describe some valid inequalities and characterize when these inequalities define facets. Using these results, we develop a Branch-and-Cut algorithm for the problem. We also study the multi-terminal vertex separator polytope in the graphs decomposable by one node cutsets. If G is a graph that decomposes into G1 and G2, we show that the multi-terminal vertex separator polytope in G can be described from two linear systems related to G1 and G2. This gives rise to a technique for characterizing the multi-terminal vertex separator polytope in the graphs that are recursively decomposable. Moreover, we propose three extended formulations for the problem and derive Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present a column generation scheme, the way to compute the dual bound, and the branching scheme. Finally, we discuss four variants of the multi-terminal vertex separator problem. We show that all these variants are NP-hard and for each one we give an integer programming formulation and present some class of valid inequalities.

L’usinage 5 axes à grande vitesse est de plus en plus utilisé dans l’industrie pour réaliser des pièces de géométrie complexe à forte valeur ajoutée avec pour contrainte de respecter la qualité géométrique tout en maximisant la productivité. Dans ce contexte, la FAO et plus particulièrement la génération des trajectoires d’usinage jouent un rôle prépondérant. Ces travaux proposent de définir des trajectoires en fonction de la pièce à réaliser mais aussi de la structure poly articulée et de ses performances cinématiques. La grande diversité des structures en termes d’architecture et de cinématique impose une méthode de calcul générique facilitant la définition de trajectoires adaptées pour leur suivi. L’état de l’art des travaux réalisé dans les domaines de l’usinage et de la robotique pour répondre à cette problématique conduit à utiliser des polytopes de manipulabilité cinématique pour modéliser les contraintes cinématiques. L’analyse de ces polytopes et de la géométrie de la pièce à usiner permet de générer des trajectoires avec une vitesse outil/pièce maîtrisée et un temps de parcours réduit dans le cas de l’usinage 5 axes positionné et de l’usinage 5 axes continu. Ce formalisme met en avant les fortes dépendances entre les différents paramètres de la stratégie d’usinage (positionnement de la pièce, direction d’avance et orientation de l’outil) et permet de privilégier certaines combinaisons de ces paramètres pour maîtriser la vitesse d’exécution de la trajectoire. / 5 axes high speed milling is increasingly used for manufacturing high addedvalue parts with complex forms in order to respect surface quality while maximizing productivity. In this context, CAM and more specifically toolpath computations play a major part. This work proposes to define toolpath depending on the workpiece but also onkinematical capacities of the polyarticulated structure.The large variety of structure in terms of architecture and kinematic enforce a generic calculation method to simplify adaptative toolpath generation. A state of the art realized in machining and robotics proposes to investigate the use of kinematical manipulability polytopes to represent kinematical capacities. An analysis of the polytopes and of the workpiece allows to generate toolpaths with a controlled feedrate and a decreasing time in 5 axes positionned milling and in 5 axes continous milling. This formalism highlights strong interactions between milling strategy parameters (workpiece setup, feed direction, tool orientation) and allows to prioritize specific parameters mix to have a controlled execution feedrate.

In this dissertation, we exhibit two instances of polyhedra in combinatorial convex geometry. The first instance arises in the context of Ehrhart theory, and the polyhedra are the central objects of study. The second instance arises in algebraic statistics, and the polyhedra act as a conduit through which we study a nonpolyhedral problem. In the first case, we examine combinatorial and algebraic properties of the Ehrhart h*-polynomial of the r-stable (n,k)-hypersimplices. These are a family of polytopes which form a nested chain of subpolytopes within the (n,k)-hypersimplex. We show that a well-studied unimodular triangulation of the (n,k)-hypersimplex restricts to a triangulation of each r-stable (n,k)-hypersimplex within. We then use this triangulation to compute the facet-defining inequalities of these polytopes. In the k=2 case, we use shelling techniques to devise a combinatorial interpretation of the coefficients of the h*-polynomials in terms of independent sets of certain graphs. From this, we then extract some results on unimodality. We also characterize the Gorenstein r-stable (n,k)-hypersimplices, and we conclude that these also have unimodal h*-polynomials. In the second case, for a graph G on p vertices we consider the closure of the cone of concentration matrices of G. The extreme rays of this cone, and their associated ranks, have applications in maximum likelihood estimation for the undirected Gaussian graphical model associated to G. Consequently, the extreme ranks of this cone have been well-studied. Yet, there are few graph classes for which all the possible extreme ranks are known. We show that the facet-normals of the cut polytope of G can serve to identify extreme rays of this nonpolyhedral cone. We see that for graphs without K5 minors each facet-normal of the cut polytope identifies an extreme ray in the cone, and we determine the rank of this extreme ray. When the graph is also series-parallel, we find that all possible extreme ranks arise in this fashion, thereby extending the collection of graph classes for which all the possible extreme ranks are known.

Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité (défini comme la plus grande taille d'un stable), et les stables se classent certainement parmi les structures les plus simples et fondamentales en théorie des graphes. La thèse est divisée en deux parties, toutes deux liées à la notion de stables dans un graphe. Dans la première partie, nous étudions un problème de coloration de graphes, c'est à dire de partition en stables, où le but est de minimiser l'entropie de la partition. C'est une variante du problème classique de minimiser le nombre de couleurs utilisées. Nous considérons aussi une généralisation du problème aux couvertures d'ensembles. Ces deux problèmes sont appelés respectivement minimum entropy coloring et minimum entropy set cover, et sont motivés par diverses applications en théorie de l'information et en bioinformatique. Nous obtenons entre autres une caractérisation précise de la complexité de minimum entropy set cover : le problème peut être approximé à une constante lg e (environ 1.44) près, et il est NP-difficile de faire strictement mieux. Des résultats analogues sont prouvés concernant la complexité de minimum entropy coloring. Dans la deuxième partie de la thèse, nous considérons les graphes dont le nombre de stabilité augmente dès qu'une arête est enlevée. Ces graphes sont dit être "alpha-critiques", et jouent un rôle important dans de nombreux domaines, comme la théorie extrémale des graphes ou la combinatoire polyédrique. Nous revisitons d'une part la théorie des graphes alpha-critiques, donnant à cette occasion de nouvelles démonstrations plus simples pour certains théorèmes centraux. D'autre part, nous étudions certaines facettes du polytope des ordres totaux qui peuvent être vues comme une généralisation de la notion de graphe alpha-critique. Nous étendons de nombreux résultats de la théorie des graphes alpha-critiques à cette famille de facettes.

In this dissertation we first introduce an extension of the notion of parking functions to cars of different sizes. We prove a product formula for the number of such sequences and provide a refinement using a multi-parameter extension of the Abel--Rothe polynomial. Next, we study the incidence Hopf algebra on the noncrossing partition lattice. We demonstrate a bijection between the terms in the canceled chain decomposition of its antipode and noncrossing hypertrees. Thirdly, we analyze the sum of the 𝑟th powers of the descent set statistic on permutations and how many small prime factors occur in these numbers. These results depend upon the base 𝑝 expansion of both the dimension and the power of these statistics. Finally, we inspect the ƒ-vector of the descent polytope DPv, proving a maximization result using an analogue of the boustrophedon transform.

Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, PG, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, PD. Basic properties of both families of simplices, PG and PD, are established using techniques from Ehrhart theory. Motivated by a well-known conjecture in the field, our investigation focuses on reflexivity, the integer decomposition property, and unimodality of Ehrhart h*-vectors of these polytopes. A systematic investigation of PG for trees, cycles, and complete graphs is provided, which is enhanced by an investigation of PD for cyclic digraphs. We form intriguing connections with other families of simplices and produce G and D such that the h*-vectors of PG and PD exhibit extremal behavior.

Un produit mécanique naît d'un besoin et doit remplir des fonctions particulières. Le travail du concepteur consiste à trouver une solution répondant à ces exigences. Il définit alors dans un langage normalisé qui est le tolérancement les variations géométriques limites des surfaces fonctionnelles du mécanisme.<br />Le modèle des domaines jeux et domaines écarts est basé sur le concept des torseurs de petits déplacements. Il permet de modéliser les déplacements relatifs entre deux pièces d'une même liaison ou les déplacements d'un élément géométrique dans sa zone de tolérance. Cette traduction se présente sous la forme de domaines dans l'espace 6D des petits déplacements (3 rotations et 3 translations) traduisant les contraintes en déplacements des entités considérées. Des opérations géométriques sur ces domaines 6D telles que la somme de Minkowski, l'intersection ou l'opération Sweeping-Intersection servent alors à valider le tolérancement choisi. La modélisation 6D peut ensuite être transformée en zones 3D injectées dans le modèle CAO dans le but de renseigner le concepteur sur la pertinence de ses choix.

Une variété horosphérique est une variété algébrique normale dans laquelle un groupe algébrique réductif opère avec une orbite ouverte fibrée en tores sur une variété de drapeaux. En particulier, les variétés toriques et les variétés de drapeaux sont horosphériques. Dans cet article, on classifie les variétés horosphériques de Fano en termes de certains polytopes rationnels qui généralisent les polytopes réflexifs considérés par V. Batyrev. Puis on obtient une majoration du degré des variétés horosphériques lisses de Fano, analogue à celle donnée par O. Debarre dans le cas torique. On étend un résultat récent de C. Casagrande: les variétés horosphériques Q-factorielles de Fano ont leur nombre de Picard majoré par deux fois la dimension. On donne aussi de nombreux exemples en rang 2.

Les réseaux de télécommunications évoluent vers des modèles qui consistent en un certain nombre de routeurs IP interconnectés par un réseau optique intelligent. Cette nouvelle infrastructure multicouche nécessite un haut niveau de fiabilité, de telle manière que les services du réseau puissent être rétablis en cas de panne. Dans cette thèse, nous considérons différents problèmes de sécurisation et de dimensionnement liés à cette infrastructure multicouche. Nous donnons des formulations en terme de programmes linéaires mixtes , et nous discutons des polytopes associés. Nous décrivons plusieurs classes d'inégalités valides et étudions les conditions pour qu'elles définissent des facettes. Nous discutons de procédures de séparation pour ces inégalités et induisons des opérations de réduction. Nous développons des algorithmes de coupes et branchements et de coupes génération de colonnes et branchements et présentons une étude expérimentales sur des instances aléatoires et réelles.

La performance d'un moteur d'hélicoptère est fortement corrélée à la performance de la turbine haute pression, et plus particulièrement à l'influence des différents composants constitutifs. Le rendement énergétique d'une turbine haute pression est garanti par la maîtrise des jeux entre les sommets des aubes et le stator durant tout le cycle de fonctionnement de la turbine. L'objectif de ces travaux est de proposer une méthode à caractère multiphysique reposant sur des opérations de polytopes (somme de Minkowski et intersection) permettant de valider des spécifications géométriques, des spécifications de contacts et des spécifications thermomécaniques. Ces spécifications garantissent une limite de la section de fuite en sommets d'aubes pour un risque de touche minimal. Un polytope permet de simuler les variations géométriques entre deux surfaces d'une même pièce, de surcroît un polytope de contact permet de simuler les variations géométriques entre deux surfaces potentiellement en contact. La structure topologique des contacts de la turbine se formalise par un graphe de contacts à une composante connexe. Cette structure permet de définir les sommes de Minkowski et les intersections des polytopes traduisant la propagation des écarts géométriques à travers la turbine. Les écarts géométriques d'origine thermomécanique sont évalués par la méthode des éléments finis. Ces travaux donnent au concepteur des éléments de décision sur l'influence des choix de conception, en particulier l'influence des formes de pièces et du comportement des liaisons, sur le fonctionnement de la turbine.