( Fourier-Motzkin’s Method )

Compatible Systems of Linear Inequalities

( Fourier-Motzkin’s Method )

Claudio Arbib

Università degli Studi di L’Aquila

Contents

1. Polyhedra

2. Implied inequalities 3. Compatible polyhedra 4. Projecting a polyhedron

Definitions Examples

5. Fourier’s Theorem

6. Fourier-Motzkin’s Algorithm

7. Applications

1. Polyhedra

Definition:

Let a ∈ IR

, b ∈ IR. The set

H = {x ∈ IR

: ax = b} ⊆ IR

is called a hyperplane.

The set

S = {x ∈ IR

: ax < b} ⊆ IR

is called a closed halfspace.

Definition:

A polyhedron is the intersection of a finite set of m closed halfspaces in IR

. So ∀ A ∈ IR

, b ∈ IR

the set

P (A, b) = {x ∈ IR

: Ax < b} ⊆ IR

defines a polyhedron. In particular, ∅, H, S, IR

are polyhedra.

2. Implied inequalities

Definition:

A linear inequality β β β βx ≤ γ is implied by the system Ax ≤ b if every x such that Ax ≤ b verifies also β β βx ≤ β γ

3x

+ x

≤ 1

x₁ x₂

P

x

≥ 0 x

+ 2x

≤ 1

x

≥ 0

2.5x

+ 2.5x

≤ 1.5

Implied inequalities

Definition:

A system of linear inequalities is minimal if it does not contain any implied inequality

Definition:

β β β

βx ≤ γ is a conic combination of the inequalities in Ax ≤ b ≡ ≡ ≡ {a ≡

x ≤ b

, i = 1, …, m}

if and only if

(β β β, γ) = β λ

(a

, b

) λ

≥ 0 Theorem:

Every linear inequality obtained as a conic combination of those in Ax ≤

b is an implied inequality

1( ) +

0.5( ) =

0( ) +

0( ) +

2.5x

+ 2.5x

≤ 1.5

Implied inequalities

Example:

3x

+ x

≤ 1 x

≥ 0 x

+ 2x

≤ 1

x

≥ 0

x1

x₂

P

2.5x

+ 2.5x

≤ 1.5

λ λ λ

λ = (1, 0.5, 0, 0)

3. Compatible polyhedra

Definition:

A polyhedron is said to be compatible (incompatible) if it (does not) admit a solution

Problem:

Decide whether a given polyhedron P(A, b) is compatible or not Principle:

All that exists, has a shade

(Corollary: vampires do not exist)

4. Projecting a polyhedron

Definition: Let P(A, b) ⊆ IR

be a polyhedron.

Then the polyhedron P(A’, b’) ⊆ IR

is a projection of P(A, b) if x ∈ P(A’, b’) ⇔ ∃z ∈ IR such that (x, z) ∈ P(A, b).

Example:

P : x

> 0, x

> 0, 3x

+ 2x

< 6 P’ : 0 < x

< 2

set z = (6 – 3x

)/2 > 0 ∀x

∈ P’

clearly (x

, (6 – 3x

)/2) ∈ P ∀x

∈ P’

Projecting a polyhedron

Example:

P : x

> 0 x

> 0 3x

+ 2x

< 6

P’ : 0 < x

< 2

∀x

∈P’, ∃z: (x

, z) ∈P P’ is a projection of P

P

P’

Projecting a polyhedron

Example:

P : x

> 0 x

> 1 3x

+ 2x

< 6

P’ : 0 < x

< 2

∃ x ∈ P such that x

= 2

P’ is not a projection of P

P

P’

Projecting a polyhedron

Example:

P : x

> 0 x

> 1 3x

+ 2x

< 6

P’ : 0 < x

< 4/3

Is P’ a projection of P?

P

P’

Projecting a polyhedron

Example:

P : x

> 0 x

> 1 3x

+ 2x

< 6

P’ : 0 < x

< 1

Is P’ a projection of P?

P

P’

5. Fourier’s Theorem

Consider the polyhedron P

a

x

+ a

x

+ … + a

x

< b

a

x

+ a

x

+ … + a

x

< b

…

a

x

+ a

x

+ … + a

x

< b

Partition the row set R in 3 subsets:

R

= {i ∈ R: a

= 0}, R

= {i ∈ R: a

> 0}, R

= {i ∈ R: a

< 0}

Construct a new polyhedron P’ containing:

1) all the inequalities in R

2) a new inequality for any pair in R

× R

Fourier’s Theorem

• Any inequality of type (2) corresponds to one row h ∈ R

and another k

∈ R

a

x

+ a

x

+ … + a

x

< b

a

x

+ a

x

+ … + a

x

< b

a

a

( ^{+ a}

) ^x

⁺ ( ⁺ ) ^x

^{+ … +} ( ⁺ ) ^x

< ( ⁺ )

|a

|

a

a

a

|a

|

a

a

a

|a

|

b

a

b

|a

|

row h row k

• The inequality of P’ is a special conic combination of these two inequalities, obtained by

– dividing the former by a_h

1

– dividing the latter by |a_k1| – summing them up

Fourier’s Theorem

Observation: The new system P’ of linear inequalities does not contain variable x

Theorem (Fourier) P’ is a projection of P in the space of variables x

, …, x

.

Proof

• Let w = (w

, …, w

) ∈ P’. We must show that there exists a real z such that (z, w

, …, w

) ∈ P.

• For any i ∈ R

one has a

w

+ … + a

w

< b

• Moreover for any h ∈ R

, k ∈ R

( ^a

⁺ ) ^w

^{+ … +} ( ⁺ ) ^w

< ( ⁺ )

a

a

|a

|

a

a

a

|a

|

b

a

b

|a

|

Fourier’s Theorem

• Rewrite the latter condition

+ … + – < – ^a

^w

– … –

a

a

w

|a

|

a

w

a

a

w

|a

|

b

a

b

|a

|

• As k ranges in R

(as h ranges in R

) the left (right) had side describes a class C (a class D) of real numbers, and all the elements of C turn out to be < than those of D

• Hence there exists a separating element z such that:

+ … + – ^{< z}

a

w

|a

|

a

w

|a

|

b

|a

| ∀k ∈ R

z < – ^a

^w

–

a

a

w

a

b

a

∀h ∈ R

Fourier’s Theorem

• The latter two inequalities rewrite:

a

z + a

w

+ … a

w

< b

∀k ∈ R

• Also, ∀i ∈ R

one has

a

z + a

w

+ … a

w

< b

∀h ∈ R

0z + a

w

+ … a

w

< b

• Therefore (z, w

, …, w

) ∈ P

• To complete the proof, vice-versa, we must show that for any w ∉ P’

there is no z ∈ IR such that (z, w) ∈ P.

Fourier’s Theorem

• Saying w ∉ P’ means to say

a

w

+ … a

w

> b

for some i ∈ R

for some (h, k) ∈ R

×R

• In the first case, the corresponding inequality of P is obviously violated

• In the second, there is an element of class C which is greater than an element of class D, thus these classes do not have any separator z.

End of proof

+ … + – ^> – ^a

^w

– … –

a

a

w

|a

|

a

w

a

a

w

|a

|

b

a

b

|a

|

D

C ∋

, or

• To complete the proof, vice-versa, we must show that for any w ∉ P’

there is no z ∈ IR such that (z, w) ∈ P.

6. Fourier-Motzkin’s Algorithm

• Fourier’s Theorem allows us to reduce the problem of deciding whether a polyhedron is empty or not to that of deciding whether one of its

projections is such

• Because the projection of a polyhedron still is a polyhedron, the theorem can be repeatedly applied, until one finds a polyhedron where the

decision problem is trivial

• For instance, one can apply the theorem n – 1 times: in this case the resulting polyhedron P

will be an interval of the real axis, possibly empty or unbounded

• Or, one can apply the theorem n times: in this case the resulting

polyhedron P

will be of the form 0·x < t. Two cases are then possible:

– if t > 0, P⁽ⁿ⁾ is trivially compatible, since it describes the whole IRⁿ, and so also P is compatible;

– If there exists an index i such that t_i < 0, then P⁽ⁿ⁾ is trivially incompatible, and so is P.

7. Applications

• The repeated application of Fourier’s Theorem is, in fact, Fourier- Motzkin’s Elimination Method

• This method can be applied to

– decide whether a polyhedron is empty or not

– find an implicit representation of conv(S) for any finite set S ⊂ IRⁿ – solve a linear program

Example

Let P be the polyhedron of the x ∈ IR

such that

3x

– x

< 4

x

– 2x

< – 6 2x

+ 2x

+ x

< 2

x

> 0

We want to check P ≠

Example

Change all the inequalities into <, and build a table containing all the system coefficients

1) 3 – ^{1 0 4}

2) 1 0 –2 –6

3) 2 2 1 2

4) –1 0 0 0

(red = right-hand side, blue = row indexes)

Example

Select a variable (column) to be suppressed. The choice can be based on the number of new rows that the suppression will generate.

• Eliminating column 1 we generate 3×1 = 3 new rows

• Eliminating column 2 or column 3 we generate 2 + 1×1 = 3 new rows

So we decide to suppress column 2, in fact 2 of the new rows derive from R

, and are therefore already present in the table

1) 3 – ^{1 0 4}

2) 1 0 –2 –6

3) 2 2 1 2

4) –1 0 0 0

Example

The sets R

, R

and R

are then the following:

S

= {2, 4} S

= {3} S

= {1}

Hence, R

× R

contains pair 31 only. The relevant row is computed by multiplying row 1 by 2 and by summing the result to row 3. The table becomes

1) 3 – 1 0 4

2) 1 0 –2 –6

3) 2 2 1 2

4) –1 0 0 0

2) 1 0 –2 –6

4) –1 0 0 0

31) 8 0 1 10

Example

It is now convenient to apply the method to column 3. We have R

= {2}, R

= {3}, R

= {1}

and R

× R

again contains only pair 31.

The relevant row is computed by multiplying row 3 by 2 and summing up the result to row 1. The table now becomes

1) 1 0 –2 –6

2) –1 0 0 0

3) 8 0 1 10

Re-number the rows so obtained

2) –1 0 0 0

31) 17 0 0 14

Example

The projection P” of P on the x

axis consists then of the (non-empty) interval [0, 14/17]. Then, also P is non-empty. In particular we can find a point of P by choosing any x

∈ P”, and computing x

and x

from the previous tables.

Take for example x

= 0. From the first table in the previous page we derive the conditions

1) x

> 0

2) 17x

< 14

This table describes the system

1) –2x

< –6 that is x

> 3

3) x

< 10

Hence x

∈[3, 10]. We can for instance choose x

= 4.

Example

Replacing now x

= 0 and x

= 4 in the initial table

1) 3 –1 0 4

2) 1 0 –2 –6

3) 2 2 1 2

4) –1 0 0 0

we obtain the conditions

–x

< 4

2x

+ 4 < 2

namely x

∈[–4, –1]. A solution of the initial system is then, for instance

x

= 0 x

= –1 x

= 4