Approche polyédrique
Cet article est une ébauche concernant la géométrie.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En mathématiques, le problème fondamental[réf. nécessaire] de l'approche polyédrique est le suivant.
Étant donné un ensemble X de points de l'espace euclidien, déterminer un système d'inégalités linéaires décrivant l'enveloppe convexe de X.
Parfois[évasif], X est un ensemble de points à coordonnées entières (voire de valeur 0 ou 1) qui représente les points admissibles d'un problème d'optimisation linéaire en nombres entiers. Cette approche est introduite par Jack Edmonds, qui donne la première caractérisation du polytope des couplages d'un graphe, c'est-à-dire de l'enveloppe convexe des vecteurs caractéristiques (dans {0, 1}E) des couplages d'un graphe (V, E).
Le succès de l'opération a une conséquence algorithmique directe puisqu'elle réduit ainsi le problème d'optimisation sur X à un problème facile d'optimisation linéaire classique. Ceci est rendu possible à la condition toutefois de posséder un algorithme polynomial pour séparer les contraintes linéaires, c'est-à-dire pour décider si un point donné de l'espace appartient ou non au polyèdre défini par les contraintes, et sinon à trouver un hyperplan de séparation. Ce résultat fondamental est connu sous le nom de théorème optimisation/séparation.
Dans les faits[pas clair], il existe un lien étroit entre la complexité algorithmique de l'optimisation sur X et la connaissance d'une description simple de l'enveloppe convexe de X. Pour beaucoup de problèmes polynomiaux, une telle description est connue[évasif][réf. nécessaire].
