Pulp优化模型报错：非常量表达式无法相乘求解求助

错误原因 #

Pulp是用于求解**线性规划（LP）**的库，不支持直接处理变量相乘的非线性表达式。你的目标函数中x[i,k] * x[j,k]是两个二进制决策变量的乘积，属于非线性项，因此触发Non-constant expressions cannot be multiplied错误。

解决方案 #

通过引入新的二进制变量将非线性项线性化：

• 定义新二进制变量z[i,j,k]，表示用户i和用户j同时被分配到组k中（即z[i,j,k] = x[i,k] * x[j,k]）
• 添加线性约束来等价这个乘积关系（利用二进制变量的特性）
• 用z[i,j,k]替换目标函数中的乘积项

修改后的完整代码 #

from pulp import LpProblem, LpVariable, lpSum, LpMaximize

# 初始化问题
prob = LpProblem("Group_Optimization", LpMaximize)

# Person i in group j   
x = {(i, j): LpVariable(cat="Binary", name=f"x_{i}_{j}") for i in result_sum.index for j in result_sum.index}

# group j exists
y = {j: LpVariable(cat="Binary", name=f"y_{j}") for j in result_sum.index}

# 新变量：z[i,j,k] = 1 当且仅当i和j都在组k中（i < j避免重复计算）
z = {}
for i in result_sum.index:
    for j in result_sum.index:
        if i < j:  # 只处理i<j的情况，减少变量数量和重复计算
            for k in result_sum.index:
                z[(i,j,k)] = LpVariable(cat="Binary", name=f"z_{i}_{j}_{k}")
                # 添加约束：z[i,j,k] ≤ x[i,k]
                prob += z[(i,j,k)] <= x[i,k]
                # 添加约束：z[i,j,k] ≤ x[j,k]
                prob += z[(i,j,k)] <= x[j,k]
                # 添加约束：z[i,j,k] ≥ x[i,k] + x[j,k] - 1
                prob += z[(i,j,k)] >= x[i,k] + x[j,k] - 1

# 目标函数：最大化组内人员的总匹配分数
# 利用i<j的z变量，避免重复计算i-j和j-i的分数
prob += lpSum(punctuation.loc[i,j] * z[(i,j,k)] for i in result_sum.index for j in result_sum.index for k in result_sum.index if i < j)

# 约束1：每个人必须属于且仅属于一个组
for i in result_sum.index:
    prob += lpSum(x[i, j] for j in result_sum.index) == 1

# 约束2：每个组的成员数在2-3之间（仅当组存在时生效）
for j in result_sum.index:
    prob += lpSum(x[i, j] for i in result_sum.index) >= 2 * y[j]
    prob += lpSum(x[i, j] for i in result_sum.index) <= 3 * y[j]

# 求解问题
prob.solve()

# 可选：输出结果
for v in prob.variables():
    if v.varValue == 1:
        print(v.name, "=", v.varValue)

关键说明 #

1. 变量去重：通过i < j定义z变量，避免重复计算(i,j,k)和(j,i,k)，减少变量总数，提升求解效率。
2. 线性化约束：三个约束共同保证z[i,j,k]等价于x[i,k] * x[j,k]：
   • 若x[i,k]或x[j,k]为0，z必须为0
   • 若x[i,k]和x[j,k]都为1，z必须为1
3. 目标函数简化：直接对z[i,j,k]乘以对应分数求和，替代原来的非线性乘积项，符合线性规划要求。

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