2
$\begingroup$

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. The question is: how do I do this?

Thanks in advance!

$\endgroup$
4
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\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 at 18:16
  • $\begingroup$ Glad to help. You might consider generating these constraints dynamically only if they are violated. $\endgroup$ – RobPratt Apr 29 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 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 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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