9
$\begingroup$

Bug introduced in 9.0 or earlier and persisting through 11.0.1 or later


While searching to answer the question

at some time I composed a set of arguments for LinearProgramming that apparently is not handled correctly. Running this code:

args = {cost, m, bs, vr, vd} = 
   Import["http://www.dropbox.com/s/73iz8t8ivakazvt/LinearProgrammingIssue.m?dl=1"];
sol = LinearProgramming @@ N@args

gives an invalid {0, 0, 0, ....., 0} solution that apparently doesn't satisfy the constraints

MapThread[#3[#1, #2] &, {m.sol, bs[[All, 1]], 
  bs[[All, 2]] /. {0 -> Equal, 1 -> GreaterEqual, -1 -> LessEqual}}]
Sign[m.sol - bs[[All, 1]]] == bs[[All, 2]]

{True, False, False, True, True, False, False, False, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False, False, False, False, False, False, False, False, False, False, False, False, False}

False

without raising any warning.

Is this a bug or am I missing something?


After @DanielLichtblau's comment, I also tried to reproduce with Minimize and Maximize.

args = {cost, m, bs, vr, vd} = 
   Import["http://www.dropbox.com/s/73iz8t8ivakazvt/LinearProgrammingIssue.m?dl=1"];

Module[{x, vars, constraints, objective, ranges, domains, N = N},
 vars = Array[x, Length@cost];
 objective = N@cost.vars;
 constraints = 
  MapThread[#3[#1, #2] &, {N@m.vars, N@bs[[All, 1]], 
    bs[[All, 2]] /. {0 -> Equal, 1 -> GreaterEqual, -1 -> LessEqual}}];
 ranges = MapThread[LessEqual @@ Riffle[#2, #1] &, {vars, vr}];
 domains = Thread[vars \[Element] N@vd];
 Minimize @@ {{objective, {constraints, ranges, domains}}, vars}
 ]

If I apply N as in LinearProgramming (so Module[{..., N=N}, ...]) the answer is immediate and still wrong.

If I don't apply N (so Module[{..., N=Identity}, ...]) Mathematica starts computing but I didn't have the patience to check if/when something happens.

I suspect this issue can be related to very big numbers in the cost vector (they are not machine precision Integer). They can converted into machine precision Real, but I'm not sure if a Real cost vector can be combined with Integer variables in a LinearProgramming/Minimize problem.

$\endgroup$
  • 6
    $\begingroup$ It's a bug. If one sets this up to use Maximize it should work correctly, albeit more slowly. $\endgroup$ – Daniel Lichtblau Mar 1 '16 at 16:45
  • $\begingroup$ Thanks @DanielLichtblau. I updated the question adding an header and the bugs tag. Hope to have done it right. $\endgroup$ – unlikely Mar 1 '16 at 17:31
  • $\begingroup$ @DanielLichtblau Apparently, on my machine, also Minimize/Maximize gives a wrong answer. $\endgroup$ – unlikely Mar 1 '16 at 20:42
  • $\begingroup$ Do you have the input for Minimize (or handy code to generate it)? $\endgroup$ – Daniel Lichtblau Mar 1 '16 at 21:08
  • $\begingroup$ @DanielLichtblau Added some code and info. $\endgroup$ – unlikely Mar 1 '16 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.