Approche polyédrique

Le problème fondamental 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, 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. À l'origine cette approche a été introduite par Jack Edmonds qui donna 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 G = (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 séparation/optimisation.

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.