# Detecting infeasibility of System of Linear Inequalities

Infeasibility of a system of linear inequalities can be detected by using artificial variables and then using an algorithm like the simplex algorithm (or ellipsoid/interior point methods) to find a basic feasible solution. If one cannot be found then the problem is infeasible.

Are there any other methods to detect infeasibility of a the system?

• @Sid: the difference between the infeasibility problem and the standard linear programming problem is exactly the difference between a search and a decision problem. The decision version of the LP problem (e.g., is the optimal solution $\geq x$) can be turned into an infeasibility problem. – Peter Shor Mar 26 '11 at 12:55