9
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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
$\endgroup$
  • $\begingroup$ If the input is rational, then checking for zero is fine, since LinearProgramming seems to use simplex. $\endgroup$ – Louis Aug 23 '16 at 9:58
  • 1
    $\begingroup$ @Louis: You're probably right. The second version should work with floating point and exact numbers, though. $\endgroup$ – Niki Estner Aug 23 '16 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 '16 at 14:44
0
$\begingroup$

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.

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

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.