时间戳

首页 > 解决方案 > 尝试使用一组集合对 MiniZinc 设置约束

arrays - 尝试使用一组集合对 MiniZinc 设置约束

问题描述

我有一个问题，我应该创建一组团队，只有一个简单的约束，其中有两个集合数组，两个成员必须在一起，哪些不应该在一起。我是 Minizinc 的新手，所以我很难处理带有一组集合的决策变量。团队的大小也必须为 n。

例如：

GroupsThatMustBePaired = [{1,3},{4,5}]
GroupsThatShouldNot = [{2,3}]

Output = [{1,3},{4,5},{2,6}..etc]

有什么帮助吗？

标签： arraysconstraint-programmingminizinc

解决方案

Using set variables can be a bit tricky at first, but if you can get back to when you learned about sets in mathematics, then the concepts should be very familiar.

The following is an example of how you could write you model. It has a few extra constraints to make sure that the "teams" contain everyone, nobody twice, and have a maximum capacity include "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]
  )
);

Some notes if you want to change this model: Most solvers do not support set variables directly but translate this model to use boolean variables instead. This is not necessarily worse, but is something to keep in mind if you feel that the problem could be easier expressed using boolean variables.

In this particular case, you might want to consider using integer variables. This problem can be seen as an assignment problem, where members are assigned to teams. This considers the viewpoint from the team-members instead of the team. Although this will probably make the subset constraint harder to write, this structure would remove the need for the all_disjoint and the array_union constraints, because we know everyone will be in a team and nobody will be in multiple teams. In this case the card (Cardinality) set constraint could be replace with a global_cardinality_low_up integer constraint.

推荐阅读