# Doubt in Fourier-Motzkin algorithm

Can someone please explain how the combination of upper and lower bounds is made here while isolating x1?
Is there a rule for making these combination?

Sure, that is explained on the slides 125-130 of the related chapter and demonstrated with some examples afterwards. In the example that you mention, we find for x1 the lower bounds -1.5+x0 and 1.0 + 1.5*x0 and the upper bounds -0.75 + 0.75*x0 and 3+1.5*x0. To make sure that such an x1 can be found, we can demand that all lower bounds must be less than all upper bound, i.e.,

• -1.5+x0 <= -0.75 + 0.75*x0
• 1.0 + 1.5*x0 <= -0.75 + 0.75*x0
• -1.5+x0 <= 3+1.5*x0
• 1.0 + 1.5*x0 <= 3+1.5*x0

which is equivalent to

• 0.25*x0 <= 0.75
• 1.0 + 0.75*x0 <= -0.75
• -1.5 <= 3+0.5*x0
• 1.0 <= 3

and thus equivalent to (the last inequality is clearly true)

• x0 <= 3
• x0 <= -7/3
• -9 <= x0

Hence, we may now choose an arbitrary value for x0 between -9 and -7/3 which can then be used to compute the inequalities for x1 so that we can also choose a suitable value for x1 to come up with a solution.

by (170k points)