I’m trying to solve a classic optimization problem using PulP – I have a set of patients with durations for their job, chairs (a patient must sit on a chair to complete their job), and nurses (that are assigned to the patients) and one of the constrants is that no two patients on the same chair should have overlapping jobs.

Here’s the code I’ve written to encode the decision variables:

# Decision variables
x = pulp.LpVariable.dicts("x", [(p['id'], n['id']) for p in patients for n in nurses], 0, 1, pulp.LpBinary)
y = pulp.LpVariable.dicts("y", [(p['id'], c) for p in patients for c in range(num_chairs)], 0, 1, pulp.LpBinary)
start_times = pulp.LpVariable.dicts("start_time", [p['id'] for p in patients], cat='Continuous')

x describes if a patient is assigned to a nurse
y describes if a patient is assigned to a chair

I have other constraints written that are working such that each patient is assigned to exactly one nurse and exactly one chair.

Here’s the code I’ve written to encode the constraint that no two patients assigned to the same chair should have overlapping jobs:

for c in range(num_chairs):
    for t in range(open_time, close_time):
        prob += pulp.lpSum([y[p['id'], c] for p in patients if
                            (start_times[p['id']] <= t <= start_times[p['id']] + p['duration'])]) <= 1

However, this constraint is not working properly because the code outputted an optimal solution that looked like the following for a chair — however, patient 0 and patient 4 are overlapping.

Chair 3 schedule:
Patient 0: 08:20 - 09:20
Patient 4: 09:10 - 10:10
Patient 6: 10:10 - 12:10