Algorithm for solving systems of linear inequaliti

问题:

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!

回答1:

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

回答2:

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.

回答3:

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

回答4:

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 

回答5:

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