Points entiers dans les polyèdres convexes - Integer points in convex polyhedra
L'étude des points entiers dans les polyèdres convexes est motivée par des questions telles que "combien de solutions à valeurs entières non négatives a un système d'équations linéaires à coefficients non négatifs" ou "combien de solutions un programme linéaire entier a -t-il". Le comptage de points entiers dans les polyèdres ou d'autres questions à leur sujet se posent dans la théorie de la représentation , l' algèbre commutative , la géométrie algébrique , les statistiques et l' informatique .
L'ensemble des points entiers, ou, plus généralement, l'ensemble des points d'un réseau affine , dans un polyèdre est appelé Z-polyèdre , à partir de la notation mathématique ou Z pour l'ensemble des nombres entiers.
Propriétés
Pour un treillis Λ, le théorème de Minkowski concerne le nombre d (Λ) et le volume d'un symétrique ensemble convexe S au nombre de points de réseau contenus dans S .
Le nombre de points de réseau contenus dans un polytope dont tous les sommets sont des éléments du réseau est décrit par le polynôme d'Ehrhart du polytope . Les formules pour certains des coefficients de ce polynôme impliquent également d (Λ).
Applications
Optimisation des boucles
Dans certaines approches d' optimisation de boucle , l'ensemble des exécutions du corps de boucle est considéré comme l'ensemble des points entiers dans un polyèdre défini par des contraintes de boucle.
Voir également
Références et notes
Lectures complémentaires
- Barvinok, Alexander ; Beck, Matthias; Haase, Christian; Reznick, Bruce ; Welker, Volkmar (2005), Integer Points In Polyhedra: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference tenue à Snowbird, UT, 13-17 juillet 2003 , Contemporary Mathematics, 374 , Providence, RI: American Mathematical Society, doi : 10.1090 / conm / 374 , ISBN 0-8218-3459-2, MR 2134757
- Barvinok, Alexander (2008), Integer Points In Polyhedra , Zurich Lectures in Advanced Mathematics, Zürich: European Mathematical Society, doi : 10.4171 / 052 , ISBN 978-3-03719-052-4, MR 2455889
- Beck, Matthias; Haase, Christian; Reznick, Bruce ; Vergne, Michèle ; Welker, Volkmar; Yoshida, Ruriko (2008), Integer Points In Polyhedra: Geometry, Number Theory, Representation Theory, Algebra, Optimization, Statistics (PDF) , Contemporary Mathematics, 452 , Providence, RI: American Mathematical Society, doi : 10.1090 / conm / 452 , ISBN 978-0-8218-4173-0, MR 2416261