关于约束的几个 minizinc 问题

Question

一些背景知识。我正在尝试制作一个用于聚类 Design Structure Matrix(DSM) 的模型。我制作了一个草稿模型并有几个问题。其中大部分与 DSM 本身没有直接关系。

include "globals.mzn";

int: dsmSize = 7;
int: maxClusterSize = 7;
int: maxClusters = 4;
int: powcc = 2;

enum dsmElements = {A, B, C, D, E, F,G};

array[dsmElements, dsmElements] of int: dsm  = 
[|1,1,0,0,1,1,0 
 |0,1,0,1,0,0,1
 |0,1,1,1,0,0,1
 |0,1,1,1,1,0,1
 |0,0,0,1,1,1,0
 |1,0,0,0,1,1,0
 |0,1,1,1,0,0,1|];
 
array[1..maxClusters] of var set of dsmElements: clusters;
array[1..maxClusters] of var int: clusterCard;

constraint forall(i in 1..maxClusters)(
  clusterCard[i] = pow(card(clusters[i]), powcc)
);



% #1
% constraint forall(i, j in clusters where i != j)(card(i intersect j) == 0);

% #2
constraint forall(i, j in 1..maxClusters where i != j)(
  card(clusters[i] intersect clusters[j]) == 0
);

% #3
% constraint all_different([i | i in clusters]);

constraint (clusters[1] union clusters[2] union clusters[3] union clusters[4]) = dsmElements;

var int: intraCost = sum(i in 1..maxClusters, j, k in clusters[i] where k != j)(
  (dsm[j,k] + dsm[k,j]) * clusterCard[i]
) ;                      
                       
var int: extraCost =   sum(el in dsmElements, 
                           c in clusters where card(c intersect {el}) = 0, 
                           k,j in c)(
                              (dsm[j,k] + dsm[k,j]) * pow(card(dsmElements), powcc)
);



var int: TCC = trace("\(intraCost), \(extraCost)\n", intraCost+extraCost);


solve maximize TCC;

问题 1

我的印象是，约束 #1 和 #2 是相同的。然而，似乎他们不是。这里的问题是为什么？有什么区别？

问题二

如何用 all_different 替换约束 #2？有道理吗？

问题三

为什么 trace("\(intraCost), \(extraCost)\n", intraCost+extraCost); 在输出中没有显示任何内容？我使用 gecode 看到的输出是：

Running dsm.mzn
intraCost, extraCost
clusters = array1d(1..4, [{A, B, C, D, E, F, G}, {}, {}, {}]);
clusterCard = array1d(1..4, [49, 0, 0, 0]);
----------
<sipped to save space>
----------
clusters = array1d(1..4, [{B, C, D, G}, {A, E, F}, {}, {}]);
clusterCard = array1d(1..4, [16, 9, 0, 0]);
----------
==========
Finished in 5s 419msec

问题4

表达式constraint (clusters[1] union clusters[2] union clusters[3] union clusters[4]) = dsmElements;，这里我想说的是所有簇的并集应该匹配所有节点的集合。不幸的是，我没有找到让这个大联盟更有活力的方法，所以现在我只是手动提供所有集群。有没有办法使这个表达式 return 集合数组中所有集合的并集？

问题5

基本上，如果我理解正确，例如 here，集群内成本 是集群内所有交互的总和乘以大小集群的某种力量，基本上是代表集群的节点集的基数。

额外集群成本是一些不属于集群的随机元素与该集群的所有元素之间的相互作用的总和乘以整体的基数space 节点的一些权力。

这里的主要问题是 intraCost 和 extraCost 我的模型是否正确（它们似乎是但仍然如此），是否有更好的方式来表达这些总和？

谢谢！

Answer 1

（如果把这个分成多个问题，也许你会得到更多的答案。）

问题 3: 这是 trace 问题的答案：

当运行模型时，trace实际显示的是：

intraCost, extraCost

当然，这不是您所期望的。 Trace 在创建模型时有效，但在那个阶段没有这两个决策值的值，MiniZinc 仅显示变量名称。在达到（第一个）解决方案后，他们得到了一些要显示的值，然后可以在 output 部分中显示。

trace 主要用于查看循环中发生的情况，其中可以跟踪（固定的）循环变量等。

如果您跟踪一组决策变量，那么它们将以不同的方式表示，数组 x 将显示为 X_INTRODUCED_0_ 等

您还可以使用 trace 进行域反射，例如使用 lb 和 ub 获取变量域的 lower/upper 值（“边界的安全近似值”，如文档所述：https://www.minizinc.org/doc-2.5.5/en/predicates.html?highlight=ub_array）。这是一个显示 intraCost 变量域的示例：

constraint
  trace("intraCost: \(lb(intraCost))..\(ub(intraCost))\n")
;

显示

intraCost: -infinity..infinity

您可以在此处 https://www.minizinc.org/doc-2.5.5/en/efficient.html?highlight=trace 阅读更多关于 trace 的信息。

更新问题 1、2 和 4 的答案。

约束#1 和#2 的意思相同，即 clusters 中的元素应该是不相交的。 #1 约束有点不同，因为它循环遍历决策变量，而 #2 约束使用普通索引。人们可以猜测 #2 更快，因为 #1 使用必须转换为一些额外约束的 where i != j 。（使用 i < j 应该会快一点。）

all_different 约束状态大致相同，并且取决于底层求解器，如果将其转换为求解器中的高效算法，可能会更快。

在模型中还有以下约束，声明必须使用所有元素：

constraint (clusters[1] union clusters[2] union clusters[3] union clusters[4]) = dsmElements;

除了效率之外，上述所有这些约束都可以用一个约束代替：partition_set，它确保 dsmElements 中的所有元素必须在 clusters.[=36 中使用=]

constraint partition_set(clusters,dsmElements);

结合 all_different 约束可能会更快，但这必须经过测试。

关于约束的几个 minizinc 问题

Few minizinc questions on constraints

minizinc