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 = [email protected];
 constraints = 
  MapThread[#3[#1, #2] &, {[email protected], 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$
5
  • 6
    $\begingroup$ It's a bug. If one sets this up to use Maximize it should work correctly, albeit more slowly. $\endgroup$ Mar 1, 2016 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, 2016 at 17:31
  • $\begingroup$ @DanielLichtblau Apparently, on my machine, also Minimize/Maximize gives a wrong answer. $\endgroup$
    – unlikely
    Mar 1, 2016 at 20:42
  • $\begingroup$ Do you have the input for Minimize (or handy code to generate it)? $\endgroup$ Mar 1, 2016 at 21:08
  • $\begingroup$ @DanielLichtblau Added some code and info. $\endgroup$
    – unlikely
    Mar 1, 2016 at 21:33

0

Your Answer

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

Browse other questions tagged or ask your own question.