基于Pulp的匹配算法替代贪心算法：实现错误排查求助

问题背景 #

尝试用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},
    {'d': 10, 'group': 'B', 'weight': 1}
])

需求说明 #

将不同id无重复匹配给用户，每个用户的参数对应：

• 第1位：总权重目标值
• 第2位：A组权重目标值
• 第3位：B组权重目标值
• 第4位：匹配的唯一id总数目标值
• 第5位：A组唯一id数目标值
• 第6位：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}

实际错误结果 #

第一次运行结果：

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

第二次改写后仍得到类似重复分配的错误结果。

可能的实现缺陷点 #

• 数据预处理错误：dataset中id为10的条目键写成了'd'而非'id'，会导致该条目无法被正常识别为有效item，后续匹配逻辑必然出错。
• 核心约束缺失：未添加每个item只能分配给一个用户的约束，这是匹配问题的基础规则。错误结果中item2和10被同时分给两个用户，完全违反了无重复匹配的要求。
• 用户参数约束未正确映射：未将用户的目标参数（总权重、组权重、id数量等）转化为Pulp的约束条件。比如用户1要求总权重5、A组权重4、B组权重1、总id数2，需要分别对这些指标的求和值设置等于目标值的约束，否则算法无法生成符合预期的解。
• 变量定义问题：分配变量（如x[u,i]表示用户u分配item i）未正确定义为二进制变量（0或1），或者变量范围设置错误，导致出现重复分配的情况。
• 目标函数不明确：若目标是严格满足用户的参数要求，应将目标函数设为最小化与目标参数的偏差，或直接设置约束使各指标等于目标值；若目标函数定义错误，算法会优先满足其他非预期的目标，导致结果偏离需求。

内容的提问来源于stack exchange，提问作者Olivia