OR-Tools - Nurse scheduling - prevent shift gaps with binary constraints

Question

I am using OR-Tools to solve a problem similar to the Nurse Scheduling problem. The difference in my case is that when I schedule a "Nurse" for a shift, they must then work consecutive days (i.e., there can be no gaps between days worked).

Most of the similar questions point to this code. I have attempted to implement the answer adapted from there. However, I am getting output solutions which do not respecting the constraints.

The logic I was trying to follow is that I want to forbid patterns that have gaps. For example:

[1,0,1]
[1,0,0,1]
[1,0,0,0,1]

Below is an example of my code where for

# Modified from the code linked above:
def negated_bounded_span(works, start, length):
    sequence = []
    # Left border
    sequence.append(works[start].Not())

    # Middle
    for i in range(1,length+1):
        sequence.append(works[start + i])
    # Right border
    sequence.append(works[start + length + 1].Not())

    return sequence

for n in range(num_nurses):
    # nurse_days[(n,d)] is 1 if nurse n works on day d
    nrses = [nurse_days[(n, d)] for d in range(5)]
    
    for length in range(1, 4):
        for start in range(5 - length - 1):
            model.AddBoolOr(negated_bounded_span(nrses, start, length))

A modified excerpt of what the output of the above would look like is the following:

['Not(nurse_days_n0d0)', nurse_days_n0d1(0..1), 'Not(nurse_days_n0d2)']
['Not(nurse_days_n0d1)', nurse_days_n0d2(0..1), 'Not(nurse_days_n0d3)']
['Not(nurse_days_n0d2)', nurse_days_n0d3(0..1), 'Not(nurse_days_n0d4)']
['Not(nurse_days_n0d0)', nurse_days_n0d1(0..1), nurse_days_n0d2(0..1), 'Not(nurse_days_n0d3)']
['Not(nurse_days_n0d1)', nurse_days_n0d2(0..1), nurse_days_n0d3(0..1), 'Not(nurse_days_n0d4)']
['Not(nurse_days_n0d0)', nurse_days_n0d1(0..1), nurse_days_n0d2(0..1), nurse_days_n0d3(0..1), 'Not(nurse_days_n0d4)']

Thanks for your help in advance.

Similar questions reviewed: [1], [2], [3].

Answer 1

I don't use/know the syntax of or-tools, but you can probably construct a little boolean logic with constraints to do this.

Let's say we introduce a binary variable to annotate which d day that nurse n starts working:

s[n, d] ∈ {0, 1}

And to enforce only one sequence of days worked, we need to constrain to one start, for all nurses

∑ s[n, d] over all d <= 1    for all n ∈ N 

Then we know for any particular day, d that in order for nurse n to be working, they either have to start on that day or be working the day prior, right? That's it...

So,

working[n, d] <= s[n, d] + working[n, d-1]    for all n ∈ N, d ∈ {d: d ≠ d_0}

The constraint for d_0 is left for the interested coder. ;)

Answer 2

This can be implemented as follows:

Introduce variables for each employee and day:

worksOnDay[e, d] = true if the employee e works any shift on day d.

workStarted[e, d] = true if the employee e has started working on day d or earlier.

okToWork[e, d] = true if it is OK for employee e to work on day d.

Constrain worksOnDay[e, d] to be true if any shift is taken on that day, i.e. boolean OR of the shifts for that day, represented using AddMaxEquality() in OR-Tools. AddMaxEquality() effectively constrains the target variable to be the OR of the operands.

Constrain workStarted[e, d] to be true if it is true on the previous day d-1 or if the day is worked. (On the first day only if the day is worked).

Constrain okToWork[e, d] to be true if the work had not already been started on the previous day, or if the previous day is worked. (On the first two days, work is always OK as there can't have been any gap). In other words, if the work had already been started, then it is only OK to work if the previous day is also worked. The expression in pseudo-code would be (not workStarted[e, d - 1]) or (worksOnDay[e, d - 1]), but since OR-Tools doesn't directly allow such Boolean operators, in the code we have to introduce a helping variable constrained to be workStarted[e, d - 1].Not() and use it in the disjunction.

Finally, prevent work on days that it is not allowed by adding the implication that worksOnDay[e, d] implies okToWork[e, d]. This constraint will work in both directions and ensure that if okToWork[e, d] is false, then worksOnDay[e, d] will also be false since otherwise the constraint is violated.

I'm sorry, I work in c# and don't have a working Python installation, but it should be easy enough to code the equivalent constraints in Python. Here's the code:

        var model = new CpModel();

        IntVar[,,] work = new IntVar[numEmployees, numShifts, numDays];
        IntVar[,] worksOnDay = new IntVar[numEmployees, numDays];
        IntVar[,] workStarted = new IntVar[numEmployees, numDays];
        IntVar[,] okToWork = new IntVar[numEmployees, numDays];

        foreach (int e in Range(numEmployees))
        {
            foreach (int s in Range(numShifts))
            {
                foreach (int d in Range(numDays))
                {
                    work[e, s, d] = model.NewBoolVar($"work{e}_{s}_{d}");

                }
            }
        }

        for (int e = 0; e < numEmployees; e++)
        {
            for (int d = 0; d < numDays; d++)
            {
                worksOnDay[e, d] = model.NewBoolVar($"WorksOnDay{e}_{d}");
                workStarted[e, d] = model.NewBoolVar($"WorkStarted{e}_{d}");
                okToWork[e, d] = model.NewBoolVar($"OkToWork{e}_{d}");
            }
        }

        // WorksOnDay is true if any shift is taken on that day
        for (int e = 0; e < numEmployees; e++)
        {
            for (int d = 0; d < numDays; d++)
            {
                IEnumerable<IntVar> shiftsOnDay = (from int s in Range(numShifts) select work[e, s, d]);
                model.AddMaxEquality(worksOnDay[e, d], shiftsOnDay);
            }
        }

        // On the first day, WorkStarted is true if that day is worked
        for (int e = 0; e < numEmployees; e++)
        {
            model.Add(workStarted[e, 0] == worksOnDay[e, 0]);
        }

        // On subsequent days, WorkStarted is true if the day is worked, or if the work had been started on the day before
        for (int e = 0; e < numEmployees; e++)
        {
            for (int d = 1; d < numDays; d++)
            {
                model.AddMaxEquality(workStarted[e, d], new List<IntVar>() { workStarted[e, d - 1], worksOnDay[e, d] });
            }
        }

        // On the first and second days, there cannot have been a gap, work is always OK
        for (int e = 0; e < numEmployees; e++)
        {
            model.Add(okToWork[e, 0] == 1);
            model.Add(okToWork[e, 1] == 1);
        }

        // For the third day and beyond, work is OK if the work had not been started by the previous day, or if the previous day is worked.
        for (int e = 0; e < numEmployees; e++)
        {
            for (int d = 2; d < numDays; d++)
            {
                IntVar workNotStartedYesterday = model.NewBoolVar("WorkNotStarted");
                model.Add(workNotStartedYesterday == (LinearExpr)workStarted[e, d - 1].Not());
                model.AddMaxEquality(okToWork[e, d], new List<IntVar>() { workNotStartedYesterday, worksOnDay[e, d - 1] });
            }
        }

        // Prevent work on days that it is not allowed
        for (int e = 0; e < numEmployees; e++)
        {
            for (int d = 0; d < numDays; d++)
            {
                // Working on a day implies that it is OK to work on that day.
                // Stated otherwise, either it is ok to work on the day, or it is not worked on the day.
                model.AddImplication(worksOnDay[e, d], okToWork[e, d]);
            }
        }