Попытка установить ограничение на MiniZin c с массивом наборов - PullRequest
Новая
       66

Попытка установить ограничение на MiniZin c с массивом наборов

1 голос
/ 24 апреля 2020

Мне задают вопрос, где я должен создать набор команд, с простым ограничением, когда есть два массива наборов, в которых два участника должны быть вместе, а какие - нет. Я новичок в Minizin c, поэтому мне трудно работать с переменной решения с массивом наборов. Команды тоже должны быть размера n.

Например: GroupsThatMustBePaired = [{1,3}, {4,5}] GroupsThatShouldNot = [{2,3}]

Вывод = [{1,3}, {4 , 5}, {2,6} .. и т.д.]

Есть помощь?

1 Ответ

2 голосов
/ 25 апреля 2020

Поначалу использование переменных множеств может быть немного сложнее, но если вы можете вернуться к тому, когда узнали о множествах в математике, то понятия должны быть очень знакомыми.

Ниже приведен пример того, как Вы могли бы написать свою модель. Он имеет несколько дополнительных ограничений, чтобы убедиться, что «команды» содержат всех, никого по два, и имеют максимальную вместимость, включая «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]
  )
);

Некоторые примечания, если вы хотите изменить эту модель : Большинство решателей не поддерживают набор переменных напрямую, но переводят эту модель для использования логических переменных. Это не обязательно хуже, но об этом следует помнить, если вы чувствуете, что проблема может быть проще выражена с помощью логических переменных.

В этом конкретном случае вы можете рассмотреть возможность использования целочисленных переменных. Эта проблема может рассматриваться как проблема назначения, когда члены назначаются командам. Это учитывает точку зрения членов команды, а не команды. Хотя это, вероятно, затруднит написание ограничения subset , эта структура устранит необходимость в ограничениях all_disjoint и array_union , поскольку мы знаем, что все будут в команде, и никто не будет в нескольких командах. В этом случае ограничение набора card (Cardinality) можно заменить целочисленным ограничением global_cardinality_low_up.

...