Concept

Integral polytope

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are also called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively. An -dimensional regular simplex can be represented as an integer polytope in , the convex hull of the integer points for which one coordinate is one and the rest are zero. Another important type of integral simplex, the orthoscheme, can be formed as the convex hull of integer points whose coordinates begin with some number of consecutive ones followed by zeros in all remaining coordinates. The -dimensional unit cube in has as its vertices all integer points whose coordinates are zero or one. A permutahedron has vertices whose coordinates are obtained by applying all possible permutations to the vector . An associahedron in Loday's convex realization is also an integer polytope and a deformation of the permutahedron. In the context of linear programming and related problems in mathematical optimization, convex polytopes are often described by a system of linear inequalities that their points must obey. When a polytope is integral, linear programming can be used to solve integer programming problems for the given system of inequalities, a problem that can otherwise be more difficult. Some polyhedra arising from combinatorial optimization problems are automatically integral. For instance, this is true of the order polytope of any partially ordered set, a polytope defined by pairwise inequalities between coordinates corresponding to comparable elements in the set. Another well-known polytope in combinatorial optimization is the matching polytope. Clearly, one seeks for finding matchings algorithmically and one technique is linear programming.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.