How do you encode a required number of consecutive days off in a set time-span constraint into an OR-Tools CP-SAT Schedule?

Question

I'm developing a system that generates a roster for an air ambulance, and obviously these rosters are highly constrained and have loads of rules on how much time off a pilot should have. One of these limits is "A pilot can have no less than [2] Consecutive Days Off in the previous [14] days." I have been trying to represent this rule as a constraint for a while and I'm a bit stuck.

I am representing duties as a BoolVar dictionary:

duties = {}
for p in p_n:
    for x in x_n:
        for d in d_n:
            duties[(p, x, d)] = model.NewBoolVar(f"duty_p{p}_x{x}_d{d}")

Where p is pilot index (each pilot is referred to as 0, 1, 2...), x is the day index, d d is the duty type. This type is 0 or 4 for days when a pilot is off and 1, 2, 3, 5, 6, 7, 8 for days when a pilot is on (all of these other duties being different types of duties). duty_p1_x1_d0 = 1 would mean pilot 1 was OFF on day 1. How would I go about representing the aforementioned rule in this representation?

I originally tried something along the lines of sum(duties[p, x, 0] * duties[(p, x+1, 0)] for x in range(0, 14)) >= 1 but this failed due to the nature of BoolVars in Or-Tools. Any advice would be appreciated, I'm a bit stumped!

Answer 1

You should have a look at the shift_scheduling example.

In particular, the soft sequence constraint defines 4 values for a sequence of Boolean variables. A hard lower and upper bound on the number of consecutive ones, and a soft lower and upper bound in the same number.

Now, to require a minimum consecutive numbers of Boolean variables assigned to True, the trick is to forbid all sequences of [False, True * forbidden_size, False], with 1 <= forbidden_size < min_consecutive. This will be done with a lot of clauses.

  min_number = 3
  sequence = [..]  # Sequence of Boolean variables

  for forbidden_size in range(1, min_number - 1):
    for start in range(len(sequence) - forbidden_size - 2):
    forbidden_sequence = []
    forbidden_sequence.append(sequence[start])
    for index in range(start + 1, start + forbidden_size):
      forbidden_sequence.append(sequence[index].Not())
    forbidden_sequence.append(sequence[start + forbidden_size].Not()
    model.AddBoolOr(forbidden_sequence)