Algorithm for solving systems of linear inequaliti

Question

I have k linear inequalities in n variables (0 < k < n). I don't particularly care what the solution set is, I only want to test whether or not it's empty - i.e. whether any assignment to my n variables satisfies the system. Anyone know a way to solve this?

Thanks!

Answer 1

You just need to intersect the ranges. Here's how to in pseudocode:

// An array that has the ranges (inequalities) to test:
fromToArray = [[0, 10], [5, 20], [-5, Infinity]] 

currentRange = [-Infinity, Infinity];
for each pair myRange in fromToArray
   if currentRange[0] < myRange[0] 
          then currentRange[0] = myRange[0]
   if currentRange[1] > myRange[1] 
         then currentRange[1] = myRange[1]
   if currentRange[0] >= currentRange[1]    // from greater than to, so set is empty.
         then return "NO SOLUTION"
end for each

return "Solution is: " + currentRange 

Answer 2

You could use Fourier-Motzkin elimination for solving the system of inequalities. You will need to know basic algebra to understand the solution though.

http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination

Answer 3

Compute the determinant of the related matrix; if it is non-zero there's a unique solution; if it is zero, there are either infinitely many solutions or none - http://en.wikipedia.org/wiki/System_of_linear_equations

Alternatively, use Gaussian elimination - http://en.wikipedia.org/wiki/Gaussian_elimination

Answer 4

Use a SMT solver for the theory of linear arithmetic (Yices, Z3, ...). These programs are designed to find models for the input you specified. Of course, you can also benefit from the existing algorithms in other ways.

Answer 5

This can be done using a linear programming with a constant objective function. That is, only checking for feasibility of the program.