Возникают проблемы с пониманием того, как выразить реальную проблему для opensolver или minincinc для распределения работников - PullRequest
Новая
       27

Возникают проблемы с пониманием того, как выразить реальную проблему для opensolver или minincinc для распределения работников

0 голосов
/ 06 марта 2019

Я собираюсь начать с того, что я не очень хорошо разбираюсь в Minizinc или в программировании с ограничениями, я смотрел учебники Excel по "решателю" на YouTube, которые я понимаю, но я не понимаю, как я могу перевести свою проблему вРешение Excel, способное к решению, и Minizinc в этом отношении.

Чтобы объяснить проблему, у меня есть то, что я считаю многоуровневой проблемой ранца, но могу ошибаться.Вот то, что я считаю ограничениями 

There are 25 "admin" who supervise over 200 "staff".
Each admin has a unique workload allocation.
Each admin also has to moderate staff 
    that is both equal to or greater than their supervisorial allocation 
    and has the ability to rate their moderation preference
Admin cannot supervise and moderate the same staff member.
Every staff member has to have both a supervisor and a moderator.

Чтобы обдумать проблему, я представил ее в виде таблицы

табличного представления набора выборок данных

  • a # = admin
  • s # = персонал
  • b = руководитель
  • v # = предпочтение модератора (ниже = лучше)

Принимая прилагаемый пример, мы можем видеть

admin1 - супервизор для staff1 , 13 и 17 Они добровольно вызвались умеренно сотрудников2 , 20 , 10 и 23 в таком порядке (предпочтение).

Игнорируя все вышеперечисленное, что является моей разбивкой проблемы, вы можете упростить проблему следующим образом

  1. каждая строка имеетравное или большее количество модераторов для супервизоров,
  2. , и в каждом столбце есть как уникальный супервизор, так и модератор (где возможный приоритет учитывается ниже = лучше).

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

Спасибо.

1 Ответ

1 голос
/ 07 марта 2019

Вы можете попробовать следующую MIP-модель в MiniZinc с решателем, установленным на OsiCbc. 

int: n = 10;
int: m = 24;
set of int: ADMIN = 1..n;
set of int: STAFF = 1..m;

array[ADMIN,STAFF] of var 0..1: supervise;
array[ADMIN,STAFF] of var 0..1: moderate;

array[ADMIN, STAFF] of int: moderateValue = [|
0,4,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,3,0,0,1,0|
3,2,0,0,0,0,0,0,4,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0|
0,0,1,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,3,0,0,0,2|
0,0,0,1,0,0,0,0,0,0,3,2,0,0,0,0,0,4,0,0,0,0,0,0|
0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,3,0,0,0,0,2,0,1|
0,0,0,0,2,4,0,0,0,0,0,0,0,0,3,1,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,2,3,0,0,0,0,0,0|
0,2,0,0,0,0,0,4,0,0,0,0,3,1,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,3,0,0,0,0,4,0,0,2,1,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,3,2,1|];

% admin member cannot both supervise and moderate staff member
constraint forall(a in ADMIN, s in STAFF)
    (supervise[a,s] + moderate[a,s] <= 1);

% each staff member is supervised by exactly one admin member
constraint forall(s in STAFF)
    (sum(col(supervise, s)) = 1);

% each staff member is moderated by exactly one admin member
constraint forall(s in STAFF)
    (sum(col(moderate, s)) = 1);

% each admin member cannot supervise more staff members than moderated
constraint forall(a in ADMIN)
    (sum(row(supervise, a)) <= sum(row(moderate, a)));

var int: obj = sum(a in ADMIN, s in STAFF)(moderateValue[a,s]*moderate[a,s]);

solve maximize obj;

output ["obj = \(obj)\n"] ++ ["assignment = \n"] ++ [show2d(array2d(ADMIN, STAFF, [if supervise[a,s] = 1 then 1 elseif moderate[a,s] = 1 then 2 else 0 endif | a in ADMIN, s in STAFF]))];

Я не уверен, понял ли я все ваши требования, но, надеюсь, модель сможетслужить базой.Каждый член admin может здесь указывать значения модерации от 4, 3, 2 и 1 до staff членов.Цель состоит в том, чтобы максимизировать сумму назначенных модераций.В выводе 1 означает, что администратор контролирует сотрудника, 2 означает, что администратор модерирует сотрудника, в противном случае отображается 0.Данные в модели основаны на предоставленном примере.

Редактировать : Чтобы сделать supervise предопределенным, измените следующее: 

%array[ADMIN,STAFF] of var 0..1: supervise;

array[ADMIN, STAFF] of int: supervise = [|
1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0|
0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0|
0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0|
0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0|
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1|
0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0|];
...