A brief tutorial on Fourier-Motzkin Elimination

Let’s start with an analogy.

Equality systems : Gaussian elimination :: Inequality systems : ???

According to Kipp Martin, the answer is Fourier-Motzkin Elimination (FME) which allows one to project out variables from a system of linear inequalities. These slides from Thomas Rothvoss nicely illustrate what it means to project out (or eliminate) the variable y.

Note: I don’t particularly like how Gaussian elimination is described (via row operations on a tableau, much like how the simplex method is often described). The intuition is lacking. Instead, everything I describe in this post will work on the (in)equalities themselves.

Eliminating variables in equality systems

Start with the linear equality system

2x+y+z=4
x+2y+z=4
x+y=4.

Proceed by isolating the variable z in each equation that contains z to get

z=4-2x-y
z=4-x-2y
x+y=4.

We can eliminate variable z by setting all “definitions” of z equal to each other (and leaving other equations as is)

4-2x-y=4-x-2y
x+y=4.

Simplifying gives

y=x
x+y=4.

By isolating and then eliminating variable y, we get x=2. Back-substitution gives

x=2
y=x=2
z=4-2x-y=4-4-2=-2.

So the only feasible solution is (x,y,z)=(2,2,-2). Observe that each time a variable is eliminated, one equality is also removed.

Eliminating variables in inequality systems

Suppose we started with the inequality system

2x+y+z\le 4
x+2y+z\ge 4
x+y\le 4.

Isolating z (where possible) gives

z\le 4-2x-y
z\ge 4-x-2y
x+y\le 4.

Matching each of the lower bounds on z with each of its upper bounds (and leaving other inequalities as is), we obtain

4-x-2y\le z\le 4-2x-y
x+y\le 4.

Eliminating z from the string of inequalities gives

4-x-2y\le 4-2x-y
x+y\le 4.

Simplifying gives

x \le y
x+y\le 4.

Isolating y gives

y \ge x
y\le 4-x.

Applying the same procedure to eliminate y, we are left with

x \le 2.

This is the projection of the original feasible set onto the space of the x variable. That is,

  1. for any x\le 2 there exist values for y and z for which the original system is satisfied, and
  2. any point that is feasible for the original system satisfies x\le 2.

Consequences of Fourier-Motzkin Elimination (FME)

FME can test whether a linear program is feasible.

If the system is feasible, FME can provide a feasible solution by employing back-substitution (in accordance with the lower and upper bounds on the variable that is being eliminated). On the other hand, if the original system is infeasible, the final inequality system will have conflicting lower and upper bounds on the final variable such as x \le 0 and x \ge 11 or obvious contradictions like 7 \le 2.

FME can optimize linear programs.

To optimize an LP in which we are to maximize c^T x, simply add a variable z and constraint z\le c^T x to our system and make sure to eliminate z last. The optimality status (e.g., infeasible, unbounded, an optimal solution) can be obtained from the final inequality system. (How?) Note, however, that Fourier-Motzkin elimination is awfully slow (doubly exponential) and is not a practical means to solve LPs. (But, there is also a singly exponential elimination method.)

Projections of polyhedra are also polyhedra

If we eliminate a variable from a system with m inequalities, then we end up with a system of at most m^2/4 inequalities. So, if we start with a finite number of inequalities and variables, then any projection will have finitely many inequalities. (FME may give redundant inequalities, which is okay.)

Projections of rational polyhedra are also rational

If every coefficient and right-hand-side in our original inequality system is rational, then they will remain rational after a variable is eliminated.

Other results

More consequences follow by FME, see Kipp Martin’s book. In fact, he develops the basics of LP (e.g., Farkas’ lemma and duality) via projection (FME) and “inverse projection.”

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s