How do I define the constraints of a multiple assignment problem with Pulp?

Question

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:

• each supervisor has a fixed number of hours that it can use to supervise, namely: 14, 11, 7, or 0 hour/s
• each consultant has a fixed number of hours that it can use to be supervised, namely: 6, 3, 2, 1, or 0 hour/s
• a supervisor can have multiple consultants to supervise according to the number of hours the supervisor is available (e.g. a supervisor with 14 hours can have 2 consultants with 6 hours and 2 with 1 hour, or just 1 with 6 hours, and so on. Not all the available hours of the supervisor have to be covered, while the hours of the consultant have to be all covered.)
• a supervisor, to be chosen, needs to have a seniority >= of the seniority of the consultant

   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.

Answer 1

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