How to set these constraints in a linear optimization problem (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 employees:
    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

Now I want to model two additional constraints. The first one should be fairly simple I hope. If an employee works on saturday (6th day of the week), he/she must also work on sunday (7th day of the week). The idea is that one either works all weekend, or is free all weekend. I tried the following:

for i in employees:
    m += N[(i, 6)] - N[(i, 7)] >= 0
    m += N[(i, 7)] - N[(i, 6)] >= 0

But these constraints turn out to be non-binding of course because when N[(i, 6)] = 0 and N[(i, 7)] = 0 the constraints are also satisfied. First question: how do I rewrite these constraints?

Then, on top of that I also want to implement a way to make sure that employees can only work odd or even weekends but don't really know where to start. I assume I must introduce two extra decision variables "works even-weekends" and "works odd-weekends" and set some constraints to enforce these. So the second question is: how could I implement this?

Ideally I'd rather be able to help myself with these kind of questions so reading materials (specific chapters/sections would be nice) are very welcome as well!

Answer 1

The rule "works on Saturday implies works on Sunday" can be expressed as $$(D_{i,6} \lor N_{i,6}) \implies (D_{i,7} \lor N_{i,7}),$$ which can be rewritten in conjunctive normal form as follows: \begin{equation} \neg (D_{i,6} \lor N_{i,6}) \lor (D_{i,7} \lor N_{i,7}) \\ (\neg D_{i,6} \land \neg N_{i,6}) \lor (D_{i,7} \lor N_{i,7}) \\ (\neg D_{i,6} \lor D_{i,7} \lor N_{i,7}) \land (\neg N_{i,6} \lor D_{i,7} \lor N_{i,7}), \end{equation} yielding linear constraints $$(1- D_{i,6} + D_{i,7} + N_{i,7}) \ge 1) \land (1- N_{i,6} + D_{i,7} + N_{i,7} \ge 1),$$ equivalently $$(D_{i,6} \le D_{i,7} + N_{i,7}) \land (N_{i,6} \le D_{i,7} + N_{i,7}).$$ Because $D_{i,6}+N_{i,6} \le 1$, you can strengthen these as a single constraint $$D_{i,6} + N_{i,6} \le D_{i,7} + N_{i,7}. \tag1$$

More simply, you can rewrite $$\neg V_{i,6} \implies \neg V_{i,7}$$ in conjunctive normal form as $$V_{i,6} \lor \neg V_{i,7},$$ yielding linear constraint $$V_{i,6} + 1 - V_{i,7} \ge 1,$$ equivalently, $$V_{i,6} \ge V_{i,7},$$ which is just the complement of $(1)$.

Your description sounds like you might also want the converse that working Sunday implies working Saturday. If so, that is $$V_{i,7} \ge V_{i,6},$$ so if you want both implications, just impose $$V_{i,6} = V_{i,7}.$$

For your second question, I think you just want some conflict constraints of the form $\text{Odd}_i + \text{Even}_i \le 1,$ together with \begin{align} 1 - V_{i,j} &\le \text{Odd}_i &&\text{for $j$ in odd weekend}\\ 1 - V_{i,j} &\le \text{Even}_i &&\text{for $j$ in even weekend} \end{align}