<p>(1) <a href="http://en.wikipedia.org/wiki/Farkas%27_lemma" rel="nofollow">Farkas' Lemma</a> should show the equivalence of the infeasibility problem and LP in strongly polynomial time.</p>

<p>(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.</p>

CC BY-SA 2.5
2011-03-27T03:01:12.643Z
2011-03-27T03:01:12.643Z
Yoshio Okamoto
<p>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.</p>

CC BY-SA 2.5
2011-03-25T04:21:46.363Z
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
CC BY-SA 2.5
2011-03-25T08:39:44.020Z
@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
Tomek Tarczynski
CC BY-SA 2.5
2011-03-26T12:55:45.673Z
@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 
CC BY-SA 2.5
2011-03-27T15:36:01.217Z
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?
Peter Shor 
CC BY-SA 2.5
2011-03-28T09:37:13.443Z
@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) ?
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2011-03-28T12:46:41.767Z
Now that I've thought about it, Tomek has indeed solved the problem.
Peter Shor 
CC BY-SA 3.0
2016-10-20T00:47:30.163Z
By the way, it's not totally clear to me that "binary search" easily works.  (Tomek's idea is OK.) It's true that if the original LP has representation size L, then you know the optimal solution (if it's not unbounded) can be expressed as a rational number where the numerator and denominator are poly(L) bits long. But it's not super-clear how to binary search for this value, since it's not like there is a fixed denominator. (I think it's possible to pull it off by binary searching to sufficiently high accuracy and then using continued fractions to figure out the answer, somehow... not obvious)
Ryan O'Donnell
CC BY-SA 2.5
2011-03-25T03:48:39.570Z
2011-03-25T03:48:39.570Z
Yuval Filmus
<p>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.</p>

<p>Are there any other methods to detect infeasibility of a the system?</p>

<ds.algorithms><optimization><linear-programming>
Detecting infeasibility of System of Linear Inequalities
Opt
# Detecting infeasibility of System of Linear Inequalities

(Asked by: username_0 on 2011-03-24)

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?

**Tags:** ds.algorithms, optimization, linear-programming


---

## 2 answers

### Answer by username_1 on 2011-03-27. Score: 4 | Accepted answer

(1) [Farkas' Lemma](http://en.wikipedia.org/wiki/Farkas%27_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.


---

### Answer by username_2 on 2011-03-25. Score: 3

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: @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  
> **username_4**: @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.  
> **username_4**: 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?  
> **username_5**: @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) ?  
> **username_4**: Now that I've thought about it, Tomek has indeed solved the problem.  
> **username_6**: By the way, it's not totally clear to me that "binary search" easily works.  (Tomek's idea is OK.) It's true that if the original LP has representation size L, then you know the optimal solution (if it's not unbounded) can be expressed as a rational number where the numerator and denominator are poly(L) bits long. But it's not super-clear how to binary search for this value, since it's not like there is a fixed denominator. (I think it's possible to pull it off by binary searching to sufficiently high accuracy and then using continued fractions to figure out the answer, somehow... not obvious)  

---

