Points entiers dans les polyèdres convexes - Integer points in convex polyhedra

Les points rouges sont les points de réseau entiers dans le polygone bleu, ce dernier représentant un programme linéaire bidimensionnel

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