wolfram-mathematica - 整数最小化技术

Question

我必须最小化一堆可以从整数范围取值的 n 个变量的函数。

函数具有一般形式:

f[{s1_,... sn_}]:= Kxy KroneckerDelta[sx,sy] + Kwz KroneckerDelta[sw,sz] +/- ..

其中 Kmn 也是整数。

举个例子，

f[{s1_, s2_, s3_, s4_, s5_}:= KroneckerDelta[s1, s2] - KroneckerDelta[s1, s4] +
                              KroneckerDelta[s1, s5] + KroneckerDelta[s3, s4] + 
                              KroneckerDelta[s3, s5] + KroneckerDelta[s4, s5]; 

si_ 必须在范围 [3] 内。

我可以很容易地进行暴力破解，例如:

rulez = Table[s[i] -> #[[i]], {i, 5}] & /@ Tuples[Range[3], 5]; 
k1    = f[Table[s[i], {i, 5}]] /. rulez;

{Min[k1], Tuples[Range[3], 5][[#]] & /@ Position[k1, Min[k1]]}
(*
->
{-1,{{{1, 2, 2, 1, 3}}, {{1, 2, 3, 1, 2}}, {{1, 3, 2, 1, 3}}, {{1, 3, 3, 1, 2}}, 
     {{2, 1, 1, 2, 3}}, {{2, 1, 3, 2, 1}}, {{2, 3, 1, 2, 3}}, {{2, 3, 3, 2, 1}}, 
     {{3, 1, 1, 3, 2}}, {{3, 1, 2, 3, 1}}, {{3, 2, 1, 3, 2}}, {{3, 2, 2, 3, 1}}}}
*)

显然，对于大量变量和更大的值范围来说，这似乎要花很长时间。

我尝试了 Minimize[ ]，但得到的结果不满足条件 (!):

Minimize[{f[Table[s[i], {i, 5}]],  And @@ Table[1 <= s[i] <= 3, {i, 5}]},
         Table[s[i], {i, 5}], Integers]
(*
-> {2, {s[1] -> 0, s[2] -> 0, s[3] -> 0, s[4] -> 0, s[5] -> 0}}
*)

或者在其他情况下，它只是失败了:

g[{s1_, s2_, s3_, s4_, s5_}]:= KroneckerDelta[s1, s3] - KroneckerDelta[s1, s4] +
                               KroneckerDelta[s1, s5] + KroneckerDelta[s3, s4] + 
                               KroneckerDelta[s3, s5] + KroneckerDelta[s4, s5]; 

Minimize[{g[Table[s[i], {i, 5}]],  And @@ Table[1 <= s[i] <= 3, {i, 5}]},
         Table[s[i], {i, 5}], Integers]
(*
-> 
During evaluation of In[168]:= Minimize::infeas: There are no values of
{s[1],s[2],s[3],s[4],s[5]} for which the constraints 1<=s[1]<=3&&1<=s[2]<=3&&
1<=s[3]<=3&&1<=s[4]<=3&&1<=s[5]<=3 are satisfied and the objective function  
KroneckerDelta[s[1],s[3]]-KroneckerDelta[s[1],s[4]]+KroneckerDelta[s[1],s[5]]+
KroneckerDelta[s[3],s[4]]+KroneckerDelta[s[3],s[5]]+KroneckerDelta[s[4],s[5]] 
is real valued.  >>
Out[169]= {\[Infinity], s[1]->Indeterminate, s[2]->Indeterminate, 
                        s[3]->Indeterminate, s[4]->Indeterminate, 
                        s[5]->Indeterminate}}
*)

所以问题是双重的:

为什么 Minimize[ ] 会失败？mathematica 解决此类问题的更好方法是什么？ ？

编辑

强调一下，第一个问题是:

为什么 Minimize[ ] 会失败？

并不是说其他​​部分不那么重要，而是我正在尝试学习何时投入时间潜伏在 Minimize[ ] 中，何时不应该。

Answer 1

问题似乎与 KroneckerDelta 有关。如果我定义一个函数，只要输入整数它就可以工作(或者至少看起来像):

In[177]:= kd[x_, y_] := Round[10^-(x - y)^2]

In[179]:= 
g[{s1_, s2_, s3_, s4_, s5_}] := 
  kd[s1, s3] - kd[s1, s4] + kd[s1, s5] + kd[s3, s4] + kd[s3, s5] + 
   kd[s4, s5];
Minimize[{g[{s1, s2, s3, s4, s5}], 
  And @@ Map[1 <= # <= 3 &, {s1, s2, s3, s4, s5}]}, {s1, s2, s3, s4, 
  s5}, Integers]

Out[180]= {-1, {s1 -> 1, s2 -> 1, s3 -> 2, s4 -> 1, s5 -> 3}}