Checking linear program feasibility?

Question

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?

Answer 1

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

Answer 2

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.