# Violation of specific constraint in Pulp

I have successfully implemented a program where I allocate N truck drivers to M gathering hubs for each one of the days of the week. The constraints I have implemented are:

• A driver cannot work more than 6 days, i.e. 1 day to rest
• A driver cannot be allocated in more than 1 hubs for each day
• Each hub must satisfy its driver requirements for each day of the week
• A driver must work his days at one hub instead of many.

The program runs smoothly, satisfies the overall objective and outputs a schedule for each hub-driver pair.

However, the extra constraint that forces the drivers to work at one hub (constraint 4), instead of their working days being split into many hubs, is violated and assigns some drivers to many hubs.

How can that be fixed?

Thank you

import pulp
import pandas as pd
import numpy as np

day_requirement = [[3, 4, 3, 4, 5, 3, 3],
[3, 4, 4, 3, 4, 5, 5],
[1, 1, 1, 1, 1, 1, 1],
[2, 2, 2, 2, 2, 2, 2],
[2, 4, 3, 2, 2, 2, 2],
[6, 5, 3, 3, 3, 5, 4],
[2, 3, 2, 2, 2, 1, 2]]

total_day_requirements = ([sum(x) for x in zip(*day_requirement)])

hub_names = {0: 'Hub 1',
1: 'Hub 2',
2: 'Hub 3',
3: 'Hub 4',
4: 'Hub 5',
5: 'Hub 6',
6: 'Hub 7'}

total_drivers = max(total_day_requirements)  # number of drivers
total_hubs = len(day_requirement)  # number of hubs

days = 7

def schedule(drivers, hubs, day_requirement):
# driver_names = ilm_riders['riders']
driver_names = ['Driver_{}'.format(i) for i in range(drivers)]
var = pulp.LpVariable.dicts('VAR', (range(hubs), range(drivers), range(days)), 0, 1, 'Binary')
problem = pulp.LpProblem('shift', pulp.LpMinimize)

obj = None
for h in range(hubs):
for driver in range(drivers):
for day in range(days):
obj += var[h][driver][day]
problem += obj

#  we add binary variables z indicating if a driver is active on a hub:
z = pulp.LpVariable.dicts('Z', (range(hubs), range(drivers)), 0, 1, 'Binary')
# minimize the sum of drivers active on hubs
for h in range(hubs):
for driver in range(drivers):
obj += z[h][driver]
problem += obj

# Add constraints to connect z with VAR:
for driver in range(drivers):
for h in range(hubs):
problem += z[h][driver] <= pulp.lpSum(var[h][driver][day] for day in range(days))
problem += days * z[h][driver] >= pulp.lpSum(var[h][driver][day] for day in range(days))

# if a driver works one day at a hub, he cannot work that day in a different hub obviously
for driver in range(drivers):
for day in range(days):
problem += pulp.lpSum([var[h][driver][day] for h in range(hubs)]) <= 1

# schedule must satisfy daily requirements of each hub
for day in range(days):
for h in range(hubs):
problem += pulp.lpSum(var[h][driver][day] for driver in range(drivers)) == \
day_requirement[h][day]

# a driver cannot work more than 6 days
for driver in range(drivers):
problem += pulp.lpSum([var[h][driver][day] for day in range(days) for h in range(hubs)]) \
<= 6

# for driver in range(drivers):
#     problem += pulp.lpSum([var[h][driver][day] for day in range(days) for h in range(hubs)]) >= 5

# Solve problem. We have a very complex solution so we set a timeout at 10secs.
status = problem.solve(pulp.PULP_CBC_CMD(msg=False, timeLimit=10))

idx = pd.MultiIndex.from_product([hub_names.values(), driver_names], names=['Hub', 'Driver'])

col = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday']
# col = ['Day_{}'.format(i) for i in range(days)]
dashboard = pd.DataFrame(0, idx, col)

for h in range(hubs):
for driver in range(drivers):
for day in range(days):
if var[h][driver][day].value() > 0.0:
dashboard.loc[hub_names[h], driver_names[driver]][col[day]] = 1

# print(dashboard)

driver_table = dashboard.groupby('Driver').sum()
driver_sums = driver_table.sum(axis=1)
# print(driver_sums)

day_sums = driver_table.sum(axis=0)
# print(day_sums)

print("Status", pulp.LpStatus[status])
return driver_sums, dashboard, status

driver_sums, dashboard, status = schedule(total_drivers, total_hubs, day_reqs)
while (driver_sums > 6).any() or status == -1:
print('Staus infeasible OR one or more drivers have been allocated more than 6 days of work so '
'driver: {}->{}'.format(total_drivers, total_drivers + 1))
total_drivers += 1
driver_sums, dashboard, status = schedule(total_drivers, total_hubs, day_reqs)

# dashboard = schedule(total_drivers, total_hubs, day_reqs)
driver_table = dashboard.groupby('Driver').sum()
driver_sums = driver_table.sum(axis=1)
# print(driver_sums)
day_sums = driver_table.sum(axis=0)

$$$$
`

Introduce linear constraints: $$\sum_{\text{h}} z[\text{h}][\text{driver}] \le 1 \quad\text{for each driver}$$

• Thank you for the answer. The problem is that when i add this constraint, then constraint 1, i.e. A driver cannot work more than 6 days, i.e. 1 day to rest, seems to be violated and only a few drivers work 6 days; most of them end up working 1-5 days. Can this somehow be amended?
– azal
Jul 25 at 17:27
• How does working 1-5 days violate the "cannot work more than 6 days" rule? Jul 25 at 18:54
• You’re right. Please Let me rephrase: I would like the truck drivers to work exactly 6 days per week and 1 day off. However, if I set the constraint to == 6 the problem seems to be unsolvable (?)
– azal
Jul 25 at 21:27
• The requirements add up to 134, which is not a multiple of 6. Jul 25 at 23:52
• Could you please elaborate on that? I literally have no idea what that means
– azal
Jul 26 at 5:06