Élimination de Fourier-Motzkin

Considérons un système ${\displaystyle S}$ de ${\displaystyle n}$ inégalités sur ${\displaystyle r}$ variables ${\displaystyle x_{1},\ldots ,x_{r}}$. L'élimination des variables ${\displaystyle x_{j+1},\ldots ,x_{r}}$ consiste à calculer un nouveau système ${\displaystyle S'}$ ayant les mêmes solutions que ${\displaystyle S}$ sur les variables restantes ${\displaystyle x_{1},\ldots ,x_{j}}$.

L'algorithme de Fourier-Motzkin procède en éliminant une à une les variables du système initial. Éliminer toutes les variables ${\displaystyle x_{1},\ldots ,x_{r}}$ réduit le système à une inégalité triviale : le système initial admet alors des solutions si et seulement si l'inégalité triviale ainsi obtenue est vraie. Cette méthode peut ainsi être utilisée pour déterminer si un système d'inégalités ${\displaystyle S}$ admet ou pas des solutions.

Considérons l'élimination de la dernière variable ${\displaystyle x_{r}}$ du système S. Les inégalités de S peuvent être groupées en trois catégories selon le signe du coefficient de ${\displaystyle x_{r}}$ :

• celles de la forme ${\displaystyle x_{r}\geq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$, que nous noterons ${\displaystyle x_{r}\geq A_{j}(x_{1},\dots ,x_{r-1})}$, où ${\displaystyle j}$ est un indice entre 1 et ${\displaystyle n_{A}}$ avec ${\displaystyle n_{A}}$ le nombre de telles inégalités ;
• celles de la forme ${\displaystyle x_{r}\leq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$, que nous noterons ${\displaystyle x_{r}\leq B_{j}(x_{1},\dots ,x_{r-1})}$, où ${\displaystyle j}$ est un indice entre 1 et ${\displaystyle n_{B}}$ avec ${\displaystyle n_{B}}$ le nombre de telles inégalités ;
• enfin, celles où ${\displaystyle x_{r}}$ n'apparaît pas, qui ne jouent aucun rôle et que nous noterons ${\displaystyle \phi }$.

Le système initial est alors équivalent à :

${\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\ \leq \ x_{r}\ \leq \ \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))\quad \wedge \quad \phi }$.

où la conjonction finale ${\displaystyle \wedge \phi }$ indique que les inégalités où x_r n'apparaît pas sont conservées dans le système réduit. L'élimination consiste alors à produire le système équivalent ${\displaystyle \exists x_{r}~S}$, dont la formule est, d'après la double inégalité ci-dessus :

${\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\ \leq \ \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))\quad \wedge \quad \phi }$.

L'inégalité :

${\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\ \leq \ \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))}$

est équivalente à un nouvel ensemble de ${\displaystyle n_{A}n_{B}}$ inégalités ${\displaystyle A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}$, pour ${\displaystyle 1\leq i\leq n_{A}}$ et ${\displaystyle 1\leq j\leq n_{B}}$.

Nous avons ainsi transformé le système initial S en un nouveau système S' dans lequel la variable ${\displaystyle x_{r}}$ a été éliminée. Ce nouveau système compte ${\displaystyle (n-n_{A}-n_{B})+n_{A}n_{B}}$ inégalités.

Dans le pire des cas où ${\displaystyle n_{A}=n_{B}=n/2}$, la taille du système après élimination passe de ${\displaystyle n}$ à ${\displaystyle n^{2}/4}$. Ainsi, après ${\displaystyle d}$ éliminations successives, la taille du système obtenu dans le pire des cas est de l'ordre de ${\displaystyle 4(n/4)^{2^{d}}}$, ce qui correspond à une complexité en mémoire doublement exponentielle.

Ce phénomène résulte du comportement paresseux de l'algorithme : chaque étape d'élimination produit un nombre potentiellement élevé d'inégalités redondantes, qui peuvent être retirées du système sans changer son ensemble de solutions (c'est-à-dire, de manière équivalente, qu'elles peuvent être déduites par combinaisons convexes d'autres inégalités du système). Les inégalités redondantes peuvent être détectées par programmation linéaire et retirées du système, au prix d'une plus grande complexité en temps.

Le nombre de contraintes nécessaires (non-redondantes) du système croît, quant à la lui, de manière simplement exponentielle[1].

Deux théorèmes d'« accélération » dus à Imbert[2] permettent d'éliminer des inégalités redondantes du système en se basant uniquement sur des propriétés syntaxiques de l'arbre de dérivation des formules, et donc sans recours à la programmation linéaire ou à des calculs de rangs matriciels. Quelques définitions sont nécessaires avant de pouvoir énoncer ces résultats.

L'historique ${\displaystyle H_{i}}$ d'une inégalité ${\displaystyle i}$ du système est définie comme l'ensemble des indices des inégalités du système initial ayant servi à générer ${\displaystyle i}$. Les inégalités ${\displaystyle i\in S}$ du système initial vérifient tout d'abord ${\displaystyle H_{i}=\{i\}}$. Lors de l'ajout d'une nouvelle inégalité ${\displaystyle k:A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}$ (par élimination de ${\displaystyle x_{r}}$), l'historique ${\displaystyle H_{k}}$ est ensuite construite comme ${\displaystyle H_{k}=H_{i}\cup H_{j}}$.

Supposons que les variables ${\displaystyle O_{k}=\{x_{r},\ldots ,x_{r-k+1}\}}$ ont été éliminées du système. Chaque inégalité ${\displaystyle i}$ du système actuel partitionne l'ensemble des variables éliminées ${\displaystyle O_{k}}$ en :

• ${\displaystyle E_{i}}$, l'ensemble des variables effectivement éliminées. Une variable ${\displaystyle x_{j}}$ est effectivement éliminée pour ${\displaystyle i}$ dès lors qu'au moins une des inégalités dans l'historique ${\displaystyle H_{i}}$ a été obtenue par élimination de ${\displaystyle x_{j}}$.
• ${\displaystyle I_{i}}$, l'ensemble des variables implicitement éliminées. Une variable est dite implicitement éliminée dès lors qu'elle apparaît dans au moins une des inégalités de l'historique ${\displaystyle H_{i}}$, sans apparaître dans ${\displaystyle i}$ ni être effectivement éliminée.
• ${\displaystyle A_{i}}$, les variables restantes.

Toute inégalité non-redondante a la propriété que son historique est minimale[3].

Une inégalité ne satisfaisant pas l'encadrement ci-dessus est nécessairement redondante et peut être éliminée du système sans changer l'ensemble des solutions.

Le second théorème fournit quant à lui un critère pour détecter les historiques minimales :

Ce théorème permet d'éviter de calculer d'autres vérifications plus coûteuses, telles que les éliminations basées sur des calculs de rangs matriciels. De plus amples détails d'implémentation sont donnés en référence[3].

• Joseph Fourier, Mémoires de l'Académie des sciences de l'Institut de France, vol. 7, Gauthier-Villars, 1827, xlvi–lv (lire en ligne)
• Theodore Motzkin, The Theory of Linear Inequalities, 1952 (lire en ligne)
• (en) Alexander Schrijver, Theory of Linear and Integer Programming, John Wiley & sons, 1998, 155–156 p. (ISBN 0-471-98232-6, lire en ligne)
• H. P. Williams, « Fourier's Method of Linear Programming and its Dual », American Mathematical Monthly, vol. 93, n^o 9,‎ 1986, p. 681–695 (DOI 10.2307/2322281)

• Portail de l'informatique théorique