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?


1 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$.

  • $\begingroup$ I guess I should've paid more attention in my "Logic and Set theory" course because this was exactly what I've been looking for. The solution works! Only downside is that adding this constraint increases the calculation time by a factor of 20. Thanks for helping out! $\endgroup$
    – Joep
    Apr 29, 2020 at 18:16
  • $\begingroup$ Glad to help. You might consider generating these constraints dynamically only if they are violated. $\endgroup$
    – RobPratt
    Apr 29, 2020 at 19:06
  • $\begingroup$ What is the benefit of dynamically generating these constraints when they are violated? And more importantly; how do I do that? $\endgroup$
    – Joep
    Apr 29, 2020 at 19:53
  • $\begingroup$ The motivation would be to reduce the run time because most of the constraints are naturally satisfied so their presence just clogs up the solver. The idea is to include only the ones that are needed. I don't use PuLP, so I can't tell you how to implement it there. Some solvers support lazy constraints or cut callbacks for this purpose. $\endgroup$
    – RobPratt
    Apr 29, 2020 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.