试图通过一组数组在MiniZinc上设置约束

Question

我被问到一个问题，我应该在哪里创建一组团队，只是有一个简单的约束，即有两个必须要在一起但不应该在一起的两个数组。我是Minizinc的新手，所以我很难处理带有一组数组的决策变量。团队的大小也必须为n。

例如：GroupsThatMustBePaired = [{{1,3}，{4,5}]GroupsThatShouldNot = [{2,3}]

输出= [{1,3}，{4,5}，{2,6} .etc]

有帮助吗？

Answer 1

起初使用集合变量可能会有些棘手，但是如果您可以回过头来学习数学中的集合，那么概念应该非常熟悉。

以下是如何编写模型的示例。它具有一些额外的约束条件，以确保“团队”容纳所有人，没有人两次，并具有最大容量包括“ all_disjoint.mzn”；

set of int: MEMBERS = 1..6;
set of int: GROUPS = 1..3;
array[int] of set of MEMBERS: GroupsThatMustBePaired = [{1,3},{4,5}];
array[int] of set of MEMBERS: GroupsThatShouldNot = [{2,3}];

array[GROUPS] of var set of MEMBERS: teams;

% Team members can only be part of one team
constraint all_disjoint(teams);
% Everyone must be part of a team
constraint array_union(teams) = MEMBERS;
% Maximal number of people per group
constraint forall(g in GROUPS) ( card(teams[g]) <= 2 );

% Eliminate bad groups
constraint forall(g in GROUPS, i in index_set(GroupsThatShouldNot)) (
  not (GroupsThatShouldNot[i] subset teams[g])
);

% Enforce good groups
constraint forall(i in index_set(GroupsThatMustBePaired)) (
  exists(g in GROUPS) (
    GroupsThatMustBePaired[i] subset teams[g]
  )
);

如果要更改此模型，请注意：大多数求解器不直接支持set变量，而是将此模型转换为使用布尔变量。这并不一定会更糟，但是如果您认为使用布尔变量可以更轻松地表达问题，则要牢记这一点。

在这种情况下，您可能要考虑使用整数变量。该问题可以看作是分配问题，其中成员被分配给团队。这考虑了团队成员而不是团队的观点。尽管这可能会使subset约束​​更难编写，但此结构将消除对all_disjoint和array_union约束的需求，因为我们知道每个人都将成为一个团队，而没人会在多个团队中。在这种情况下，card（基数）设置约束可以替换为global_cardinality_low_up整数约束。