首页 / 技术问答 / Python问答列表 / 问答详情

Python Pulp Matching 算法取代贪婪算法

我试图创建一个匹配算法使用纸浆，但我得到的样本数据的结果是错误的，因为我认为函数是有缺陷的.

样本数据:

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}
])

我想匹配不同的ID给用户(没有重复).对于每个用户，I具有总权重、组A权重、组B权重、唯一ID计数、组A唯一ID计数、组B唯一ID计数.

对于上面的示例，正确答案应该是:

{'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}

我的第一次try :

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

然而，结果是:

{1: {'group_a': [2], 'group_b': [10]}, 2: {'group_a': [2], 'group_b': [10]}}

看起来我的结果可能会互相覆盖，但看起来也是错误的.

我试图重写它，但得到了类似的错误结果:

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

我哪里错了？

推荐答案

当我认为不应该有目标的时候，你设定了一个优化目标和优化意识(和默认的感觉).换句话说，一旦你完成了公式化，print(prob)应该包括

MINIMIZE
None

您不应该有总权重、唯一用户总数等变量:相反，只有一个决策变量种类，这是一个关于ID是否已分配给用户的二进制赋值.

"合计"约束是多余的，您可以在没有合计的情况下处理单个组值.

由于您是在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_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

Python相关问答推荐

opencv Python稳定的图标识别

Chatgpt API不断返回错误：404未能从API获取响应

当多个值具有相同模式时返回空

如何使用LangChain和AzureOpenAI在Python中解决AttribeHelp和BadPressMessage错误？

如何记录脚本输出

为什么sys.exit()不能与subproccess.run()或subprocess.call()一起使用

如何使用它？

avxspan与pandas period_range

连接一个rabrame和另一个1d rabrame不是问题，但当使用[...]'运算符会产生不同的结果

如何保持服务器发送的事件连接活动？

用渐近模计算含符号的矩阵乘法

在两极中过滤

如何使regex代码只适用于空的目标单元格

下三角形掩码与seaborn clustermap bug

python中csv. Dictreader. fieldname的类型是什么？'

以异步方式填充Pandas 数据帧

我对这个简单的异步者的例子有什么错误的理解吗？

如何将一组组合框重置回无 Select tkinter？

ModuleNotFoundError：Python中没有名为google的模块''

SpaCy：Regex模式在基于规则的匹配器中不起作用

实用课程推荐
相关教程推荐
休闲君评测 |  TOOLFK工具网 |  古诗文网 |  良许Linux教程网 |  Python之禅 |  红色石头 |  入党申请书 | 

© 2020 Hi LearnFk 意见反馈 免责声明 关于我们 桂ICP备11002319号-3 友链&广告位+QQ: 1963612630