Algorithm for solving systems of linear inequalities

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

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

Answer 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.