I am trying to solve an assignment problem: A supervisor can be assigned to multiple consultants according to the number of languages a supervisor and a consultant speak (the more languages they have in common the better). The constraints are:
supervisor_h = ... # number of hours of the availability per each supervisor
consultant_h = ... # number of hours needed per each consultant
y = pulp.LpVariable.dicts("pairs", [(i,j) for i in supervisors for j in consultants] ,cat='Binary')
prob = pulp.LpProblem("matching", pulp.LpMaximize)
prob += pulp.lpSum([costs[i][m] * y[(i,j)] for i in supervisors for m, j in enumerate(consultants)])
# each supervisor can have a number of consultants >= 1
for i in supervisors:
prob += pulp.lpSum(y[(i,j)] for j in consultants) >= 1
# each consultant can have only one supervisor
for j in consultants:
prob += pulp.lpSum(y[(i,j)] for i in supervisors) <= 1
# a supervisor can accept a consultant if the number of hours the supervisor still has available is >= than the number of hours requested by the consultant
# Here I have a problem in defining the constraint
for n, i in enumerate(supervisors):
prob += supervisor_h[n] - pulp.lpSum(qcee_h[m] for m, j in enumerate(consultants)) <= consultant_h[n]
# I have the same problem in defining the constraint for the seniority
It is the first time I use pulp, so if you can help me I appreciate it.
Use matrix
instead of dicts
; use more lpDot
; something like:
import pulp
supervisor_h = (11, 14, 11, 7) # number of hours of the availability per each supervisor
consultant_h = (3, 1, 6, 2, 3) # number of hours needed per each consultant
supervisor_sen = (3.5, 5.5, 6, 5) # seniorities
consultant_sen = (1, 2, 4, 4.5, 3)
supervisors = range(len(supervisor_h))
consultants = range(len(consultant_h))
costs = (
(60, 50, 57, 40, 55),
(50, 45, 65, 44, 50),
(70, 60, 65, 40, 51),
(49, 51, 50, 51, 48),
)
pairs = pulp.LpVariable.matrix(
name='pairs', cat=pulp.LpBinary, indices=(supervisors, consultants),
)
prob = pulp.LpProblem(name='matching', sense=pulp.LpMaximize)
prob.setObjective(pulp.lpDot(costs, pairs))
# each supervisor must have a number of consultants >= 1
for supervisor, pair_row in zip(supervisors, pairs):
prob.addConstraint(name=f'sup{supervisor}_mincount', constraint=pulp.lpSum(pair_row) >= 1)
# each consultant must have exactly one supervisor. the hours load that a given consultant imposes
# on a supervisor is implied.
for consultant in consultants:
prob.addConstraint(
name=f'con{consultant}_maxcount',
constraint=pulp.lpSum(row[consultant] for row in pairs) == 1,
)
# each supervisor has a maximum number of available hours. each consultant contribution to the
# supervisor hours load is either 0 or the entire hour demand from that consultant.
for supervisor, pair_row, hours in zip(supervisors, pairs, supervisor_h):
prob.addConstraint(
name=f'sup{supervisor}_hourmax',
constraint=pulp.lpDot(pair_row, consultant_h) <= hours,
)
# consultant seniority is at most supervisor seniority.
for consultant, sen in zip(consultants, consultant_sen):
prob.addConstraint(
name=f'con{consultant}_sen',
constraint=sen <= pulp.lpDot(
supervisor_sen,
[pairs[s][consultant] for s in supervisors],
),
)
print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
for consultant in consultants:
print(f'Consultant {consultant} has been assigned supervisor ',
next(
s
for s in supervisors
if pairs[s][consultant].value() > 0.5
),
)
matching:
MAXIMIZE
60*pairs_0_0 + 50*pairs_0_1 + 57*pairs_0_2 + 40*pairs_0_3 + 55*pairs_0_4 + 50*pairs_1_0 + 45*pairs_1_1 + 65*pairs_1_2 + 44*pairs_1_3 + 50*pairs_1_4 + 70*pairs_2_0 + 60*pairs_2_1 + 65*pairs_2_2 + 40*pairs_2_3 + 51*pairs_2_4 + 49*pairs_3_0 + 51*pairs_3_1 + 50*pairs_3_2 + 51*pairs_3_3 + 48*pairs_3_4 + 0
SUBJECT TO
sup0_mincount: pairs_0_0 + pairs_0_1 + pairs_0_2 + pairs_0_3 + pairs_0_4 >= 1
sup1_mincount: pairs_1_0 + pairs_1_1 + pairs_1_2 + pairs_1_3 + pairs_1_4 >= 1
sup2_mincount: pairs_2_0 + pairs_2_1 + pairs_2_2 + pairs_2_3 + pairs_2_4 >= 1
sup3_mincount: pairs_3_0 + pairs_3_1 + pairs_3_2 + pairs_3_3 + pairs_3_4 >= 1
con0_maxcount: pairs_0_0 + pairs_1_0 + pairs_2_0 + pairs_3_0 = 1
con1_maxcount: pairs_0_1 + pairs_1_1 + pairs_2_1 + pairs_3_1 = 1
con2_maxcount: pairs_0_2 + pairs_1_2 + pairs_2_2 + pairs_3_2 = 1
con3_maxcount: pairs_0_3 + pairs_1_3 + pairs_2_3 + pairs_3_3 = 1
con4_maxcount: pairs_0_4 + pairs_1_4 + pairs_2_4 + pairs_3_4 = 1
sup0_hourmax: 3 pairs_0_0 + pairs_0_1 + 6 pairs_0_2 + 2 pairs_0_3
+ 3 pairs_0_4 <= 11
sup1_hourmax: 3 pairs_1_0 + pairs_1_1 + 6 pairs_1_2 + 2 pairs_1_3
+ 3 pairs_1_4 <= 14
sup2_hourmax: 3 pairs_2_0 + pairs_2_1 + 6 pairs_2_2 + 2 pairs_2_3
+ 3 pairs_2_4 <= 11
sup3_hourmax: 3 pairs_3_0 + pairs_3_1 + 6 pairs_3_2 + 2 pairs_3_3
+ 3 pairs_3_4 <= 7
con0_sen: 3.5 pairs_0_0 + 5.5 pairs_1_0 + 6 pairs_2_0 + 5 pairs_3_0 >= 1
con1_sen: 3.5 pairs_0_1 + 5.5 pairs_1_1 + 6 pairs_2_1 + 5 pairs_3_1 >= 2
con2_sen: 3.5 pairs_0_2 + 5.5 pairs_1_2 + 6 pairs_2_2 + 5 pairs_3_2 >= 4
con3_sen: 3.5 pairs_0_3 + 5.5 pairs_1_3 + 6 pairs_2_3 + 5 pairs_3_3 >= 4.5
con4_sen: 3.5 pairs_0_4 + 5.5 pairs_1_4 + 6 pairs_2_4 + 5 pairs_3_4 >= 3
VARIABLES
0 <= pairs_0_0 <= 1 Integer
0 <= pairs_0_1 <= 1 Integer
0 <= pairs_0_2 <= 1 Integer
0 <= pairs_0_3 <= 1 Integer
0 <= pairs_0_4 <= 1 Integer
0 <= pairs_1_0 <= 1 Integer
0 <= pairs_1_1 <= 1 Integer
0 <= pairs_1_2 <= 1 Integer
0 <= pairs_1_3 <= 1 Integer
0 <= pairs_1_4 <= 1 Integer
0 <= pairs_2_0 <= 1 Integer
0 <= pairs_2_1 <= 1 Integer
0 <= pairs_2_2 <= 1 Integer
0 <= pairs_2_3 <= 1 Integer
0 <= pairs_2_4 <= 1 Integer
0 <= pairs_3_0 <= 1 Integer
0 <= pairs_3_1 <= 1 Integer
0 <= pairs_3_2 <= 1 Integer
0 <= pairs_3_3 <= 1 Integer
0 <= pairs_3_4 <= 1 Integer
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
At line 2 NAME MODEL
At line 3 ROWS
At line 23 COLUMNS
At line 164 RHS
At line 183 BOUNDS
At line 204 ENDATA
Problem MODEL has 18 rows, 20 columns and 80 elements
Coin0008I MODEL read with 0 errors
Result - Optimal solution found
Objective value: 301.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.01
Time (Wallclock seconds): 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.01 (Wallclock seconds): 0.01
Consultant 0 has been assigned supervisor 2
Consultant 1 has been assigned supervisor 2
Consultant 2 has been assigned supervisor 1
Consultant 3 has been assigned supervisor 3
Consultant 4 has been assigned supervisor 0