# 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. – Louis Aug 23 '16 at 9:58
• @Louis: You're probably right. The second version should work with floating point and exact numbers, though. – Niki Estner Aug 23 '16 at 10:20
• Also, for the general form, extra slack variables are needed. I'll post an extended version later. – Louis Aug 23 '16 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_] :=
Not[Head[Quiet[LinearProgramming[c, A, b]]] === LinearProgramming]


I'm not really sure this is entirely guaranteed to keep working, though.

• Wouldn't this be true whenever LinearProgramming throws an error, even if it's due to a syntax mistake? – mimuller Apr 5 '17 at 19:26