Final Solution of Fourier-Motzkin

Question

For the following exercise:

=======================================================
-oo <= -1 x[0] + 1 x[1] + 3 x[2] <= 1
-oo <= -2 x[0] + -4 x[1] + 1 x[2] <= 3
-oo <= -2 x[0] + 2 x[1] + 4 x[2] <= 4
-4 <= -3 x[0] + 1 x[1] + 3 x[2] <= -4
4 <= 1 x[0] + 3 x[1] + 4 x[2] <= +oo
=======================================================

the solution of the online tool is the following:

=======================================================
     -oo <= (2/3) x[0] <= (5/3)
     -oo <= 0 x[0] <= 0
     -oo <= (36/13) x[0] <= 15
     -oo <= (8/5) x[0] <= (62/5)
     -oo <= (48/19) x[0] <= (274/19)
     -oo <= 0 x[0] <= 14
     -oo <= 0 x[0] <= (42/5)
=======================================================
Eliminated variable x[0] which is not both-bounded:
=======================================================
     -oo <= 0 <= 0
     -oo <= 0 <= 14
     -oo <= 0 <= (42/5)
=======================================================
The final constraints are satisfiable.
A solution will be computed while returning from recursive calls.
    Computed solution x[0] := (5/2)
    Computed solution x[1] := (13/2)
    Computed solution x[2] := -1
The given linear inequalities are solved!

I understand why x0 = 5/2 and x1 =13/2 and x2 = -1 are a working solution.
However, when I try to choose another value for x0 and calculate x1 and x2 from it, it is not accepted by the exercise system. 

I tried using:

x0 = 7,75
x1 = -9,25
x2 = -18,5

which I got from the line: -oo <= (8/5) x[0] <= (62/5)

Is this also a solution which the exercise system just doesn't accept or is there something wrong with this solution?

Also another question:
Why is the step
Eliminated variable x[0] which is not both-bounded:
=======================================================
     -oo <= 0 <= 0
     -oo <= 0 <= 14
     -oo <= 0 <= (42/5)
=======================================================
needed? Do we need to check if any of the formulas is wrong?

What happens if one of the formulas is like this: -oo <= 0 <= -4 
This is obviously wrong. Do we stop then and say that no solution can be found?

Answer 1

First question: Your suggested solution (x0,x1,x2) = (7.75, -9.25, -18.5) is not correct since -3.0 * x0 + 1.0*x1 + 3.0*x2 = -88.0 which does not satisfy the inequations -4 <= -3 x[0] + 1 x[1] + 3 x[2] <= -4. I also don't see how you got that from just one line.

Second question: Yes, you have to check the final constraints for being true. If they would not be true, there would be no solution, otherwise, there is one. Since the final variable x[0] has only upper bounds, it is however already clear that there is a solution, namely the minumum of the right hand sides, and seeing this, you may skip that final step. If there would be however both lower and upper bounds, you have to check for a solution (which may not exist in that case).

Comments

Thanks for your answer. Did I then understand this correctly that for x[0] (and also the other x-values when calculating backwards) we always choose the lowest upper bound? And this would also mean that there is only one possible solution for the inequations that we can compute?

---

No not really. As you can check on slide 88, we generally can choose a solution within an interval [s0,s1] where s0 is the maximum of all lower bounds and s1 is the minimum of all upper bounds. You can choose any number of that interval.

In case there is only one such bound given (and the interval is open on one end), you can also choose any value from that interval. So, there is not a unique solution, but we may agree on always choosing the minimum of the upper bounds if the exist, and only if these should not exits, we may choose the maximum of the lower bounds. Thus, we could determine an algorithm that computes a unique solution (as the teaching tool does), but one may write another algorithm, of course. For example, you can choose the middle of the interval [s0,s1] also.