CODEWITHSUNDEEP
linear-algebra
GMB
GMB

Reputation: 506

Algorithm for solving systems of linear inequalities

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!

Upvotes: 15

Views: 10280

Answers (6)

Evald Ubi
Evald Ubi

Reputation: 1

You could use simplex method, see "A version of the simplex method for solving system of linear inequalities and linear programming problem"

Upvotes: 0

Rouz
Rouz

Reputation: 1367

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

Upvotes: 2

C-Otto
C-Otto

Reputation: 5843

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.

Upvotes: 3

Shai
Shai

Reputation: 114826

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

Upvotes: 7

scibuff
scibuff

Reputation: 13755

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

Upvotes: 0

Diego
Diego

Reputation: 18359

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

Upvotes: 1

Related Questions