Consecutive shifts in the "Nurse Scheduling" problem using OR-Tools?

Question

I'm using OR-Tools to try and solve a problem similar to the Nurse Scheduling problem, but where the shift length is different for each nurse (or, in my case, students). My current approach is to divide up shifts into the blocks of the smallest common denominator (in my case 5 minutes), and require that:

1. If a student is scheduled that day, they must be scheduled for the appropriate number of blocks
2. Those blocks must be consecutive

I am also setting constraints on when students are/aren't available. My current code below seems to largely work, BUT I find strange cases where a solution is not found. In the simple example below for instance, if I constrain Alice to be unavailable during blocks 3 and 4 (indexing from zero), the solver fails, even though a solution exists. Any other set of constraints (with a viable solution) works and fits the above requirements. Am I doing something wrong in defining my constraints? Is there a better way to implement this? I've seen this example, but I am new to this and don't quite understand what's going on, so was hoping to implement something simpler.

from ortools.sat.python import cp_model

#assign student[0] to be a placeholder, stands for "no students during this time"
student_names = ['none','Alice'] 

#number of sessions per student; i.e. Alice needs 1 session
student_sessions = [0,1] 

#how many 5-minute blocks for each student's sessions; i.e. Alice's sessions are 3x5 minutes long
student_blocks = [0,3] 

#constraints, in the form (student,day,block); i.e. Alice can't be scheduled in block 3 on day 0
constraints = [(1,0,3)] 

#define the length of the day
num_blocks = 6

#define the number of days in the week
num_days = 1

num_students = len(student_sessions) 
print('Scheduling',num_students-1,'students') #recall that student[0] is just a placeholder
students = range(num_students)
blocks = range(num_blocks)
days = range(num_days)

#create the model
model = cp_model.CpModel()

#create the primary variable 'slots', a list of booleans with coordinates given by student, day, block
slots = {}
for s in students:
    for d in days:
        for b in blocks:
            slots[(s,d,b)] = model.NewBoolVar('block_s%id%ib%i' % (s,d,b))

#no more than 1 student per block
for d in days:
    for b in blocks:
        model.Add(sum(slots[(s,d,b)] for s in students)==1)

#require the total number of blocks per student = # sessions x blocks per session
for s in students[1:]: #we always skip over constraints for student[0]; they can fill in everything else
    total = 0
    for d in days:
        for b in blocks:
            total += slots[(s,d,b)]
    model.Add(total == int(student_sessions[s]*student_blocks[s]))

#each day, student should either have no blocks, or a number of blocks equaling their session length
for d in days:
    for s in students[1:]:
        blocked = model.NewBoolVar('blocking')
        noblock = model.NewBoolVar('noblock')
        model.Add(sum(slots[(s,d,b)] for b in blocks)==student_blocks[s]).OnlyEnforceIf(blocked)
        model.Add(sum(slots[(s,d,b)] for b in blocks)==0).OnlyEnforceIf(noblock)
        model.AddBoolOr([blocked,noblock])

# require session continuity, i.e. all a students blocks should be sequential, not spread out over a day
for d in days:
    for s in students[1:]:
        for b in blocks[:-(student_blocks[s])]:
            cont = model.NewBoolVar('cont')
            startBlock = model.NewBoolVar('startBlock')
            model.Add(sum([slots[(s,d,b)]])==0).OnlyEnforceIf(startBlock)
            model.Add(sum(slots[(s,d,b+i)] for i in range(student_blocks[s]))==student_blocks[s]).OnlyEnforceIf(cont)
            model.AddBoolXOr([startBlock,cont])

for ct in constraints:
    model.Add(slots[ct]==0)

solver = cp_model.CpSolver()
solver.Solve(model)
for d in days:
    print('Day',d)
    for b in blocks:
        for s in students:
            if solver.Value(slots[(s,d,b)])==1:
                print(student_names[s],'in block',b)

Answer 1

The code below incorporates the suggestions from Stradivari and seems to work:

from ortools.sat.python import cp_model

def negated_bounded_span(works, start, length):
    """Filters an isolated sub-sequence of variables assined to True.
  Extract the span of Boolean variables [start, start + length), negate them,
  and if there is variables to the left/right of this span, surround the span by
  them in non negated form.
  Args:
    works: a list of variables to extract the span from.
    start: the start to the span.
    length: the length of the span.
  Returns:
    a list of variables which conjunction will be false if the sub-list is
    assigned to True, and correctly bounded by variables assigned to False,
    or by the start or end of works.
  """
    sequence = []
    # Left border (start of works, or works[start - 1])
    if start > 0:
        sequence.append(works[start - 1])
    for i in range(length):
        sequence.append(works[start + i].Not())
    # Right border (end of works or works[start + length])
    if start + length < len(works):
        sequence.append(works[start + length])
    return sequence

#assign student[0] to be a placeholder, stands for "no students during this time"
student_names = ['none','Alice'] 

#number of sessions per student; i.e. Alice needs 1 session
student_sessions = [0,1] 

#how many 5-minute blocks for each student's sessions; i.e. Alice's sessions are 3x5 minutes long
student_blocks = [0,3] 

#constraints, in the form (student,day,block); i.e. Alice can't be scheduled in block 3 on day 0
constraints = [(1,0,5)] 

#define the length of the day
num_blocks = 6

#define the number of days in the week
num_days = 1

num_students = len(student_sessions) 
print('Scheduling',num_students-1,'students') #recall that student[0] is just a placeholder
students = range(num_students)
blocks = range(num_blocks)
days = range(num_days)

#create the model
model = cp_model.CpModel()

#create the primary variable 'slots', a list of booleans with coordinates given by student, day, block
slots = {}
for s in students:
    for d in days:
        for b in blocks:
            slots[(s,d,b)] = model.NewBoolVar('block_s%id%ib%i' % (s,d,b))

#no more than 1 student per block
for d in days:
    for b in blocks:
        model.Add(sum(slots[(s,d,b)] for s in students)==1)

#require the total number of blocks per student = # sessions x blocks per session
for s in students[1:]: #we always skip over constraints for student[0]; they can fill in everything else
    total = 0
    for d in days:
        for b in blocks:
            total += slots[(s,d,b)]
    model.Add(total == int(student_sessions[s]*student_blocks[s]))

#each day, student should either have no blocks, or a number of blocks equaling their session length
for d in days:
    for s in students[1:]:
        blocked = model.NewBoolVar('blocking')
        noblock = model.NewBoolVar('noblock')
        model.Add(sum(slots[(s,d,b)] for b in blocks)==student_blocks[s]).OnlyEnforceIf(blocked)
        model.Add(sum(slots[(s,d,b)] for b in blocks)==0).OnlyEnforceIf(noblock)
        model.AddBoolOr([blocked,noblock])

#require sessions be the correct length
for s in students[1:]:
    for d in days:
        sts = [slots[(s,d,b)] for b in blocks]
        for length in range(1, student_blocks[s]):
                for start in range(len(sts) - length + 1):
                    model.AddBoolOr(negated_bounded_span(sts, start, length))

for ct in constraints:
    model.Add(slots[ct]==0)

solver = cp_model.CpSolver()
solver.Solve(model)
for d in days:
    print('Day',d)
    for b in blocks:
        for s in students:
            if solver.Value(slots[(s,d,b)])==1:
                print(student_names[s],'in block',b)