# Algorithm for deciding feasibility of linear programs [closed]

Suppose I have the simple linear program

$$Ax \geq 0, \quad x \geq 0$$

We know that this system has a solution (for example, $$x=0$$). But, what if we made this rule for this system?

$$Ax \geq 0, \quad e^T x > 0$$

where $$e = (1, 0, \dots, 0)$$. Rewriting,

$$Ax \geq 0, \quad x_1 > 0$$

Is there a way to decide whether this system has solutions or not before using some algorithms to solve it?

• You may want to take a look at Kroening & Strichman's Decision Procedures — An Algorithmic Point of View Commented Mar 21, 2021 at 15:44
• Thank you for editing and book! Commented Mar 21, 2021 at 17:22
• @RodrigodeAzevedo, sorry, I had trouble with my net. A is fat and I already used Farkas' lemma to get this system (I thought that this system will be easier to analyze for a solution). I can write you whole what I got. Commented Mar 22, 2021 at 20:17
• @RodrigodeAzevedo, the main task was to understand if $$Ax \geq b$$ have a solution for polynomical time? From this task I've made a same task with other system (by Alexandrov' and Fan Ky alternative) $$-e=Bx, x \geq 0$$ where e = (1,0,...0) and B = [b, A] (matrix where first row is b from first system). Then by Farkas' lemma I've got this system (in the question). Commented Mar 22, 2021 at 20:23
• If you have an LP solver, you can simply solve the linear program \begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & \mathrm A \mathrm x \geq \mathrm b\end{array} Commented Mar 23, 2021 at 4:00