4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Opt Mar 25 '11 at 4:21
  • 5
    $\begingroup$ @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 $\endgroup$ – Tomek Tarczynski Mar 25 '11 at 8:39
  • 2
    $\begingroup$ @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. $\endgroup$ – Peter Shor Mar 26 '11 at 12:55
  • $\begingroup$ 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? $\endgroup$ – Peter Shor Mar 27 '11 at 15:36
  • $\begingroup$ @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) ? $\endgroup$ – Kristoffer Arnsfelt Hansen Mar 28 '11 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.