Fourier-Motzkin Elimination

The Fourier-Motzkin elimination is a method by a given by a linear inequality convex polyhedron to a hyperplane of the mold to project . There is a matrix and a matching right side. ${\displaystyle P(A,b):=\{x\;|\;Ax\leq b\}}$ ${\displaystyle H:=\{x\;|\;x_{j}=0\}}$ ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ ${\displaystyle b\in \mathbb {R} ^{m}}$

The process was first described by Joseph Fourier in 1827, but was forgotten and was finally rediscovered in 1936 in Theodore Motzkin's doctoral thesis .

Description of the procedure

The algorithm conically combines the rows of the matrix and the entries on the right-hand side to form new inequalities. This is done in a way that ensures that the resulting new inequalities no longer include the variable . ${\displaystyle A_{i\cdot }\ i\in M:=\{1\ldots m\}}$ ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle x_{j}}$

The algorithm is described by the following pseudocode :

 function FourierMotzkin(A, b, j) is
     Eingabe: eine Matrix  ${\displaystyle A}$ der Dimension  ${\displaystyle (m,n)}$, ein Vektor  ${\displaystyle b}$ der Dimension  ${\displaystyle m}$
              und ein Index j  ${\displaystyle \in \{1,\ldots ,n\}}$
     Ausgabe: eine Matrix  ${\displaystyle D}$ der Dimension  ${\displaystyle (r,n)}$, sodass  ${\displaystyle D_{ij}=0}$ für alle  ${\displaystyle i=1,\ldots ,r}$
              und ein Vektor  ${\displaystyle d}$ mit  ${\displaystyle r}$ Einträgen

      ${\displaystyle Z\leftarrow \{i\in M\;|\;a_{ij}=0\}}$
      ${\displaystyle N\leftarrow \{i\in M\;|\;a_{ij}<0\}}$
      ${\displaystyle P\leftarrow \{i\in M\;|\;a_{ij}>0\}}$
      ${\displaystyle R\leftarrow Z\cup (N\times P)}$
      ${\displaystyle r\leftarrow |R|}$
      ${\displaystyle p\leftarrow }$ eine Indizierung der Elemente in  ${\displaystyle R}$, also eine Bijektion  ${\displaystyle p:\{1,\ldots ,r\}\rightarrow R}$

     for  ${\displaystyle i=1}$ to  ${\displaystyle r}$ do
         if  ${\displaystyle p(i)\in Z}$ then
              ${\displaystyle D_{i\cdot }\leftarrow A_{p(i)\cdot }}$
              ${\displaystyle d_{i}\ \leftarrow b_{p(i)}}$
         else if  ${\displaystyle p(i)=(s,t)\in N\times P}$ then
              ${\displaystyle D_{i\cdot }\leftarrow a_{tj}A_{s\cdot }-a_{sj}A_{t\cdot }}$
              ${\displaystyle d_{i}\ \leftarrow a_{tj}b_{s}-a_{sj}b_{t}}$
         endif
     endfor
     return  ${\displaystyle (D,d)}$

The resulting polyhedron then describes the desired projection. ${\displaystyle P(D,d)}$

Example for the Fourier-Motzkin elimination

The projection of a polyhedron onto different (linear) hyperplanes

As an example we choose the polyhedron given by the following system of inequalities: ${\displaystyle P(A,b)}$

${\displaystyle P(A,b)=\{(x,y)\in \mathbb {R} ^{2}\ |\ x\geq 1,\ 2x+4y\leq 14,\ x-2y\leq -1\}}$

The corresponding matrix and right side are therefore

${\displaystyle A=\left({\begin{array}{rr}-1&0\\2&4\\1&-2\\\end{array}}\right),\ b=\left({\begin{array}{r}-1\\14\\-1\\\end{array}}\right)}$

For the projection onto the hyperplane , i.e. for , we get the following quantities: ${\displaystyle x=0}$ ${\displaystyle j=1}$

${\displaystyle Z=\emptyset }$, and . ${\displaystyle N=\{1\}}$ ${\displaystyle P=\{2,3\}}$

So is and . We set . ${\displaystyle r=2}$ ${\displaystyle R=\{(1,2),\ (1,3)\}}$ ${\displaystyle p(1)=(1,2),\ p(2)=(1,3)}$

For we combine the first and second inequality: ${\displaystyle i=1}$

${\displaystyle 2\cdot (-x)-(-1)\cdot (2x+4y)\leq 2\cdot (-1)-(-1)\cdot (14)\;\Longrightarrow \;4y\leq 12}$

For , combining the first and third inequality, we get the following new inequality: ${\displaystyle i=2}$

${\displaystyle 1\cdot (-x)-(-1)\cdot (x-2y)\leq 1\cdot (-1)-(-1)\cdot (-1)\;\Longrightarrow \;-2y\leq -2}$

The image of the projection is thus given by , while the resulting matrix or the right side have the following shape: ${\displaystyle \{(0,y)\in \mathbb {R} ^{2}\ |\ 1\leq y\leq 3\}}$ ${\displaystyle D}$ ${\displaystyle d}$

${\displaystyle D=\left({\begin{array}{rr}0&4\\0&-2\\\end{array}}\right),\ d=\left({\begin{array}{r}12\\-2\\\end{array}}\right)}$

The Fourier-Motzkin Elimination from the point of view of linear algebra

The row operations used in the algorithm can be represented by multiplying the matrix or the right-hand side with a matrix whose -th row is given by ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle U\in \mathbb {R} _{+}^{r\times m}}$ ${\displaystyle i}$

${\displaystyle U_{i\cdot }={\begin{cases}e_{k}&{\text{falls }}p(i)=k\in Z\\a_{tj}e_{s}-a_{sj}e_{t}&{\text{falls }}p(i)=(s,t)\in N\times P\\\end{cases}}}$

Since the matrix describes a conical combination of the rows of , all entries of are not negative. In the example above, ${\displaystyle U}$ ${\displaystyle A}$ ${\displaystyle U}$

${\displaystyle U=\left({\begin{array}{rrr}2&1&0\\1&0&1\\\end{array}}\right)}$

Applications

Admissibility Issues

As a projection method, the Fourier-Motzkin elimination has the property that the system has a solution precisely when this also applies to the system . ${\displaystyle Ax\leq b}$ ${\displaystyle Dx\leq d}$

While it is generally difficult to decide whether a convex polyhedron has a feasible solution, in some special cases it is quite easy to do:

• Remains not a variable in the resulting system , so it is the zero matrix , the system is then and only then solved if the right side is not negative ${\displaystyle Dx\leq d}$ ${\displaystyle D}$ ${\displaystyle d}$
• If only a single column of the matrix belonging to a variable contains entries other than zero, the projection corresponds to an interval . If this is not empty, the system can also be solved. Furthermore, the possible values of the variables in the polyhedron just by the interval where ${\displaystyle x_{k}}$ ${\displaystyle D}$ ${\displaystyle I}$ ${\displaystyle Ax\leq b}$ ${\displaystyle x_{k}}$ ${\displaystyle P(A,b)}$ ${\displaystyle I}$

This knowledge can be used to check whether any polyhedron has a feasible solution or not: First, all variables are projected out one after the other: ${\displaystyle P(A,b)}$

${\displaystyle P(A,b)\ {\xrightarrow {{\text{FourierMotzkin}}(A,b,1)}}\ P(D^{(1)},d^{(1)})\ {\xrightarrow {{\text{FourierMotzkin}}(D^{(1)},d^{(1)},2)}}\ P(D^{(2)},d^{(2)})\ \cdots \ P(D^{(n-1)},d^{(n-1)})\ {\xrightarrow {{\text{FourierMotzkin}}(D^{(n-1)},d^{(n-1)},n)}}\ P(D^{(n)},d^{(n)})}$

The resulting matrix is then the zero matrix and you can decide whether , because iff. . ${\displaystyle D^{(n)}}$ ${\displaystyle P(A,b)=\emptyset }$ ${\displaystyle P(A,b)=\emptyset }$ ${\displaystyle P(D^{(n)},d^{(n)})=\emptyset }$

In particular, iff . ${\displaystyle P(A,b)\neq \emptyset }$ ${\displaystyle d^{(n)}\geq 0}$

Since the -th projection step can be carried out by a multiplication with a non-negative matrix , the following also applies: ${\displaystyle j}$ ${\displaystyle U^{(j)}}$

${\displaystyle D^{(n)}=U\cdot A,\ d^{(n)}=U\cdot b,\;{\text{wobei}}\;U:=U^{(n)}\cdot U^{(n-1)}\ldots U^{(1)}}$.

If the -th entry of is negative, then is and , where . This statement corresponds to Farkas' lemma . Since the matrices can be set up during the execution of the algorithm, the Fourier-Motzkin elimination offers the possibility to calculate the certificate for explicitly. ${\displaystyle k}$ ${\displaystyle d^{(n)}}$ ${\displaystyle u\cdot A=0}$ ${\displaystyle u\cdot b<0}$ ${\displaystyle u:=e_{k}\cdot U}$ ${\displaystyle U^{(j)}}$ ${\displaystyle P(A,b)=\emptyset }$

In addition, the Fourier-Motzkin elimination implies that the projection of a polyhedron is a polyhedron again. This result can be used to show the equivalence of the and representations of polyhedra. ${\displaystyle {\mathcal {V}}}$ ${\displaystyle {\mathcal {H}}}$

Example of the decision on admissibility

We want to decide whether the following convex polyhedron has a feasible solution:

${\displaystyle P(A,b)=\{x\in \mathbb {R} ^{2}\ |\ x_{1}+x_{2}\geq 4,\ x_{1}\leq 1,\ x_{2}\leq 1\}}$

This corresponds in form to the system ${\displaystyle Ax\leq b}$

${\displaystyle \left[{\begin{array}{rrr}-x_{1}&-x_{2}&\leq -4\\x_{1}&&\leq 1\\&x_{2}&\leq 1\\\end{array}}\right]\;\;}$

After the individual projection steps, the following systems result:

${\displaystyle \left[{\begin{array}{rr}-x_{2}&\leq -3\\x_{2}&\leq 1\\\end{array}}\right]\;\;\left[{\begin{aligned}0&\leq -2\\\end{aligned}}\right]}$

A contradiction is revealed, the polyhedron corresponds to the empty set. The resulting matrices are given by ${\displaystyle P(A,b)}$

${\displaystyle U^{(1)}=\left({\begin{array}{rrr}1&1&0\\0&0&1\\\end{array}}\right),\;\;U^{(2)}=\left({\begin{array}{rr}1&1\\\end{array}}\right)}$

A certificate for the inadmissibility is the vector . ${\displaystyle e_{1}U^{(2)}U^{(1)}=(1,1,1)}$

Solution of linear programs

By taking advantage of the duality of the linear optimization , each linear program can be reduced to an admissibility problem , which can then be solved by applying Fourier-Motzkin elimination. In this case, however, a large number of new variables and inequalities are required, which slows down the application of the method. Alternatively, one can take the following approach: To solve the problem , one introduces an additional variable and additionally requires that . The value of the variable is therefore limited by the optimal solution to the problem. This gives a polyhedron with ${\displaystyle \max\{c^{T}x\;|\;Ax\leq b\}}$ ${\displaystyle y\in \mathbb {R} }$ ${\displaystyle y\leq c^{T}x}$ ${\displaystyle y}$ ${\displaystyle P({\tilde {A}},{\tilde {b}})}$

${\displaystyle {\tilde {A}}=\left({\begin{array}{rr}A&0\\-c^{T}&1\\\end{array}}\right)\in \mathbb {R} ^{m+1\times n+1},\ {\tilde {b}}=\left({\begin{array}{r}b\\0\\\end{array}}\right)\in \mathbb {R} ^{m+1}}$

You then project the first entries out, so that you finally have a system of form ${\displaystyle n}$

${\displaystyle {\begin{aligned}D_{1,n+1}^{(n)}y&\leq d_{1}^{(n)}\\\vdots &\\D_{l,n+1}^{(n)}y&\leq d_{l}^{(n)}\\\end{aligned}}}$

receives. The resulting interval describes the set of possible values ​​for the variable . The following cases occur: ${\displaystyle I}$ ${\displaystyle y}$

1. The interval is empty. In this case the optimization problem has no feasible solution.
2. There is no upper limit to the interval. The optimization problem is therefore also unlimited.
3. The interval is not empty and has a maximum element . Thus the objective function value of the optimal solution of the problem is exact . ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

In order to obtain a solution with a given objective function value , proceed as follows: First, consider the system after the -th iteration: Only the variables and appear, with the value already set to: ${\displaystyle x^{*}}$ ${\displaystyle y^{*}:=\gamma }$ ${\displaystyle n-1}$ ${\displaystyle y}$ ${\displaystyle x_{n}}$ ${\displaystyle y}$ ${\displaystyle y^{*}}$

${\displaystyle {\begin{aligned}D_{1,n}^{n-1}x_{n}+D_{1,n+1}^{n-1}y&\leq d_{1}^{n-1}\\\vdots &\\D_{l,n}^{n-1}x_{n}+D_{l,n+1}^{n-1}y&\leq d_{l}^{n-1}\\\end{aligned}}}$

One thus obtains a (not empty) interval of possible solutions for , from which one can choose any one. One iterates this process for . ${\displaystyle x_{n}}$ ${\displaystyle x_{n-1},\ldots ,x_{1}}$

Example for solving a linear program

To illustrate the process, we choose the program

${\displaystyle {\begin{aligned}\max ~&x_{1}\\{\text{so dass }}&x_{1}+x_{2}\leq 4\\&x_{1}\geq 0\\&x_{2}\geq 0\\\end{aligned}}}$

To solve the problem, let's add the variable along with the inequality to the problem. The following systems show the polyhedron , as well as the changed systems after the projection on and : ${\displaystyle y}$ ${\displaystyle y\leq x_{1}}$ ${\displaystyle P({\tilde {A}},{\tilde {b}})}$ ${\displaystyle \{x_{1}=0\}}$ ${\displaystyle \{x_{2}=0\}}$

${\displaystyle \left[{\begin{array}{rrrr}x_{1}&+x_{2}&&\leq 4\\-x_{1}&&&\leq 0\\&-x_{2}&&\leq 0\\-x_{1}&&+y&\leq 0\\\end{array}}\right]\;\;\left[{\begin{array}{rr}-x_{2}&\leq 0\\x_{2}&\leq 4\\x_{2}+y&\leq 4\\\end{array}}\right]\;\;\left[{\begin{aligned}0&\leq 4\\y&\leq 4\\\end{aligned}}\right]}$

It is thus certain that the optimal solution to the problem has the objective function value 4. To get an appropriate solution, we bet and return to the penultimate step. The system arises ${\displaystyle y^{*}=4}$

${\displaystyle {\begin{aligned}-x_{2}&\leq 0\\x_{2}&\leq 4\\x_{2}&\leq 0\\\end{aligned}}}$

So there is nothing left but to bet. The value of ultimately results from the system ${\displaystyle x_{2}^{*}=0}$ ${\displaystyle x_{1}^{*}}$

${\displaystyle {\begin{aligned}x_{1}&\leq 4\\-x_{1}&\leq 0\\-x_{1}&\leq -4\\\end{aligned}}}$

This is the optimal solution . Of course, this also has the expected objective function value of . ${\displaystyle (x_{1}^{*},x_{2}^{*})=(4,0)}$ ${\displaystyle y^{*}=4}$

running time

Although Fourier-Motzkin elimination can be used to solve linear programs, in practice other algorithms are preferred. The problem of the Fourier-Motzkin elimination, that the number of inequalities and the size of the matrices in the worst case in every projection step of previously on increases. In this case the running time of the algorithm is no longer polynomial . In general, most of the inequalities generated are also redundant. Since this can usually not be recognized efficiently, however, the Fourier-Motzkin elimination requires far more memory than would be necessary to describe the polyhedra . ${\displaystyle D^{(j)}}$ ${\displaystyle m}$ ${\displaystyle \left({\frac {m}{2}}\right)^{2}}$ ${\displaystyle P(D^{(j)},d^{(j)})}$

Remarks

1. ↑ Since the amount can generally become very large, it is advisable to first scale the inequalities so that for all . To determine and the columns then only have to be subtracted from one another. ${\displaystyle R}$ ${\displaystyle a_{ij}\in \{\pm 1,0\}}$ ${\displaystyle i\in \{1,\ldots m\}}$ ${\displaystyle D}$ ${\displaystyle d}$
2. ↑ The method of backward substitution presented here can always be used to obtain a feasible solution of the polyhedron.

Individual evidence

1. ^ JBJ Fourier from the journal: Analysis des travaux de l'Académie Royale des Sciences pendant l'année 1824, Partie mathématique, 1827.
2. ^ TS Motzkin: Contributions to the theory of linear inequalities.

literature

• Alexander Schrijver : Theory of Linear and Integer Programming . John Wiley & sons, 1998, ISBN 0-471-98232-6 , pp. 155-156.
• HP Williams: Fourier's Method of Linear Programming and its Dual . In: American Mathematical Monthly . 93, 1986, pp. 681-695.
• Unger, Thomas; Dempe, Stefan: Lineare Optimization , pp. 19-23, Vieweg + Teubner 2010, ISBN 978-3-8351-0139-5

Web links

• A lecture script on linear optimization (PDF; 3.5 MB)