# Checking linear program feasibility?

I want to check whether a certain linear program is feasible programmatically. If I just type in an infeasible instance, such as

LinearProgramming[{1, 1}, {{-1, -1}}, {1}]


I get back an error, not an output indicating that it's infeasible. What is the right way to get that behaviour?

I don't think LinearProgramming can do that directly. The documentation says: LinearProgramming returns unevaluated if no solution can be found.

However, checking the feasibility is a linear programming problem, too, so you could write a helper function like this:

feasibility[c_, m_, b_] :=
Last[LinearProgramming[Append[0*c, 1],
ArrayFlatten[{{m, 1}, {0, 1}}], Append[b, 0]]] == 0


The idea is that I add a new variable/constraint pair that "loosens" the constraints, and minimize that variable. If it can be minimized to 0, then the constraints are feasible.

EDIT: I think it's possible that LinearProgramming returns a small nonzero value due to numerical inaccuracy. This version would prevent this:

Clear[feasability]
feasability[c_, m_, b_] :=
With[{offset = 5 (*can be any positive number*)},
Last[LinearProgramming[
Append[0*c, 1],
ArrayFlatten[{{m, 1}}],
b + offset]] - offset] <= 0

• If the input is rational, then checking for zero is fine, since LinearProgramming seems to use simplex. Aug 23, 2016 at 9:58
• @Louis: You're probably right. The second version should work with floating point and exact numbers, though. Aug 23, 2016 at 10:20
• Also, for the general form, extra slack variables are needed. I'll post an extended version later. Aug 23, 2016 at 14:44

I ended up using the following alternative, since it works with the general form of input to LinearProgramming

LPFeasible[c_, A_, b_] :=