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?

(1) Farkas' Lemma should show the equivalence of the infeasibility problem and LP in strongly polynomial time.

(2) Solving a linear programming problem (as a computational problem) usually means "detect the problem is either infeasible, unbounded, or having an optimal solution, and if the problem has an optimal solution, find one". In this sense, they are equivalent.

The problem is equivalent to LP. To solve LP using an infeasibility oracle, determine a polynomial-length bound on the optimum (this reduces to raising the modulus of the largest coefficient to some power which depends on the number of variables and inequalities) and use binary search.

• Well, LP is not known to have any strongly-polynomial algorithms. The reduction you described is also not a strongly-polynomial reduction thus one could have say a strongly polynomial method to detect infeasibility while still not have a strongly polynomial method for LP.
– Opt
Mar 25 '11 at 4:21
• @What about the Primal-Dual method, doesn't it imply an equivalence between LP and determining whether a system of linear equalities is infeasible? You can add dual constraints to a primal system and then any basic solution to the system should bo an optimal solution Mar 25 '11 at 8:39
• @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. Mar 26 '11 at 12:55
• Could you use some version of Megiddo's parametric search to show that if you had an oracle for the search problem, then you could find a randomized strongly polynomial time algorithm for the decision problem? Mar 27 '11 at 15:36
• @Peter Shor: What excatly is your question, and why is it not solved by the remark by Tomek Tarcynski above (i.e. adding dual variables, dual constraints and an equality for the primal and dual objective functions) ? Mar 28 '11 at 9:37