Théorème optimisation/séparation

Un article de Wikipédia, l'encyclopédie libre.

Le théorème Optimisation/Séparation est une conséquence la méthode de l'ellipsoïde. Il constitue un résultat (très difficile à montrer) majeur en optimisation combinatoire qui fait le lien entre l'approche polyèdrale et l'algorithmique. Ce résultat établit l'équivalence, du point de vue de la complexité algorithmique, entre "optimiser" et "séparer" sur un même polyèdre. Un polyèdre P de \mathbb R^n est constitué par l'ensemble des points x\in \mathbb R^n satisfaisant un nombre arbitrairement grand mais fini d'inégalités linéaires (i.e. de la forme \sum_{i=1}^{i=n} a_ix_i \le b ).

  • Optimiser sur P consiste à déterminer \max_{x\in P} f(x) pour toute fonction linéaire f(x).
  • Séparer sur P consiste à déterminer si \bar x\in P ou non, pour tout point \bar x \in \mathbb R^n , et si non à déterminer un hyperplan séparant \bar x de P (i.e. trouver une inégalité linéaire violée par \bar x mais satisfaite par tout point de P).


Théorème Optimisation/Séparation (M. Grötschel, L. Lovász, A. Shrijver, 1981) 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.