2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

The short answer to your question is: kind of.

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.

However, in the general case, as Arnold Neumaier points out in the SciComp link from ChristianClason, linear program feasibility checking is polynomial-time reducible to linear programming and vice versa.

$\endgroup$

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.