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?


2 Answers 2


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:

feasability[c_, m_, b_] := 
 With[{offset = 5 (*can be any positive number*)},
      Append[0*c, 1], 
      ArrayFlatten[{{m, 1}}], 
      b + offset]] - offset] <= 0
  • $\begingroup$ If the input is rational, then checking for zero is fine, since LinearProgramming seems to use simplex. $\endgroup$
    – Louis
    Aug 23, 2016 at 9:58
  • 1
    $\begingroup$ @Louis: You're probably right. The second version should work with floating point and exact numbers, though. $\endgroup$ Aug 23, 2016 at 10:20
  • $\begingroup$ Also, for the general form, extra slack variables are needed. I'll post an extended version later. $\endgroup$
    – Louis
    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_] :=
  Not[Head[Quiet[LinearProgramming[c, A, b]]] === LinearProgramming]

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.