How to enforce this specific constraint in PuLP?

Question

I am trying to implement an employee (nurse) scheduling problem and seek some advice on how to implement a specific constraint.The problem is as follows: There is a set of employees and days (both labeled by integer numbers). Each employee can be assigned a day shift D[(i, j)] , nightshift N[(i, j)] or a day off V[(i, j)]. These are my decision variables:

D = LpVariable.dicts(name="Dagdienst", indexs=[(i, j) for i in employees for j in days], cat='Binary')
N = LpVariable.dicts(name="Nachtdienst", indexs=[(i, j) for i in employees for j in days], cat='Binary')
V = LpVariable.dicts(name="Vrij", indexs=[(i, j) for i in employees for j in days], cat='Binary')

An example constraint to enforce either a dayshift, nightshift or day-off for each day and each employee is the following.

for i in employees:
    for j in days:
        m += D[(i, j)] + N[(i, j)] + V[(i, j)] == 1

To give you some idea what I'm working with, two other constraints are the following:

for i in employees:
    for j in range(1, len(days)-1):
        m += N[(i, j)] + D[(i, (j + 1))] <= 1
        m += N[(i, j)] + D[(i, (j + 2))] <= 1

max_consecutive_days = 4
for i in medewerkers:
    for j in range(1, (len(days)+1 - max_consecutive_days)):
        m += D[(i, j)] + D[(i, j + 1)] + D[(i, j + 2)] + D[(i, j + 3)]+ D[(i, j + 4)] <= max_consecutive_days

The first constraint enforces two days off after a night shift and the second one makes sure an employee cannot be assigned more than 4 consecutive day shifts. I hope the implementation of the aforementioned constraint speak for themselves, if not please ask.

In the same fashion I am trying to implement a constraint that ensures a break (a break is a series of day-offs) always has a minimum length of 2 days. It must enforce something like the following:

for i in medewerkers:
    for j in range(1, len(days):
        m += (V[(i, j)] + V[(i, j + 1)]) mod 2 == 0

However, taking the modulo is not allowed here and this conditional constraint must be formulated in a different way.

How do I do this?

Answer 1

In other words, you want to avoid a pattern of 010. As a logical proposition: $$\neg (\neg V_{i,j} \land V_{i,j+1} \land \neg V_{i,j+2}),$$ which you can write in conjunctive normal form as: $$V_{i,j} \lor \neg V_{i,j+1} \lor V_{i,j+2}.$$ The corresponding linear constraint is: $$V_{i,j} + (1 - V_{i,j+1}) + V_{i,j+2} \ge 1,$$ equivalently, $$V_{i,j} - V_{i,j+1} + V_{i,j+2} \ge 0.$$

For the boundary cases, treat $V_{i,j}$ or $V_{i,j+2}$ as $0$.