Employees shift problem - link missions together

Question

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.

---

Problem:

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.

---

EDIT:

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?

Heliopolis

Suggestion: used named tuples instead of Item1 and Item2. Much easier to read and less error prone. – Beaumarchais

What constraint solver? And what does this line adding a bool to model do? model.Add(linkedShifts[i] == linkedShifts[i + 1]); – Beaumarchais

@IanMercer Solver is Google CpSat, from or-tools package. This line is part of a loop that forces all the IntVars in linkedShifts to be equal. – Heliopolis

Why don't you use the same Boolean variables for all shifts that must be together ? – Ransom

You may need to capture the loop variable inside the loop. See stackoverflow.com/questions/271440 – Beaumarchais

@LaurentPerron tried your method, see my edit. – Heliopolis

@IanMercer tried that, nothing changed – Heliopolis

Try to remove constraints one by one to find the wrong one. – Ransom

@LaurentPerron 2 groups of 2 linked missions w/ 35 employees, it represents 75 constraints to remove one by one. So I'll do it as a last resort if nobody can help me – Heliopolis

Start by reducing the model (5 employes...) – Ransom

Answer 1

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.

Grimsby