How to determine whether a system of linear inequalities has a positive solution or not?

Is there any poly-time algorithm to do this? Or the best algorithms known are no less complex than algorithms for solving set of linear inequalities?

  • $\begingroup$ Question posted at mathoverflow and was closed. Don't remember the link. $\endgroup$ – user38268 Jan 15 '12 at 18:05
  • 1
    $\begingroup$ Note that search for positive solutions can be written as another general linear inequality because $x_i>0$ is just a linear inequality, so you can add it to your system and you still have a system of linear equalities. $\endgroup$ – Thomas Andrews Jan 15 '12 at 18:43
  • $\begingroup$ @Benjamin: Two versions at MO were posted: This one and this one. They were both closed there. But, they're clearly on-topic here. $\endgroup$ – cardinal Jan 15 '12 at 20:38

Your problem is known as Linear Programming (if you change positive to non-negative). Usually linear programming is thought of as an optimization problem, but in fact the optimization problem is equivalent to feasibility, which is exactly what you're asking: whether a system of inequalities has any solution.

If you really want to ask whether there's a positive solution, then what you can do is take your system of inequalities $Ax \geq b$ and add the constraint $x_i \geq m$, maximizing over $m$. If the maximum is $m > 0$, then there is a strictly positive solution, otherwise there isn't.


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.