使用PuLP优化参与者三人匹配：如何设置约束获得合法唯一解？

• 决策变量定义允许i、j、k重复，没有限制组内三人身份唯一，模型会优先选择成员重复的低方差三元组（重复成员的特征方差远低于三人不同的组，自然会输出不符合业务要求的解）
• 原有约束逻辑完全不匹配三人组分配需求：既没有限制每个参与者仅被分配一次，也没有保证所有参与者都被分配，原约束里的配对上限、双向配对规则和三人组场景不兼容。

1. 优化决策变量定义 #

直接生成严格满足i<j<k的三元组变量，天然避免同组成员重复、同组重复排列的问题，同时大幅减少变量数量：

participants = range(len(data))
# 仅生成i<j<k的三元组，保证组内三人唯一，无重复排列冗余
y = LpVariable.dicts("trio", [(i,j,k) for i in participants for j in participants for k in participants if i < j < k], cat='Binary')

2. 替换原有全部约束，设置两个核心规则 #

# 约束1：每个参与者恰好属于1个三元组，保证所有参与者被分配且不重复
for i in participants:
    prob += lpSum(y[(i,j,k)] for j in participants for k in participants if i<j<k) + \
            lpSum(y[(j,i,k)] for j in participants for k in participants if j<i<k) + \
            lpSum(y[(j,k,i)] for j in participants for k in participants if j<k<i) == 1

# 约束2：总三元组数量等于总人数/3，本次6个参与者对应2个组
prob += lpSum(y[triple] for triple in y.keys()) == len(participants)//3

3. 同步修改目标函数和结果输出逻辑 #

适配新的变量定义，避免无效遍历：

# 新目标函数：三元组特征方差是提前计算的常量，目标函数仍为线性可解
prob += lpSum([np.mean([np.std([data['gender'][i], data['gender'][j], data['gender'][k]]),
                        np.std([data['age'][i], data['age'][j], data['age'][k]]),
                        np.std([data['experience'][i], data['experience'][j], data['experience'][k]])]) * y[(i,j,k)] for (i,j,k) in y.keys()])

# 输出结果
prob.solve()
print("Finished matching!\n")
for (i,j,k) in y.keys():
    if y[(i,j,k)].varValue == 1:
        print('{}、{}、{} 匹配，平均标准差为 {}'.format(data['name'][i], data['name'][j], data['name'][k],
                                                  np.mean([np.std([data['gender'][i], data['gender'][j], data['gender'][k]]),
                                                           np.std([data['age'][i], data['age'][j], data['age'][k]]),
                                                           np.std([data['experience'][i], data['experience'][j], data['experience'][k]])])))

运行后会输出2组无重复成员、覆盖所有参与者的匹配结果。

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