I have a list of Employee and a list of Mission.
Each mission have a start time and a duration.
In the cp model (Google CpSat, from or-tools package), I defined shifts = Dictionary<(int,int),IntVar>, where shifts[(missionId, employeeId)] == 1 if and only if this mission is realized by this employee.
I need to assign each mission to exactly one employee, and obviously one employee cannot realize two missions at the same time. I already have written those two hard constraints and they are working fine.
Now, some missions are "linked" together and should be realized by the same employee. They are stored as follow:
linkedMissions = {{1,2}, {3,4,5}}
Here, mission 1 and 2 must be realized together by the same employee, and it is the same for missions 3, 4 and 5.
To write this last constraint, I gathered for each employee the list of all the shifts that should be linked together, then I made them all equal.
foreach (var employee in listEmployeesIds)
foreach (var missionGroup in linkedMissionsIds)
{
var linkedShifts = shifts
.Where(o => o.Key.Item2 == employee
&& missionGroup.Contains(o.Key.Item1))
.Select(o => o.Value)
.ToList();
for (var i = 0; i < linkedShifts.Count - 1; i++)
model.Add(linkedShifts[i] == linkedShifts[i + 1]);
}
However, the solver tells me the model is infeasible, but with a paper and a pen I can easily find a working planning. I have 35 employees and 25 missions, the missions that are linked together don't overlap, so there shouldn't be any problem.
As an alternative approach, as suggested by @Laurent Perron, I tried to use the same boolean variables for all shifts that must be together:
var constraintBools = new List<IntVar>();
foreach (var missionGroup in linkedMissionsIds) {
var constraintBools = new List<IntVar>();
foreach (var employee in listEmployeesIds)
{
var linkedShifts = shifts
.Where(o => o.Key.Item2 == employee
&& missionGroup.Contains(o.Key.Item1))
.Select(o => o.Value)
.ToList();
var constraint = model.NewBoolVar($"{linkedShifts.GetHashCode()}");
model.AddBoolAnd(linkedShifts).OnlyEnforceIf(constraint);
constraintBools.Add(constraint);
}
model.AddBoolOr(constraintBools);
}
But now, the constraint simply doesn't work: the linked shifts are not realized by the same employee.
What is wrong in my reasoning? Why is my model infeasible?
The reasoning described in the question seems fine, however it's hard to verify without a minimal working example.
I was able to implement your approach (in Python) and it seems to work, so it would seem the issue is either in some other part of the code, or in some technical issue in the implementation, unrelated directly to the solver and conditions (e.g. related to lazy function calls as proposed in the comments by @Ian Mercer).
Here's a working example, based on your description:
model = cp_model.CpModel()
employees = 35
tasks = 25
# 3 non overlapping groups of linked tasks (as an example)
linkedTasks = [[t+1 for t in range(tasks) if t%5 == 0],
[t for t in range(tasks) if t%9 == 0],
[22, 23, 24]]
#semi random durations, 1-6
task_durations = [t%6+1 for t in range(tasks)]
MAX_TIME = sum(task_durations)
#employee shift assignment: shifts[e,t] == 1 iff task t is assigned to employee e
shifts = {}
for e in range(employees):
for t in range(tasks):
shifts[e, t] = model.NewBoolVar('shift_%i_%i' % (e, t))
# task intervals. Intervals are optional - interval [e, t] is only in effect if
# task t is performed by employee e
task_starts = {}
task_ends = {}
task_intervals = {}
for e in range(employees):
for t in range(tasks):
task_starts[e, t] = model.NewIntVar(0, MAX_TIME, 'task_starts_%i_%i' % (e, t))
task_ends[e, t] = model.NewIntVar(0, MAX_TIME, 'task_ends_%i_%i' % (e, t))
task_intervals[e, t] = model.NewOptionalIntervalVar(task_starts[e, t], task_durations[t], task_ends[e, t], shifts[e, t], 'interval_%i_%i' % (e, t))
# employees tasks cannot overlap
for e in range(employees):
model.AddNoOverlap(task_intervals[e, t] for t in range(tasks))
# all tasks must be realized
model.Add(sum(shifts[e, t] for e in range(employees) for t in range(tasks)) == tasks)
# each task is assigned exactly once
for t in range(tasks):
model.Add(sum(shifts[e, t] for e in range(employees)) == 1)
# make sure linked tasks are performed by the same employee (each consecutive pair of tasks in l, l[t] and l[t+1],
# must both be performed by the same user e, or not both not performed by the user)
# Note: this condition can be written more elegantly, but I tried to stick to the way the question was framed
for l in linkedTasks:
for t in range(len(l)-1):
for e in range(employees):
model.Add(shifts[e, l[t]] == shifts[e, l[t+1]])
# Goal: makespan (end of last task)
obj_var = model.NewIntVar(0, MAX_TIME, 'makespan')
model.AddMaxEquality(obj_var, [
task_ends[e, t] for e in range(employees) for t in range(tasks)
])
model.Minimize(obj_var)
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.parameters.num_search_workers = 8
solver.parameters.max_time_in_seconds = 30
result_status = solver.Solve(model)
if (result_status == cp_model.INFEASIBLE):
print('No feasible solution under constraints')
elif (result_status == cp_model.OPTIMAL):
print('Optimal result found, makespan=%i' % (solver.ObjectiveValue()))
elif (result_status == cp_model.FEASIBLE):
print('Feasible (non optimal) result found')
else:
print('No feasible solution found under constraints within time')
for e in range(employees):
for t in range(tasks):
if (solver.Value(shifts[e, t]) > 0):
print('employee %i-> task %i (start: %i, end: %i)' % (e, t, solver.Value(task_starts[e, t]), solver.Value(task_ends[e, t])))
This code results with a feasible assignment (optimal makespan=18), where the linked tasks are performed by the same employee as required.
So, to sum, while I wasn't able to pinpoint the issue, the approach seems reasonable as demonstrated by the code above.