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
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.
Comments
Post a Comment