Un polyèdre convexeP de est constitué par l'ensemble des points satisfaisant un nombre arbitrairement grand mais fini d'inégalités linéaires (i.e. de la forme ).
Optimiser sur P consiste à déterminer pour toute fonction linéaire .
Séparer sur P consiste à déterminer, pour tout point , si appartient à P ou non, et sinon, à déterminer un hyperplan séparant de P (i.e. trouver une inégalité linéaire violée par mais satisfaite par tout point de P).
On peut optimiser sur un polyèdre en temps polynomial si et seulement si on peut séparer sur ce polyèdre en temps polynomial.