# How to find a solution to an inequality system?

I need to find a solution to the following system of linear inequalities:

\begin{align} x_1-x_2 &\le 1\\ x_1-x_4 &\le -4 \\ x_2-x_3 &\le 2 \\ x_2-x_5 &\le 7 \\ x_2-x_6 &\le 5 \\ x_3-x_6 &\le 10 \\ x_4-x_2 &\le 2 \\ x_5-x_1 &\le -1 \\ x_5-x_4 &\le 3 \\ x_6-x_3 &\le -8 \end{align}

In contrast to my previous question there should be a solution for this system. Is there any systematic way to find a solution?

• Linear programming is designed for this. Commented Nov 26, 2019 at 22:49
• @DonThousand On the contrary, linear programming doesn't find the solution to the inequalities, This would require finding all the vertices of the simplex, rather than just one at which the optimum of the objective function (lacking here) is attained. Commented Nov 26, 2019 at 22:54
• @saulspatz True, I just meant the general style of problem. Commented Nov 26, 2019 at 22:56
• What do you mean by a solution? The solution set is a region in $6$-dimensional space, formed by the intersection of $10$ closed half-spaces. What form do you expect a solution to take that is simpler than what is given? If the solution set turns out to be bounded, it's the convex hull of a finite number of points. Is that what you want? What if the solution set isn't bounded? Commented Nov 26, 2019 at 23:03
• Any one of the infinitely many solutions will do? Commented Nov 26, 2019 at 23:11

Using linear programming (LP) with a constant zero objective, I found the following feasible solution: $$x=(-6, 0, 2, 8, -7, 0).$$

By the way, this LP is the dual of a network LP, hence the constraint matrix is totally unimodular.

This is a linear program without an objective. Algorithms for solving linear programs include the simplex algorithm (Phase I is enough when there is no objective), the ellipsoid algorithm, and many others. https://en.wikipedia.org/wiki/Simplex_algorithm