# linear programming feasiblity checking

Is there any sufficient and necessary condition to check the feasibility of the linear constraints

$Ax=b, x\geq 0$

without solving an LP with a constant objective function? $x$ is the variable and $A\in\mathbb{R}^{m\times n}$ is given and has full row rank. $b$ is also given.

Farka's lemma could be an option. But it is not what I'm looking for since if has the flavor of "if a solution exists for a set of equalities and inequalities" but does not provide a direct way to determine whether the solution exists.

Is there any more direct method to do the feasibility checking, such as by merely looking at the rank of augmented matrix and coefficient matrix similar to what Rouché–Capelli theorem does?

There are methods called "preprocessing" or "presolve", that will take a problem with constraints $b_{l} \leq Ax \leq b_{u}$ and $l \leq x \leq u$ as input. Using tests that are usually linear time, you can check sufficient conditions for infeasibility (but not necessary conditions). These methods are commonly used to transform a problem to reduce the runtime of standard algorithms for linear programming. You should look at a 1994 paper by Savelsbergh, a paper by Andersen and Andersen, and a survey paper by Ashutosh Mahajan. These papers all cover more general transformations that are also of interest; the Mahajan paper probably has the most modern and readable notation.