0
$\begingroup$

Using the code from this answer for a sufficiently large problem setting crashes my kernel. I'll copy/paste the code here:

n = 12;
m = 4;
costs = Range@n/2 // N;

vars = Flatten@{
    Array[x, {n, m}],
    Array[y, m],
    z
    };

constraints = Flatten@{
    Table[Sum[x[i, j], {j, m}] == 1, {i, n}],
    Table[y[j] == Sum[x[i, j] costs[[i]], {i, n}], {j, m}],
    Table[z >= y[j], {j, m}]
    };

bm = CoefficientArrays[Equal @@@ constraints, vars];
solution = LinearProgramming[
   Last@CoefficientArrays[z, vars],
   bm[[2]],
   Transpose@{-bm[[1]], 
     constraints[[All, 0]] /. {Equal -> 0, GreaterEqual -> 1}},
   vars /. {_x -> {0, 1}, (_y | z) -> {0, \[Infinity]}},
   vars /. {_x -> Integers, (_y | z) -> Reals}
   ];


Cases[Pick[vars, solution, 1], x[ij__] :> {ij}];
GroupBy[%, Last -> First] // Values // SortBy[First]

Running this for n=40 yields a result almost instantly, whereas n=60 leads to this

enter image description here

after a minute or so. I am using Mathematica 10.0.1 on Windows 8 64bit. Can you reproduce this behavior? If so, do you have an idea why it is happening?

Small update The kernel crash really appears to be due to LinearProgramming. Everything that is set before or is called within LinearProgramming evaluates basically instantly without issues. Only when solution is evaluated, the kernel crashes - on a Linux x64 it stays alive but Mathematica 10.0.2 freezes and does not return a result even after an hour.

$\endgroup$
  • $\begingroup$ Confirmed on Mathematica 10.3.0.0, OS X 10.10.5, after 10 minutes running. No idea, though. I thought Dynamic was only related to front-end operations. $\endgroup$ – Aisamu Feb 25 '16 at 12:59
  • $\begingroup$ Absolutely no problem in Mathematica 10.3.0 Windows 8.1 x64. Response is immediate, even faster than with n=12. $\endgroup$ – unlikely Feb 25 '16 at 17:02
  • $\begingroup$ Works ok on 10.0 for Mac OS X.11.3 x86 (64-bit) (December 4, 2014) $\endgroup$ – user9660 Feb 25 '16 at 17:16
  • $\begingroup$ Does it actually crash (i.e. the kernel process exits due to some error like segmentation fault), or does it just lock up? Can you clarify this point in the question and edit the tags accordingly? $\endgroup$ – Szabolcs Feb 27 '16 at 12:03
  • $\begingroup$ Works fine on 10.3.1 Win 7 Pro 64bit $\endgroup$ – Edmund Feb 27 '16 at 12:20

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.