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

Question

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

Задача состоит в том, чтобы свести к минимуму количестволица, занятые при соблюдении всех ограничений, указанных выше. Он хранится в переменной 'nb_personnes'.

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

include "globals.mzn";

int: n_jour = 7; 
int: maxpersonnes = 40;
var 1..maxpersonnes : nb_personnes ;

set of int: jours = 1..n_jour;
array[1..n_jour] of int: minempl_perday = [14,13,15,16,19,18,11] ;
%set of int var: personnes = 1..n_personnes;

array[1..maxpersonnes, jours] of var 0..1: planning;

% Now pad all remaining rows to 0
constraint forall(i in nb_personnes+1..maxpersonnes,j in jours)(planning[i,j]=0);

% Constraints

% Each value of every point in array can only be 1 or 0
%constraint forall(p in 1..nb_personnes, d in jours)(planning[p,d] = 1 \/ planning[p,d] = 0);

% Each employee only works 5 days a week.
%constraint forall(p in 1..nb_personnes)(forall(d in jours))(sum(planning[p][d]) = 5); 
constraint forall(p in 1..nb_personnes)(sum(d in jours)(planning[p,d]) = 5);

% Minimum number of employees respected each day
constraint forall(i in 1..n_jour )(sum(p in 1..nb_personnes)(planning[p,i]) >= minempl_perday[i]);


% Five days consecutive worked by every employee
% First day - monday
constraint forall(p in 1..nb_personnes)(if planning[p,1] = 1 /\ planning[p,7] = 0 then planning[p,2] = 1 /\ planning[p,3]= 1 /\ planning[p,4] = 1/\ planning[p,5] = 1 endif);

% First day - tuesday
constraint forall(p in 1..nb_personnes)(if planning[p,2] = 1 /\ planning[p,1] = 0 then planning[p,3] = 1 /\ planning[p,4]= 1 /\ planning[p,5] = 1/\ planning[p,6] = 1 endif);

% First day - wednesday
constraint forall(p in 1..nb_personnes)(if planning[p,3] = 1 /\ planning[p,2] = 0 then planning[p,4] = 1 /\ planning[p,5]= 1 /\ planning[p,6] = 1/\ planning[p,7] = 1 endif);

% First day - tnursday
constraint forall(p in 1..nb_personnes)(if planning[p,4] = 1 /\ planning[p,3] = 0 then planning[p,5] = 1 /\ planning[p,6]= 1 /\ planning[p,7] = 1/\ planning[p,1] = 1 endif);

% First day - friday
constraint forall(p in 1..nb_personnes)(if planning[p,5] = 1 /\ planning[p,4] = 0 then planning[p,6] = 1 /\ planning[p,7]= 1 /\ planning[p,1] = 1/\ planning[p,2] = 1 endif);

% First day - saturday
constraint forall(p in 1..nb_personnes)(if planning[p,6] = 1 /\ planning[p,5] = 0 then planning[p,7] = 1 /\ planning[p,1]= 1 /\ planning[p,2] = 1/\ planning[p,3] = 1 endif);

% First day - sunday
constraint forall(p in 1..nb_personnes)(if planning[p,7] = 1 /\ planning[p,6] = 0 then planning[p,1] = 1 /\ planning[p,2]= 1 /\ planning[p,3] = 1/\ planning[p,4] = 1 endif);


% Minimize the nb_personnes such that all the constraints of above are satisfied
solve minimize(nb_personnes);

output [show(planning[p,j])++" "++
     if j==n_jour 
       then "\n" 
       else "" 
     endif 
     |p in 1..maxpersonnes, j in jours];

Answer 1

При использовании оптимизации (минимизировать или развернуть) рекомендуется использовать опции -a, чтобы увидеть все промежуточные решения. Без этой опции отображается только последнее оптимальное решение.

Если решение занимает слишком много времени, вы можете поэкспериментировать с различными вариантами поиска, например,

solve ::int_search(array1d(planning), anti_first_fail, indomain_split, complete)  minimize nb_personnes;

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

include "nosets.mzn";

Однако для этой проблемы, вероятно, лучше использовать решатель MIP, например CBC. Обратите внимание, что вам все равно нужно добавить строку include "nosets.mzn;.

Позже (и немного не по теме): ваши семидневные ограничения могут быть заменены следующими:

function int: modadd(int: n, int: s, int: m) =
  let {
     int: r = (n + s) mod m;
     int: t = if r == 0 then m else r  endif
  }
  in t;

constraint
  forall(t in 1..7) (
    forall(p in 1..nb_personnes)(
       if planning[p,t] = 1 /\ planning[p,modadd(t,-1,7)] = 0 then
         forall(a in 1..4) (
            planning[p,modadd(t,a,7)] = 1
         )
      endif
    )
);