Fourier–Motzkin elimination
Fourier Motzkin elimination is a method for projecting a given by a linear inequality convex polyhedron onto a hyperplane of the mold. Here, a matrix and a suitable right side.
The method was described by Joseph Fourier in 1827 for the first time, but was forgotten and was eventually rediscovered in the PhD thesis of Theodore Motzkin 1936.
Description of the procedure
The algorithm combines the rows of the matrix, and the entries in the right side conical new inequalities. This is done in a way that ensures that the resulting new inequalities include the variable is no longer.
The algorithm is described by the following pseudocode:
FourierMotzkin function (a, b, j) is Input: a matrix of the dimension of a vector of dimension and an index j Output: a matrix of dimension such that for all and a vector with entries indexing of the elements in, ie a bijection for to do if then else if then endif endfor return The resulting polyhedron then describes the desired projection [A. 1].
For example for the Fourier Motzkin elimination
As an example we choose the polyhedron is given by the following inequality:
The corresponding matrix and right side are therefore
For the projection onto the hyperplane, in other words for, we obtain the following amounts:
Thus, and. We set.
For we combine the first and second inequality:
For we obtain by combining the first and third inequality the following new inequality:
The image of the projection is given by Thus, while the resulting matrix or the right side have the following form:
The Fourier - Motzkin elimination from the viewpoint of linear algebra
The algorithm used in the line operations can also be multiplication of the matrix or the right side with a matrix showing, whose th row is given by
Since the matrix describes a conical combination of the rows of all entries of are nonnegative. In the above example
Applications
Admissibility problems
The Fourier - Motzkin elimination is a projection method the property that the system has a solution then if this is true exactly on the system.
While it is generally difficult to decide whether a convex polyhedron has a feasible solution, this can be quite easily accomplished in a few special cases:
- A variable remains in the resulting system, therefore is the zero matrix, the system is then, and only then solved if the right hand side is not negative
- Contains only one associated with a variable column of the matrix of non-zero entries, so the projection corresponds to an interval. If it is not empty, and the system can be solved. Furthermore, the possible values of the variables in the polyhedra are just given by the interval
This knowledge can be exploited to check whether any polyhedron has a feasible solution or not: First of all variables are projected out in sequence:
The resulting matrix is then the zero matrix, and you can decide whether, for iff. .
In particular iff. .
Since the - th projection step can be carried out by a multiplication by a non-negative matrix, also applies:
If the- th entry of is negative, it is and where. This statement corresponds to the Farkas ' lemma. Since the matrices can be set up during the execution of the algorithm, the Fourier - Motzkin elimination thus offers the possibility to calculate the certificate for explicitly.
Additionally implies the Fourier Motzkin elimination that the projection of a polyhedron is a polyhedron again. This result can be used to determine the equivalence of the - to show and display of polyhedra.
Example, the decision of admissibility
We want to decide whether the following convex polyhedron has a feasible solution:
This corresponds in shape to the system
After the individual projection steps, the following systems result:
It reveals a contradiction of the polyhedra corresponding to the empty set. The resulting matrices are given by
A certificate for non- admissibility is therefore the vector.
Solution of linear programs
By exploiting the duality of linear programming can be any linear program reduced to a problem of admissibility which can be solved by applying the Fourier - Motzkin elimination then. In this case, however, it requires quite a lot of new variables and inequalities, which slows down the application of the method. Alternatively, you can choose the following approach: To solve the problem, one introduces an additional variable, and calls in addition that. The value of the variable is thus limited by the optimal solution of the problem. This gives a polyhedron with
We then projected the first entries out, so that one finally, a system of the form
Receives. The resulting interval describes the set of possible values for the variable. You experience the following cases:
In order to obtain a solution with a given objective function value, proceed as follows: First, we consider the system after the th iteration: it occurred only on the variables and where the value is determined by forward to:
This yields a ( non-empty ) interval of possible solutions, from which one selects any. This process is iterated for [A. 2].
Example of solving a linear program
To illustrate the procedure, we select the program
To solve the problem, we add the variable together with the inequality to the problem. The following systems show the polyhedron, and the changed system on and after the projection:
It is therefore clear that the optimal solution of the problem has the objective function value 4. In order to obtain a corresponding solution, we set and return to the penultimate step. This results in the system
So there is no other choice than to set. The value of results ultimately from the system
This is the optimal solution. This of course also has the expected objective function value of.
Term
Although the Fourier - Motzkin elimination can be used for solving linear programs, it is in practice other algorithms to preference. The problem of the Fourier Motzkin elimination is that in the worst case, the number of the inequalities or the size of the matrices to each projection step of previously on increases. In this case, the running time of the algorithm is no longer tractable. In general, besides, most of the inequalities generated are redundant. However, since this can not be detected efficiently in general, far more memory for the Fourier - Motzkin elimination used than is necessary to describe the polyhedron.