Fourier–Motzkin elimination

Fourier–Motzkin elimination is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can look for both real and integer 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 and Theodore Motzkin.

ee also

* Real closed field: the cylindrical algebraic decomposition algorithm performs quantifier elimination over "polynomial" inequalities, not just linear

References

* 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.

Look at other dictionaries:

  • Elimination — can refer to several things: *When referencing the word in a Reality TV show, it means to vote one off, also known as voting off, consisting of they are out of the game or contest. *In chemistry, an elimination reaction is a one or two step… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia

  • Inequality — In mathematics, an inequality is a statement about the relative size or order of two objects, or about whether they are the same or not (See also: equality) *The notation a < b means that a is less than b . *The notation a > b means that a is… …   Wikipedia

  • Simplex algorithm — In mathematical optimization theory, the simplex algorithm, created by the American mathematician George Dantzig in 1947, is a popular algorithm for numerical solution of the linear programming problem. The journal Computing in Science and… …   Wikipedia

  • Polyedermodell — Das Polytopmodell (oder allgemeiner auch Polyedermodell) ist ein mathematisches Modell, das von Compilern zur Optimierung von Schleifensätzen benutzt werden kann. Dabei werden die Schleifen im Quellprogramm durch Polytope beschrieben, auf die… …   Deutsch Wikipedia

  • Polytopmodell — Das Polytopmodell (oder allgemeiner auch Polyedermodell) ist ein mathematisches Modell, das von Compilern zur Optimierung von Schleifensätzen benutzt werden kann. Dabei werden die Schleifen im Quellprogramm durch Polytope beschrieben, auf die… …   Deutsch Wikipedia

  • Inequality (mathematics) — Not to be confused with Inequation. Less than and Greater than redirect here. For the use of the < and > signs as punctuation, see Bracket. More than redirects here. For the UK insurance brand, see RSA Insurance Group. The feasible regions… …   Wikipedia

  • Category:Optimization algorithms — An optimization algorithm is an algorithm for finding a value x such that f(x) is as small (or as large) as possible, for a given function f, possibly with some constraints on x. Here, x can be a scalar or vector of continuous or discrete values …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.