如何使用 Pulp 定义多重分配问题的约束？

Question

我正在尝试解决分配问题： 可以根据主管和顾问使用的语言数量（共同语言越多越好）将一位主管分配给多名顾问。 限制条件是：

• 每个主管都有固定的可用于监督的小时数，即：14、11、7 或 0 小时/秒
• 每位顾问都有固定的可用于监督的小时数，即：6、3、2、1或0小时/秒
• 一名主管可以根据其可用的小时数拥有多名顾问进行监督（例如，一名主管 14 小时可以拥有 2 名顾问 6 小时和 2 名顾问 1 小时，或者只有 1 名顾问 6 小时，依此类推。不必涵盖主管的所有可用时间，而必须涵盖顾问的所有可用时间。）
• 选择的主管需要资历 >= 顾问的资历

   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

这是我第一次使用纸浆，所以如果你能帮助我，我将不胜感激。

Answer 1

使用

matrix

代替

dicts

；使用更多

lpDot

；像这样的东西：

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 implies
# 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