## Tuesday, January 10, 2012

### Fourier–Motzkin elimination

Fourier–Motzkin elimination, FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can look for both real and integer solutions. Its computational complexity is double-exponential.
Elimination (or ∃-elimination) of variables V from a system of relations (here, linear inequalities) consists in creating another system of the same kind, but without the variables V, such that both systems have the same solutions over the remaining variables.
If one eliminates all variables from a system of linear inequalities, then one obtains a system of constant inequalities, which can be trivially decided to be true or false, such that this system has solutions (is true) if and only if the original system has solutions. As a consequence, elimination of all variables can be used to detect whether a system of inequalities has solutions or not.

Let us consider a system S of n inequalities with r variables x1 to xr, with xr the variable to eliminate. The linear inequalities in the system can be grouped into three classes, depending on the sign (positive, negative or null) of the coefficient for xr:
• those that are equivalent to some inequalities of the form $x_r \geq \sum_{k=1}^{r-1} a_k x_k$; let us note these as $x_r \geq A_i(x_1, \dots, x_{r-1})$, for i ranging from 1 to nA where nA is the number of such inequalities;
• those that are equivalent to some inequalities of the form $x_r \leq \sum_{k=1}^{r-1} a_k x_k$; let us note these as $x_r \leq B_i(x_1, \dots, x_{r-1})$, for i ranging from 1 to nB where nB is the number of such inequalities;
• those in which xr plays no role, grouped into a single conjunction ϕ.
The original system is thus equivalent to $\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})) \wedge \phi$.
Elimination consists in producing a system equivalent to $\exists x_r~S$. Obviously, this formula is equivalent to $\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})) \wedge \phi$.
The inequality $\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}))$ is equivalent to nAnB inequalities $A_i(x_1, \dots, x_{r-1}) \leq B_j(x_1, \dots, x_{r-1})$, for $1 \leq i \leq n_A$ and $1 \leq j \leq n_B$.
We have therefore transformed the original system into another system where xr is eliminated. Note that the output system has (n − nA − nB) + nAnB inequalities. In particular, ifnA = nB = n / 2, then the number of output inequalities is n2 / 4.
The operation is named after Joseph Fourier and Theodore Motzkin.