En mathématiques, le problème fondamental de l'approche polyédrique est le suivant.
Parfois, 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}) 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, 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.
Catégorie:Algorithmique et convexité Catégorie:Optimisation combinatoire