python - 使用python的分配优化问题

Question

我有一个部门列表，每个部门都有一定的容量。例如:

Sectors = { 
       "1A": 80,
       "1B": 20, 
       "2A": 10, 
       "3A": 50,
       "3B": 20,
       "3C": 110
     }

我还有一个团队列表，每个团队都有一定数量的成员，例如:

Teams = {
   "TeamA":20, 
   "TeamB":15, 
   "TeamC":100, 
   "TeamD":20,
   "TeamF":85, 
   "TeamG":35,
   "TeamH":25,
   "TeamI":7,
 } 

请注意，Teams 多于 Sectors，并且每个团队中的团队成员总数高于扇区容量总数，因此会有没有扇区的团队。
现在我需要将每个团队与部门匹配，以便:

分配扇区的团队中的团队成员总和最大化

对于 约束有:

团队大小不能超过分配的扇区大小(例如:TeamC 只能作为一个整体放入扇区 3C，除非将其拆分为约束 2 中描述的两个)

现在这是更难的一个:

一个Team可以分配到多个扇区，但是扇区需要以相同的编号开始(例如:可以将TeamC分配给1A和1B，但不能分配给1A和3B)

一个扇区只能分配一个团队。

团队需要被完全容纳或完全被排除在外。

如果我想得对，第二个约束使这个问题类似于多个背包问题，但我不确定一个团队是否是一个背包，而扇区是我们装进袋子的元素。因为在这种情况下，元素尺寸需要等于或大于袋容量。
由于这个限制，我很不知道我应该使用什么样的算法来解决这个问题，或者这个问题是否真的可以以这种形式解决。
有没有人知道解决这个问题的尽可能简单的python算法？
编辑:添加代码:
目前我正在使用 ORTools 库来解决这个问题:
多变的:

x = {}
for i in data['sector_number']:
    for j in data['teams']:
        x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

# y[j] = 1 if team j has allocated sector.
y = {}
for j in data['teams']:
    y[j] = solver.IntVar(0, 1, 'y[%i]' % j)

这是我的限制条件:

# Each sector can be allocated to at most one team.
for i in data['sector_number']:
    solver.Add(sum(x[i, j] for j in data['teams']) <= 1)
# The sector seats amount allocated to each team needs to be minimum this team capacity
for j in data['teams']:
    solver.Add(sum(x[(i, j)] * data['sector_capacity'][i] for i in data['sector_number']) >= y[j] * data['team_members'][j])

最后目标:

# Objective
objective = solver.Objective()

solver.Maximize(solver.Sum([y[j] for j in data['teams']]))

所以实际上唯一缺少的约束是考虑到如果将多个扇区分配给一个团队，那么只能在那里分配开始时编号相同的扇区。
这是为此的数据输入:

{'sector_capacity': [80, 20, 10, 50, 20, 110],
 'sector_number': [0, 1, 2, 3, 4, 5],
 'sector_names': ['1A', '1B', '2A', '3A', '3B', '3C']
 'num_sectors': 6,
 'teams': [0, 1, 2, 3, 4, 5, 6, 7],
 'team_names': ['TeamA',
  'TeamB',
  'TeamC',
  'TeamD',
  'TeamE',
  'TeamF',
  'TeamG',
  'TeamH',
  'TeamI'],
 'team_members': [20, 15, 100, 20, 85, 35, 25, 7]}

Answer 1

这是 pyomo 中的另一个 hack .我将扇区剥离为扇区和区域(第一个数字)以帮助澄清限制。

# Team Assignment

import pyomo.environ as pyo

### DATA
sectors = { 
       "1A": 80,
       "1B": 20, 
       "2A": 10, 
       "3A": 50,
       "3B": 20,
       "3C": 110
     }

teams = {
   "TeamA":20, 
   "TeamB":15, 
   "TeamC":100, 
   "TeamD":20,
   "TeamF":85, 
   "TeamG":35,
   "TeamH":25,
   "TeamI":7,
 } 

sector_zones = { s:s[0] for s in sectors} # a pairing of the sector with the zone (first digit)

### SETS

m = pyo.ConcreteModel("Team Assignment")

m.S = pyo.Set(initialize=sectors.keys())
m.T = pyo.Set(initialize=teams.keys())
m.Z = pyo.Set(initialize=set(sector_zones.values()))
m.SZ = pyo.Set(within=m.S*m.Z,initialize=[(s,z) for (s,z) in sector_zones.items()])

### PARAMS

m.sector_cap = pyo.Param(m.S, initialize=sectors)
m.team_size  = pyo.Param(m.T, initialize=teams)

### VARS

# assign X players from team T to sector S in zone Z
m.X = pyo.Var(m.T, m.SZ, domain=pyo.NonNegativeIntegers)
# include team T at sector S
m.team_sector = pyo.Var(m.T, m.S, domain=pyo.Binary)
# include team T in zone Z
m.team_zone   = pyo.Var(m.T, m.Z, domain=pyo.Binary)

### OBJ

m.obj = pyo.Objective(expr=sum(m.X[t,s,z] for t in m.T for s,z in m.SZ), sense=pyo.maximize)

### CONSTRAINTS

# All-or-nothing in a particular zone
def all_or_not(m, t):
    return sum(m.X[t,s,z] for s,z in m.SZ) == sum(m.team_zone[t,z] * m.team_size[t] for z in m.Z)
m.C1 = pyo.Constraint(m.T, rule=all_or_not)

# Don't bust sector limit
def sector_lim(m, t, s, z):
    return m.X[t,s,z]  <= m.team_sector[t,s] * m.sector_cap[s]
m.C2 = pyo.Constraint(m.T, m.SZ, rule=sector_lim)

# 1 team per sector max
def one_per_sector(m, s):
    return sum(m.team_sector[t,s] for t in m.T) <= 1
m.C3 = pyo.Constraint(m.S, rule=one_per_sector)

# link sector assignment to zone
def sector_zone(m, t, z):
    return sum(m.team_sector[t,s] for s in m.S if (s,z) in m.SZ) <= \
           m.team_zone[t, z] * len(m.S)
m.C4 = pyo.Constraint(m.T, m.Z, rule=sector_zone)

# 1 zone assignment per team
def one_zone(m, t):
    return sum(m.team_zone[t,z] for z in m.Z) <= 1
m.C5 = pyo.Constraint(m.T, rule=one_zone)


### Solve
solver = pyo.SolverFactory('cbc')
res = solver.solve(m)
print(res)

#m.X.display()

assigned = 0
for idx in m.X.keys():
   val = m.X[idx].value
   if val:
      print(f'assign {val} from {idx[0]} to {idx[1]}')
      assigned += val

print(f'total assigned: {assigned}')

产量:

assign 20.0 from TeamA to 3B
assign 80.0 from TeamC to 1A
assign 20.0 from TeamC to 1B
assign 85.0 from TeamF to 3C
assign 35.0 from TeamG to 3A
assign 7.0 from TeamI to 2A
total assigned: 247.0