英文:
Pulp Matching algorithm to replace greedy algo
问题
你的代码存在一些问题。我会为你指出这些问题：
-
在你的第一个尝试中，你创建了一个LP问题，但没有明确定义你的目标函数。你应该定义一个目标函数来最大化或最小化某些值。在这种情况下，你似乎想要最大化某些值，但你的目标函数是
prob += lpSum(variables[i] for i in range(len(dataset)))，这只是将所有变量的总和添加到目标函数中。你需要考虑如何构建目标函数来实现你的匹配目标。 -
你的约束也有问题。例如，你的 "Total weight constraint" 是
prob += lpSum(variables[i] * dataset.loc[i, 'weight'] for i in range(len(dataset))) <= user_vars[user_id]['total_weight']，但这个约束不会正确地将权重与用户匹配。你应该将变量与数据集中的用户相关联，以便在匹配时考虑权重。 -
在第二个尝试中，你的目标函数仍然不明确，而且在约束中仍然存在问题。
为了正确解决这个问题，你需要重新考虑如何定义目标函数和约束，以便实现你的匹配目标。你可能需要重新设计你的模型，以确保它正确地表示了你的问题。这可能需要一些重新思考和重写代码。如果你需要更多的帮助，可以提供更多详细信息，我会尽力提供更多指导。
英文:
I am trying to create a matching algorithm using pulp but the results for the sample data I'm getting are wrong as I think the function is flawed.
Sample data:
users = {
1: (5.0, 4.0, 1.0, 2, 1, 1),
2: (8.0, 6.0, 2.0, 3, 2, 1)
}
dataset = pd.DataFrame([
{'id': 1, 'group': 'A', 'weight': 1},
{'id': 2, 'group': 'A', 'weight': 2},
{'id': 3, 'group': 'A', 'weight': 3},
{'id': 4, 'group': 'A', 'weight': 3},
{'id': 5, 'group': 'A', 'weight': 4},
{'id': 6, 'group': 'A', 'weight': 6},
{'id': 7, 'group': 'A', 'weight': 7},
{'id': 8, 'group': 'A', 'weight': 8},
{'id': 9, 'group': 'B', 'weight': 2},
{'d': 10, 'group': 'B', 'weight': 1}
])
I would like to match different ids to users (without repetition). For each user I have a total weight, group A weight, group B weight, unique id count, group A unique id count, group B unique id count.
For the sample above the correct answer should be:
{'id': 5, 'group': 'A', 'weight': 4, 'user_id': 1}
{'id': 10, 'group': 'B', 'weight': 1, 'user_id': 1}
{'id': 3, 'group': 'A', 'weight': 3, 'user_id': 2}
{'id': 4, 'group': 'A', 'weight': 3, 'user_id': 2}
{'id': 9, 'group': 'B', 'weight': 2, 'user_id': 2}
My first attempt:
from pulp import *
import pandas as pd
from itertools import product
def match_weights(users, dataset):
matched_rows = []
variables = LpVariable.dicts("Item", range(len(dataset)), lowBound=0, cat='Binary')
user_vars = {}
for user_id, (total_weight, group_a_weight, group_b_weight, total_unique_users, group_a_unique_users, group_b_unique_users) in users.items():
user_vars[user_id] = {}
user_vars[user_id]['total_weight'] = LpVariable("TotalWeight_{}".format(user_id), lowBound=0, upBound=total_weight)
user_vars[user_id]['group_a_weight'] = LpVariable("GroupAWeight_{}".format(user_id), lowBound=0, upBound=group_a_weight)
user_vars[user_id]['group_b_weight'] = LpVariable("GroupBWeight_{}".format(user_id), lowBound=0, upBound=group_b_weight)
user_vars[user_id]['total_unique_users'] = LpVariable("TotalUniqueUsers_{}".format(user_id), lowBound=0, upBound=total_unique_users, cat='Integer')
user_vars[user_id]['group_a_unique_users'] = LpVariable("GroupAUniqueUsers_{}".format(user_id), lowBound=0, upBound=group_a_unique_users, cat='Integer')
user_vars[user_id]['group_b_unique_users'] = LpVariable("GroupBUniqueUsers_{}".format(user_id), lowBound=0, upBound=group_b_unique_users, cat='Integer')
prob = LpProblem("MatchingProblem", LpMaximize)
prob += lpSum(variables[i] for i in range(len(dataset)))
for user_id, (total_weight, group_a_weight, group_b_weight, total_unique_users, group_a_unique_users, group_b_unique_users) in users.items():
group_a_items = dataset[dataset['group'] == 'A'].index.tolist()
group_b_items = dataset[dataset['group'] == 'B'].index.tolist()
# Total weight constraint
prob += lpSum(variables[i] * dataset.loc[i, 'weight'] for i in range(len(dataset))) <= user_vars[user_id]['total_weight']
# Group A weight constraint
prob += lpSum(variables[i] * dataset.loc[i, 'weight'] for i in group_a_items) <= user_vars[user_id]['group_a_weight']
# Group B weight constraint
prob += lpSum(variables[i] * dataset.loc[i, 'weight'] for i in group_b_items) <= user_vars[user_id]['group_b_weight']
# Total unique user constraint
unique_users = set()
for i in range(len(dataset)):
if variables[i].value() == 1:
unique_users.add(dataset.loc[i, 'id'])
prob += lpSum(1 for u in unique_users) <= user_vars[user_id]['total_unique_users']
# Group A unique user constraint
unique_users_a = set()
for i in group_a_items:
if variables[i].value() == 1:
unique_users_a.add(dataset.loc[i, 'id'])
prob += lpSum(1 for u in unique_users_a) <= user_vars[user_id]['group_a_unique_users']
# Group B unique user constraint
unique_users_b = set()
for i in group_b_items:
if variables[i].value() == 1:
unique_users_b.add(dataset.loc[i, 'id'])
prob += lpSum(1 for u in unique_users_b) <= user_vars[user_id]['group_b_unique_users']
prob.solve()
for user_id, (total_weight, group_a_weight, group_b_weight, total_unique_users, group_a_unique_users, group_b_unique_users) in users.items():
matched_user_rows = []
for i in range(len(dataset)):
if variables[i].value() == 1:
matched_row = dataset.loc[i].copy()
matched_row['user_id'] = user_id
matched_user_rows.append(matched_row)
matched_rows.extend(matched_user_rows)
return matched_rows
However the results are:
{1: {'group_a': [2], 'group_b': [10]}, 2: {'group_a': [2], 'group_b': [10]}}
Looks like my results might overwrite each other but also look wrong.
I tried to rewrite it and got similar incorrect results:
def match_weights(users, dataset):
model = LpProblem("MatchingProblem", LpMaximize)
variables = LpVariable.dicts("Item", dataset.index, lowBound=0, cat='Binary')
model += lpSum(variables[i] for i in dataset.index)
# Add constraints for each user
for user_id, (total_weight, group_a_weight, group_b_weight, _, _, _) in users.items():
# Filter dataset based on user group
group_a_indices = dataset[dataset['group'] == 'A'].index
group_b_indices = dataset[dataset['group'] == 'B'].index
# Total weight constraint
model += lpSum(variables[i] * dataset.loc[i, 'weight'] for i in dataset.index) <= total_weight
# Group A weight constraint
model += lpSum(variables[i] * dataset.loc[i, 'weight'] for i in group_a_indices) <= group_a_weight
# Group B weight constraint
model += lpSum(variables[i] * dataset.loc[i, 'weight'] for i in group_b_indices) <= group_b_weight
unique_user_set = set(dataset['respondent_id'])
for user_id, (total_weight, _, _, total_unique_users, group_a_unique_users, group_b_unique_users) in users.items():
group_a_indices = dataset[dataset['group'] == 'A'].index
group_b_indices = dataset[dataset['group'] == 'B'].index
# Total unique users constraint
model += lpSum(variables[i] for i in dataset.index if dataset.loc[i, 'respondent_id'] in unique_user_set) \
<= total_unique_users
# Group A unique users constraint
model += lpSum(variables[i] for i in group_a_indices if dataset.loc[i, 'respondent_id'] in unique_user_set) \
<= group_a_unique_users
# Group B unique users constraint
model += lpSum(variables[i] for i in group_b_indices if dataset.loc[i, 'respondent_id'] in unique_user_set) \
<= group_b_unique_users
model.solve()
results = {}
for user_id, (_, _, _, _, _, _) in users.items():
group_a_indices = dataset[dataset['group'] == 'A'].index
group_b_indices = dataset[dataset['group'] == 'B'].index
matched_a = [dataset.loc[i, 'respondent_id'] for i in group_a_indices if variables[i].value() == 1]
matched_b = [dataset.loc[i, 'respondent_id'] for i in group_b_indices if variables[i].value() == 1]
results[user_id] = {'group_a': matched_a, 'group_b': matched_b}
return results
Where am I going wrong?
答案1
得分: 2
您已经设置了一个优化目标和优化条件，但我认为不应该设置目标（将条件保留为默认）。换句话说，一旦您完成了公式化，print(prob) 应该包括以下内容：
MINIMIZE
None
您不应该有关于总权重、总唯一用户等的变量：而应该只有一种决策变量类型，即判断是否将ID分配给用户的二进制分配。
"total" 约束是多余的，您可以处理单个组的值而不是总和。
由于您正在使用 Pandas，只要数据的形状正确，您不需要使用 lpSum；您可以直接操作框架和系列（.dot()、.sum()）。
dataset 是一个数据框（很好！）需要将 id 转换为索引。users 应该从字典转换为数据框。
import pandas as pd
import pulp
requirements = pd.DataFrame(
data={
1: (5.0, 4.0, 1.0, 2, 1, 1),
2: (8.0, 6.0, 2.0, 3, 2, 1),
},
# row index, soon to turn into column names via .T
index=pd.MultiIndex.from_product(
iterables=(('weight', 'count'), ('total', 'A', 'B')),
names=('requirement', 'group'),
),
).drop(labels='total', level='group').T # redundant
requirements.index.name = 'user'
user_values = requirements.index.to_series()
requirements = requirements.stack(level='group')
print(requirements, end='\n\n')
dataset = pd.DataFrame([
{'id': 1, 'group': 'A', 'weight': 1},
{'id': 2, 'group': 'A', 'weight': 2},
{'id': 3, 'group': 'A', 'weight': 3},
{'id': 4, 'group': 'A', 'weight': 3},
{'id': 5, 'group': 'A', 'weight': 4},
{'id': 6, 'group': 'A', 'weight': 6},
{'id': 7, 'group': 'A', 'weight': 7},
{'id': 8, 'group': 'A', 'weight': 8},
{'id': 9, 'group': 'B', 'weight': 2},
{'id': 10, 'group': 'B', 'weight': 1},
]).set_index('id')
print(dataset, end='\n\n')
combos = pd.merge(left=user_values, right=dataset.index.to_series(), how='cross')
asn_name = 'asn_u' + combos.user.astype(str) + '_i' + combos.id.astype(str)
combos['asn'] = asn_name.apply(pulp.LpVariable, cat=pulp.LpBinary)
combos = combos.set_index(['user', 'id']).asn.unstack(level='user')
print(combos, end='\n\n')
prob = pulp.LpProblem(name='user_assignment')
# Every ID can be assigned to at most one user
for user, total in combos.sum(axis=1).items():
prob.addConstraint(name=f'excl_u{user}', constraint=total <= 1)
for group, dataset_weights in dataset.groupby('group'):
group_assigns = combos.loc[dataset_weights.index]
for user, user_assigns in group_assigns.items():
requirement = requirements.loc[(user, group), :]
prob.addConstraint(
name=f'count_u{user}_g{group}',
constraint=user_assigns.sum() == requirement['count'],
)
prob.addConstraint(
name=f'weight_u{user}_g{group}',
constraint=user_assigns.dot(dataset_weights.weight) == requirement['weight'],
)
print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
combos = combos.applymap(pulp.LpVariable.value).astype(int)
combos = combos[combos.any(axis=1)]
print(combos)
requirement count weight
user group
1 A 1.0 4.0
B 1.0 1.0
2 A 2.0 6.0
B 1.0 2.0
group weight
id
1 A 1
2 A 2
3 A 3
4 A 3
5 A 4
6 A 6
7 A 7
8 A 8
9 B 2
10 B 1
user 1 2
id
1 asn_u1_i1 asn_u2_i1
2 asn_u1_i2 asn_u2_i2
3 asn_u1_i3 asn_u2_i3
4 asn_u1_i4 asn_u2_i4
5 asn_u1_i5 asn_u2_i5
6 asn_u1_i6 asn_u2_i6
7 asn_u1_i7 asn_u2_i7
8 asn_u1_i8 asn_u2_i8
9 asn_u1_i9 asn_u2_i9
10 asn_u1_i10 asn_u2_i10
user_assignment:
MINIMIZE
None
SUBJECT TO
excl_u1: asn_u1_i1 + asn_u2_i1 <= 1
excl_u2: asn_u1_i2 + asn_u2_i2 <= 1
...
count_u1_gA: asn_u1_i1 + asn_u1_i2 + asn_u1_i3 + asn_u1_i4 + asn_u1_i5
+ asn_u1_i6 + asn_u1_i7 + asn_u1_i8 = 1
weight_u1_gA: asn_u1_i1 + 2 asn_u1_i2 + 3 asn_u1_i3 + 3 asn_u1_i4
+ 4 asn_u1_i5 + 6 asn_u1_i6 + 7 asn_u1_i7 + 8 asn_u1_i8 = 4
...
VARIABLES
0 <= asn_u1_i1 <= 1 Integer
0 <= asn_u1_i10 <= 1 Integer
0 <= asn_u1_i2 <= 1 Integer
0 <= asn_u1_i3 <= 1 Integer
0 <= asn_u1_i4 <= 1 Integer
0 <= asn_u1_i5 <= 1 Integer
0 <= asn_u1_i6 <= 1 Integer
0 <= asn_u1_i7 <= 1 Integer
0 <= asn_u1_i8 <= 1 Integer
0 <= asn
<details>
<summary>英文:</summary>
You've set an optimisation objective and optimisation sense when I believe there should be no objective (and the sense left as default). In other words, once you're done formulating, `print(prob)` should include
```none
MINIMIZE
None
You should not have variables for total weight, total unique users etc: instead, only have one decision variable kind, which is a binary assignment of whether an ID has been assigned to a user.
The "total" constraint is redundant and you can deal with the individual group values without the total.
Since you're in Pandas, so long as your data are shaped correctly, you do not need to use lpSum; you can operate on the frames and series directly (.dot(), .sum()).
dataset is a frame (good!) that needs id to move to an index. users should be converted from a dictionary to a frame.
import pandas as pd
import pulp
requirements = pd.DataFrame(
data={
1: (5.0, 4.0, 1.0, 2, 1, 1),
2: (8.0, 6.0, 2.0, 3, 2, 1),
},
# row index, soon to turn into column names via .T
index=pd.MultiIndex.from_product(
iterables=(('weight', 'count'), ('total', 'A', 'B')),
names=('requirement', 'group'),
),
).drop(labels='total', level='group').T # redundant
requirements.index.name = 'user'
user_values = requirements.index.to_series()
requirements = requirements.stack(level='group')
print(requirements, end='\n\n')
dataset = pd.DataFrame([
{'id': 1, 'group': 'A', 'weight': 1},
{'id': 2, 'group': 'A', 'weight': 2},
{'id': 3, 'group': 'A', 'weight': 3},
{'id': 4, 'group': 'A', 'weight': 3},
{'id': 5, 'group': 'A', 'weight': 4},
{'id': 6, 'group': 'A', 'weight': 6},
{'id': 7, 'group': 'A', 'weight': 7},
{'id': 8, 'group': 'A', 'weight': 8},
{'id': 9, 'group': 'B', 'weight': 2},
{'id': 10, 'group': 'B', 'weight': 1},
]).set_index('id')
print(dataset, end='\n\n')
combos = pd.merge(left=user_values, right=dataset.index.to_series(), how='cross')
asn_name = 'asn_u' + combos.user.astype(str) + '_i' + combos.id.astype(str)
combos['asn'] = asn_name.apply(pulp.LpVariable, cat=pulp.LpBinary)
combos = combos.set_index(['user', 'id']).asn.unstack(level='user')
print(combos, end='\n\n')
prob = pulp.LpProblem(name='user_assignment')
# Every ID can be assigned to at most one user
for user, total in combos.sum(axis=1).items():
prob.addConstraint(name=f'excl_u{user}', constraint=total <= 1)
for group, dataset_weights in dataset.groupby('group'):
group_assigns = combos.loc[dataset_weights.index]
for user, user_assigns in group_assigns.items():
requirement = requirements.loc[(user, group), :]
prob.addConstraint(
name=f'count_u{user}_g{group}',
constraint=user_assigns.sum() == requirement['count'],
)
prob.addConstraint(
name=f'weight_u{user}_g{group}',
constraint=user_assigns.dot(dataset_weights.weight) == requirement['weight'],
)
print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
combos = combos.applymap(pulp.LpVariable.value).astype(int)
combos = combos[combos.any(axis=1)]
print(combos)
requirement count weight
user group
1 A 1.0 4.0
B 1.0 1.0
2 A 2.0 6.0
B 1.0 2.0
group weight
id
1 A 1
2 A 2
3 A 3
4 A 3
5 A 4
6 A 6
7 A 7
8 A 8
9 B 2
10 B 1
user 1 2
id
1 asn_u1_i1 asn_u2_i1
2 asn_u1_i2 asn_u2_i2
3 asn_u1_i3 asn_u2_i3
4 asn_u1_i4 asn_u2_i4
5 asn_u1_i5 asn_u2_i5
6 asn_u1_i6 asn_u2_i6
7 asn_u1_i7 asn_u2_i7
8 asn_u1_i8 asn_u2_i8
9 asn_u1_i9 asn_u2_i9
10 asn_u1_i10 asn_u2_i10
user_assignment:
MINIMIZE
None
SUBJECT TO
excl_u1: asn_u1_i1 + asn_u2_i1 <= 1
excl_u2: asn_u1_i2 + asn_u2_i2 <= 1
...
count_u1_gA: asn_u1_i1 + asn_u1_i2 + asn_u1_i3 + asn_u1_i4 + asn_u1_i5
+ asn_u1_i6 + asn_u1_i7 + asn_u1_i8 = 1
weight_u1_gA: asn_u1_i1 + 2 asn_u1_i2 + 3 asn_u1_i3 + 3 asn_u1_i4
+ 4 asn_u1_i5 + 6 asn_u1_i6 + 7 asn_u1_i7 + 8 asn_u1_i8 = 4
...
VARIABLES
0 <= asn_u1_i1 <= 1 Integer
0 <= asn_u1_i10 <= 1 Integer
0 <= asn_u1_i2 <= 1 Integer
0 <= asn_u1_i3 <= 1 Integer
0 <= asn_u1_i4 <= 1 Integer
0 <= asn_u1_i5 <= 1 Integer
0 <= asn_u1_i6 <= 1 Integer
0 <= asn_u1_i7 <= 1 Integer
0 <= asn_u1_i8 <= 1 Integer
0 <= asn_u1_i9 <= 1 Integer
0 <= asn_u2_i1 <= 1 Integer
0 <= asn_u2_i10 <= 1 Integer
0 <= asn_u2_i2 <= 1 Integer
0 <= asn_u2_i3 <= 1 Integer
0 <= asn_u2_i4 <= 1 Integer
0 <= asn_u2_i5 <= 1 Integer
0 <= asn_u2_i6 <= 1 Integer
0 <= asn_u2_i7 <= 1 Integer
0 <= asn_u2_i8 <= 1 Integer
0 <= asn_u2_i9 <= 1 Integer
...
Result - Optimal solution found
user 1 2
id
3 0 1
4 0 1
5 1 0
9 0 1
10 1 0
答案2
得分: 1
以下是翻译好的部分：
你确实在正确的方向上... 有点。
我在第一次尝试中无法真正理解逻辑。不清楚为什么要创建这么多变量。在核心上，这是一个分配问题，我们正在为user分配id。所以我们真正需要的唯一变量应该是类似于：
assign[item, user] # 一个指示分配的二进制变量
然后，如果我们需要分配的总权重，我们可以按标准方式总结分配乘以权重。不需要更多的变量。
第二次尝试在更好的方向上，但是变量设置错误。您真的想要按照我下面展示的方式对其进行双索引，然后一切就会顺利进行。当您习惯在数学编程环境中思考这个问题时，事情会变得更容易。您需要正确的变量和一些问题中指示所有id集合以及组的子集。如果有许多组，我可能会重新组织数据以能够按组进行索引，但是对于2个组，这是可以的。
关于您的循环，您可以将我下面的内容组合成一个循环"对于每个用户"并在其中包含所有约束，但我认为如果您对每个约束进行一个循环更容易理解。最终这是一种偏好。
我认为您可能可以完成我下面已经开始的内容，以获取其余的约束并解决问题。如果卡住了，请回复评论。
代码：
# 组分配
import pandas as pd
import pulp
### 数据
users = {
1: (5.0, 4.0, 1.0, 2, 1, 1),
2: (8.0, 6.0, 2.0, 3, 2, 1)
}
dataset = pd.DataFrame([
{'id': 1, 'group': 'A', 'weight': 1},
{'id': 2, 'group': 'A', 'weight': 2},
{'id': 3, 'group': 'A', 'weight': 3},
{'id': 4, 'group': 'A', 'weight': 3},
{'id': 5, 'group': 'A', 'weight': 4},
{'id': 6, 'group': 'A', 'weight': 6},
{'id': 7, 'group': 'A', 'weight': 7},
{'id': 8, 'group': 'A', 'weight': 8},
{'id': 9, 'group': 'B', 'weight': 2},
{'id': 10, 'group': 'B', 'weight': 1} # <-- 请注意这一行中有一个拼写错误
]).set_index('id')
### 一些整理和方便的工作...
for user in users:
users[user] = dict(zip(('wt_limit', 'a_wt_limit', 'b_wt_limit', 'item_limit', 'a_item_limit', 'b_item_limit'), users[user]))
ids = dataset.index
print(ids)
# 子集
grp_a_idx = dataset[dataset['group'] == 'A'].index
grp_b_idx = dataset[dataset['group'] == 'B'].index
### 问题设置
prob = pulp.LpProblem('id_assigner', pulp.LpMaximize)
### 集合
id_user = {(i, u) for i in dataset.index for u in users}
### 变量
assign = pulp.LpVariable.dicts('assign', indices=id_user, cat=pulp.LpBinary)
### 目标：最大化分配
prob += pulp.lpSum(assign)
### 约束
# 1. 每个id只能分配一次（或者不分配）
for i in ids:
prob += sum(assign[i, user] for user in users) <= 1
# 2. 不要超出每个用户的总权重
for user in users:
prob += sum(assign[i, user]*dataset.loc[i, 'weight'] for i in ids ) <= users[user]['wt_limit']
# 3. 不要超出组A的权重，对于每个用户
for user in users:
prob += sum(assign[i, user]*dataset.loc[i, 'weight'] for i in grp_a_idx) <= users[user]['a_wt_limit']
# ..... 与其他约束类似。根据需要使用子集进行组特定的操作，例如上面的＃3。
# 检查一下：
print(prob)
### 解决
### 结果
希望这能帮助您理解代码的内容。如果有任何问题，请随时提问。
英文:
You are on the right track... kinda.
I couldn't really follow the logic in the first attempt. It isn't clear why you were creating so many variables. At the core, this is an assignment problem, where we are assigning ids to users. So the only variable we should really need is something like:
assign[item, user] # a binary variable indicating assignment
Then, if we need the total weight assigned, we can just sum up the assignments times the weights in standard fashion. No need for more variables.
The second attempt is on a better track, but the variable is set up wrong, You really want to double-index it as I show below, then things fall into place. The more you get used to thinking about this in a math programming context, the easier things get. You need the correct variable and some subsets in your problem indicating the set of all ids and then the groups. If you had many groups, I'd probably reorganize the data to be able to index by group as well, but for 2 groups, this is fine.
Regarding the loops you have, you can combine what I did below into a loop "for each user" and include all the constraints there, but I think it is easier to digest if you do a loop per constraint. In the end it is a preference
I think you can probably finish what I've started below to scoop up the rest of the constraints and solve. Comment back if you are stuck.
Code:
# group assignment
import pandas as pd
import pulp
### DATA
users = {
1: (5.0, 4.0, 1.0, 2, 1, 1),
2: (8.0, 6.0, 2.0, 3, 2, 1)
}
dataset = pd.DataFrame([
{'id': 1, 'group': 'A', 'weight': 1},
{'id': 2, 'group': 'A', 'weight': 2},
{'id': 3, 'group': 'A', 'weight': 3},
{'id': 4, 'group': 'A', 'weight': 3},
{'id': 5, 'group': 'A', 'weight': 4},
{'id': 6, 'group': 'A', 'weight': 6},
{'id': 7, 'group': 'A', 'weight': 7},
{'id': 8, 'group': 'A', 'weight': 8},
{'id': 9, 'group': 'B', 'weight': 2},
{'id': 10, 'group': 'B', 'weight': 1} # <-- note you had a typo in this row
]).set_index('id')
### a little tidying & conveniences...
for user in users:
users[user] = dict(zip( ('wt_limit', 'a_wt_limit', 'b_wt_limit', 'item_limit', 'a_item_limit', 'b_item_limit'), users[user]))
ids = dataset.index
print(ids)
# subsets
grp_a_idx = dataset[dataset['group'] == 'A'].index
grp_b_idx = dataset[dataset['group'] == 'B'].index
### PROBLEM SETUP
prob = pulp.LpProblem('id_assigner', pulp.LpMaximize)
### SETS
id_user = { (i, u) for i in dataset.index for u in users }
### VARS
assign = pulp.LpVariable.dicts('assign', indices=id_user, cat=pulp.LpBinary)
### OBJ: Maximize assignments
prob += pulp.lpSum(assign)
### CONSTRAINTS
# 1. Can only assign each id only once (or not at all)
for i in ids:
prob += sum(assign[i, user] for user in users) <= 1
# 2. Don't overassign total weight, for each user
for user in users:
prob += sum(assign[i, user]*dataset.loc[i, 'weight'] for i in ids ) <= users[user]['wt_limit']
# 3. Don't overassign weights for grp A, for each user
for user in users:
prob += sum(assign[i, user]*dataset.loc[i, 'weight'] for i in grp_a_idx) <= users[user]['a_wt_limit']
# ..... similarly for other constraints. Use the subsets as needed for group-specific things, like #3 above.
# check it:
print(prob)
### SOLVE
### RESULTS
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论