CODEWITHSUNDEEP
pythonlinear-programmingpulp
Joep
Joep

Reputation: 43

How to properly write constraints over multiple indexes?

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 produce sensible schedules is the following.

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

Another constraint that does seem to have effect (i.e. no employees were assigned day shifts the following two days after a night shift after implementing this constraint)

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

I hope the implementation of the aforementioned constraint speaks for itself. If clarification is needed please ask!

In the same fashion I am trying to enforce a constraint that there is a maximum numbers of consecutive days an employee can (day) shifts assigned.

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

However, this does not seem to have any effect on the produced schedules as employees are still assigned 4+ days in a row.

What am I missing here? Thanks in advance!

Upvotes: 0

Views: 544

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16782

You can see that

D[(i, j)] + D[(i, j + 1)] + D[(i, j + 2)] + D[(i, j + 3)] <= 4

is never binding. I think you want:

D[(i, j)] + D[(i, j + 1)] + D[(i, j + 2)] + D[(i, j + 3)] + D[(i, j + 4)] <= 4

Upvotes: 1

Related Questions