For my thesis I am making a simple schedule model. A small section of the code can be found below. The model aims to connect a set of specialized workers to a shift based on the required workload on time t. For now, this is a pure satisfaction problem.
Model:
enum employees; % all employees
set of employees: runnersPrimary; % runners employees
array[positions] of float: positionsRatio; % 50% of workload should be runners
% General labels
enum positions = {bar, runner, kitchen, free};
set of employees: emergencyResponseOfficer;
% Contract hours
array[employees] of int: contractHours;
% Workload requested
set of int: shiftLength = 1..(7*24); % one week schedule, scheduled per hour
array[shiftLength] of int: workload;
% Settings
int: minShiftLength = 3;
int: maxShiftLength = 8;
% Target variable
array[employees, shiftLength] of var positions: empToShift;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Support variables %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
array[shiftLength] of int: runnerLoad = [round(workload[s] * positionsRatio[runner]) | s in shiftLength];
set of positions: runnerAllowed = {runner, free}; % either working or not working
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Hard requirements %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nobody working when store is closed
constraint forall(e in employees, s in shiftLength where workload[s] = 0)(empToShift[e,s] = free);
% Employees with fixed contract hours should work atleast contracthours
constraint forall(e in employees where contractHours[e] > 0)(
sum(s in shiftLength)(empToShift[e, s] != free) >= contractHours[e]
/\ sum(s in shiftLength)(empToShift[e, s] != free) <= (contractHours[e] + 8)
);
% Min and max shift length
constraint forall(e in employees, s in 1..(length(shiftLength) - 3)
where workload[s+1] > 0 /\ empToShift[e,s] = free /\ empToShift[e,s+1] != free)(
empToShift[e,s+2] != free /\ empToShift[e,s+3] != free
);
constraint forall(e in employees, s in 1..(length(shiftLength) - (maxShiftLength+1))
where workload[s+1] > 0 /\ empToShift[e,s] = free /\ empToShift[e,s+1] != free)(
empToShift[e,s+9] = free
);
% Atleast 12 hours off after a shift
constraint forall(e in employees, s in 1..(length(shiftLength) - 12)
where empToShift[e,s] != free /\ empToShift[e,s+1] = free) (
empToShift[e,s+2] = free /\ empToShift[e,s+3] = free /\ empToShift[e,s+4] = free /\
empToShift[e,s+5] = free /\ empToShift[e,s+6] = free /\ empToShift[e,s+7] = free /\ empToShift[e,s+8] = free /\
empToShift[e,s+9] = free /\ empToShift[e,s+10] = free /\ empToShift[e,s+11] = free /\ empToShift[e,s+12] = free
);
% Employees can only work in assigned departments
include "member.mzn";
constraint forall(e in runnersPrimary, s in shiftLength)(member(runnerAllowed, empToShift[e,s]));
% Load at department should approximate target
constraint forall(s in shiftLength)(
sum(e in runnersPrimary where runnerLoad[s] = 0)(empToShift[e,s] = runner) = 0
/\ sum(e in runnersPrimary where runnerLoad[s] != 0)(empToShift[e,s] = runner) = runnerLoad[s]
);
solve satisfy;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Print %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
var int: targetRunnerLoad = sum(s in shiftLength)(runnerLoad[s]);
var int: assignedRunnerLoad = sum(s in shiftLength, e in runnersPrimary)(empToShift[e, s] != free);
output [ "time:\t" ];
output [ "\((t mod 24))\t" | t in shiftLength ];
output [ "\n\ntotal workload:\t" ];
output [ "\(p)\t" | p in workload ];
output [ "\nbarload:\t" ];
output [ "\(p)\t" | p in runnerLoad ];
output [ "\nkitchenload:\t"];
output [ if s = 1 then "\n\(e)\t\(empToShift[e,s])\t" else "\(empToShift[e,s])\t" endif | e in employees, s in shiftLength];
output [ "\nTarget runner:\(targetRunnerLoad)\tActual runner:\(assignedRunnerLoad)" ];
Data set:
employees = {fixed1, fixed2, fixed3, fixed4, fixed5, fixed6, fixed7, fixed8, fixed9, fixed10, variable1, variable2, variable3, variable4, variable5, variable6, variable7, variable8, variable9, variable10, variable11, variable12, variable13, variable14, variable15, variable16, variable17, variable18, variable19, variable20, variable21, variable22, variable23, variable24, variable25, variable26, variable27, variable28, variable29, variable30, variable31, variable32, variable33, variable34, variable35, variable36, variable37, variable38, variable39, variable40};
contractHours = [24, 40, 24, 40, 24, 40, 24, 40, 24, 40, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
positionsRatio = [0.20 , 0.50, 0.30, 0];
runnersPrimary = {fixed3, fixed4, fixed5, fixed6, fixed7, variable9, variable10, variable11, variable12, variable13, variable14, variable15, variable16, variable17, variable18, variable19, variable20, variable21, variable22, variable23, variable24, variable25, variable26, variable27, variable28};
emergencyResponseOfficer = {fixed1, fixed9, fixed10, variable8, variable31};
% 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
workload = [0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 6, 8, 8, 8, 8, 8, 12, 12, 12, 12, 6, 6, 0, 0, %mo
0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 9, 9, 9, 9, 9, 14, 14, 14, 14, 7, 7, 0, 0, %tu
0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 9, 9, 9, 9, 9, 14, 14, 14, 14, 7, 7, 0, 0, %we
0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 9, 9, 9, 9, 9, 14, 14, 14, 16, 9, 9, 0, 0, %th
0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 10, 10, 10, 18, 18, 18, 11, 11, 11, 0, %fr
0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 14, 14, 14, 14, 14, 14, 20, 20, 20, 18, 16, 16, 16, 16, %sa
0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 12, 12, 18, 18, 18, 11, 11, 11, 0, 0]; %su
With Chuffed a solution can be found within two seconds whereas OR-Tools can not find a solution at all. Clearly there is a problem with the model. What should be changed in order to make it find a solution within reasonable time?
When using systems that solves combinatorial optimization problems using automatic search strategies, it is not that uncommon for one system to solve a problem and for another to have trouble with it.
For your particular case, it is worth noting that OR-Tools works best when given multiple threads and free search. Running your model on my computer with OR-Tools using 10 threads, a solution was found in less than 2 seconds. Relatedly, using Gecode with 10 threads with restarts (luby sequence) and using nogoods found a solution in less than 5 seconds. On the other hand, checking the free search box for Chuffed changed it from 1.3 seconds to 21 seconds.
In essence relying on automatic search heuristics can be a problem sometimes, and it can be somewhat hard to understand what modelling decisions lead to what outcomes. Experimentation is usually the best thing.
Worth noting is that you model has quite deep search trees. Gecode reports a depth of more than 1600 levels, which is significant. Consider if there is anything you can strengthen in your formulation, or if there is some search heuristic that can be given as guidance indicating what variables are important.