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!
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)