2
$\begingroup$

Help please

M = 10; 
z = Array[x, M]
{x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10]}
Gcd = Array[GCD, {M, M}];
Minimize[{ Sum[Gcd[[ x[i], x[j] ]], {i, M}, {j, M}],
           And @@ Table[1 <= x[k] <= M, {k, M}]},
         z,
         Integers]
Part::pspec: Part specification x[1] is neither a machine-sized integer nor
a list of machine-sized integers. >>_

Michael E2, thank you!

How to simplify the description a more complex function Sum?

M = 10; z = Array[x, M];
Gcd = Array[GCD, {M, M}];
Gcd1 = Table[GCD[a, b] + 1, {a, M}, {b, M}];

obj[x_?(VectorQ[#, NumericQ] &)] := Sum[Gcd[[x[[i]], x[[j]]]]*Gcd1[[i, j]], {i, M}, {j, M}];

NMinimize[{obj[z], And @@ Table[1 <= x[k] <= M, {k, M}] && z ∈ Integers}, z]

And how to add a constraint alldifferent x[i]? (like AMPL-syntax "subject to all_diff {i in 1..M, j in 1..M : i < j}: x[i] != x[j];")

$\endgroup$
  • 1
    $\begingroup$ What is it supposed to do? $\endgroup$ – mlainz Nov 15 '14 at 22:19
  • 2
    $\begingroup$ You can't beat {1,1,1...1} $\endgroup$ – Dr. belisarius Nov 15 '14 at 22:33
  • $\begingroup$ @dio: I think what the OP is trying to do is minimize the given sum, where the x[i] are integers between 1 and 10. Part is getting unhappy at the fact that the x[i] are being treated as variables, and I don't know how to fix this, so I'd be interested to see what the correct syntax for this is. $\endgroup$ – DumpsterDoofus Nov 15 '14 at 22:39
  • $\begingroup$ What do you want to get with Gcd[[x[i], x[j]]]? $\endgroup$ – mlainz Nov 15 '14 at 22:45
  • 1
    $\begingroup$ Alldifferent constraint I found: "And @@ Flatten[Table[x[i] != x[j], {i, M}, {j, i - 1}]]". $\endgroup$ – dio Nov 16 '14 at 11:54
3
$\begingroup$

One part of the problem is answered here: What are the most common pitfalls awaiting new users?. You have to prevent the objective function from being evaluated before the x[i] are assigned numeric values.

The rest of the problem is, I think, that Minimize can't deal with this type of optimization, since the function cannot be analyzed symbolically, not without Part complaining at least. (Perhaps someone will show us.) However, NMinimize can deal with it, although it is not guaranteed to find the absolute minimum.

M = 10; z = Array[x, M];
Gcd = Array[GCD, {M, M}];
obj[x_?(VectorQ[#, NumericQ] &)] := Sum[Gcd[[x[[i]], x[[j]]]], {i, M}, {j, M}];
NMinimize[{obj[z], And @@ Table[1 <= x[k] <= M, {k, M}] && z ∈ Integers}, z]

(*
  {100., {x[1] -> 1, x[2] -> 1, x[3] -> 1, x[4] -> 1, x[5] -> 1, 
    x[6] -> 1, x[7] -> 1, x[8] -> 1, x[9] -> 1, x[10] -> 1}}
*)

Update

This version of the objective function is about five or six times faster

obj[x_?(VectorQ[#, NumericQ] &)] := Total[Gcd[[x, x]], 2]

For the second objective function, the analogous formula would be

obj[x_?(VectorQ[#, NumericQ] &)] := Total[Gcd[[x, x]]*Gcd1, 2]

The speed up in NMinimize is about a factor of 2 or less.

$\endgroup$

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.