Determining the number of solutions of a system of linear inequalities.
I want to determine the number of solutions of a system of linear inequalities, and I was wondering if there was a simple way to to that. I know that linear programming is often used to check whether there are a zero or non-zero number of solutions, i.e. if the system/bounds is/are feasible, but is it possible to distinguish between there being a finite amount of unique solutions or infinitely many solutions? For instance, the system$$ \begin{array}{lcl} x & \leq & y \\ x & \geq & y \\ x + y & \leq & 1 \\ x + y & \geq & 1 \end{array} $$
has 1 unique solution, namely $x=y=\frac{1}{2}$, while the system
$$ \begin{array}{lcl} x & \geq & y \\ x + y & \leq & 1 \\ x + y & \geq & 1 \end{array} $$
has infinitely many solutions. Is there a away to find out how many solutions a system of linear inequalities has, if any?
$\endgroup$ 63 Answers
$\begingroup$As @Milten noted in the comments, the number of solutions to a system of linear inequalities (over $\mathbb{R}$) may only be $0,1$ or infinite. This is because of convexity: if $v,w$ are two solutions, then $\alpha v + (1-\alpha)w$ is a solution for any $0 \leq \alpha \leq 1$, and for $v \neq w$ this gives an infinite number of solutions. This means that you only need to find two distinct solutions to decide whether there is an infinite number of them.
As you say, linear programming can be used to decide whether there is any solution, but with a bit more work it can also tell you whether there are multiple solutions or just one. Heuristically, you can use linear programming to maximize a random objective function $c\cdot x$ over the feasible region; one would expect that if the feasible region has more than one points then with high probability you would obtain multiple solutions. Granted, this is just a heuristic, but for practical purposes it should be good enough. (See also this answer.)
For an honest polynomial-time algorithm to decide whether the solution is unique you may want to take a look at this article, in which the authors reduce the problem of deciding uniqueness to finding the solution to another linear program. The article also contains a survey of previous results on this problem. Sadly, all the (legal) links I could find to the article are paywalled. If you would like to, I can describe their solution in more detail.
Finally, I would just like to note that in general you "can't avoid" linear programming in the sense that deciding whether there is at least one solution to a linear program is almost as difficult as finding an optimal solution. This is true in the sense that if you can decide whether there is a solution, then you can use a binary search-like algorithm to find an optimal solution in reasonable time.
$\endgroup$ 2 $\begingroup$The techniques for solving systems of linear inequalities differ from those for linear equations because the inequality signs do not allow us to perform substitution as we do with equations. Many of the concepts we learned when studying systems of linear equations translate to solving a system of linear inequalities, but the process can be somewhat difficult. Perhaps the most lucid way to simultaneously solve a set of linear inequalities is through the use of graphs. The solution to the system is all the points that satisfy both inequalities or the region in which the shading overlaps.
A system of linear inequalities in two variables consists of at least two linear inequalities in the same variables. It involves several expressions that, when solved, may yield a range of solutions. The solution of a linear inequality is the ordered pair that is a solution to all inequalities in the system. For a system of linear inequalities, there is only one solution set which can contain any number of solutions, or no solution.
To find the number of solution sets, we use the graphical representation of the inequalities, and shades in the values which satisfy each separate inequality. By visually representing the potential values of each one, we shall quickly notice if there be an overlap. Wherever the shading overlaps, it is said to be the solution set for the system. If they do not overlap, there is no solution to the system. For example, consider two parallel lines. If the solution to one are the values above the line, and the solution to the other one are the values below the other line, there is no intersection and therefore there is also no solution to the system.
The following links (and the links therein) may give the idea of some algorithm to solve the linear inequality.
Algorithm for finding integer solutions for linear inequalities
Solving a system of linear inequalities — what is the dimension of the solution set?
Firstly, let us present the inequality system in the unified form. For example,\begin{cases} -x+y\ge 0\\ x-y\ge 0\\ -x-y+1\ge0\\ x+y-1\ge0\\ x+3y-2\ge0,\tag1 \end{cases}$$L_k(x,y,1)\ge 0, \quad k=1,2,\dots,5.$$
Easily to see, that
- $L_1+L_2=0,\;$ i.e. the sum of non-negative values equals to zero. Then should $L_1=L_2=0.\;$ Therefore, we have the equation instead the pair of the inequalities.
- Similarly $L_3+L_4=0,\;\Rightarrow\;L_3=L_4=0.$
- $L_2+2L_3+L_5 = 0,\;$i.e. the positive linear combination of non-negative values equals to zero. Then should overdefined $L_2=L_3=L_5 =0,$ and really we have two independent equalities instead of three inequalities.
- $L_5 =L_1+2L_4,\;$ i.e. inequality $(1.5)$ follows from the pair $(1.1),(1.4)$ and can be eliminated.
Finally, we have the system $\;L_1=L_3=0,\;$ with the rank $2$ and the single solution.
In the common case, the Jordan algorithm can be applied additionally. Finally, this leads to the inequality system for 'independent' unknowns and the set of the linear functions for the others.
Since the system $(1)$ is presented in the homogenius form, then solutions can exist only if its matrix has rank $2$ or less, and any three expressions $\;L_k\;$are linearly dependent. The similar situation takes place also in the common case.
$\endgroup$
