4
$\begingroup$

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?

  • 0
    @Benjamin: Two versions at MO were posted: [This one](http://mathoverflow.net/questions/85731/how-to-determine-whether-a-system-of-linear-inequalities-has-a-positive-solution) and [this one](http://mathoverflow.net/questions/85669/how-to-determine-whether-a-system-of-linear-inequalities-has-a-solution-or-not). They were both closed there. But, they're clearly on-topic here.2012-01-15

1 Answers 1

6

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.