- Fourier–Motzkin elimination
Fourier–Motzkin elimination is a mathematical
algorithm for eliminating variables from asystem of linear inequalities . It can look for both real andinteger solutions. It is computationally expensive.Elimination (or exists-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 x_1 to x_r, with x_r 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 x_r:
* 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 n_A where n_A 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 n_B where n_B is the number of such inequalities;
* those in which x_r plays no role, grouped into a single conjunction phi.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, the above 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 n_A n_B 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 x_r is eliminated. Note that the output system has n-n_A-n_B)+n_A n_B inequalities. In particular, if n_A = n_B = n/2, then the number of output inequalities is n^2/4.
The operation is named after
Joseph Fourier andTheodore Motzkin .ee also
*
Real closed field : the cylindrical algebraic decomposition algorithm performs quantifier elimination over "polynomial" inequalities, not just linearReferences
* Alexander Schrijver, "Theory of Linear and Integer Programming". John Wiley & sons, 1998, ISBN 0-471-98232-6, pp. 155-156
* Keßler, Christoph W., "Parallel Fourier–Motzkin Elimination", Universität Trier [http://citeseer.ist.psu.edu/71579.html Citeseer page]----
Wikimedia Foundation. 2010.