You need to enable JavaScript to run this app. CVXPY搭建合作伙伴偏好优化模型触发DCPError:目标函数不合规求助
优惠活动
大模型
产品
解决方案
定价
更多

CVXPY搭建合作伙伴偏好优化模型触发DCPError:目标函数不合规求助

问题核心定位

直接把报错的几个核心原因说清楚,不用绕弯:

  • DCP报错的直接触发点:CVXPY的DCP规则卡死了曲率要求——最大化目标必须是凹函数,最小化目标必须是凸函数。你用的y.T @ part_pref_np @ y这个二次项,因为偏好矩阵既不是半正定也不是半负定,对应的二次函数是既凸又凹不沾边的类型,不管前面加不加负号都不符合DCP要求,直接抛错。
  • 目标逻辑的小偏差:你写的cp.sum(y.T @ part_pref_np @ y)会把4个团队之间跨团队的员工对偏好也算进总分,但合作伙伴偏好本来就是针对同团队成员的,跨团队的部分和业务目标完全没关系,正确的统计范围应该是同团队内部的两两偏好,也就是只取二次型矩阵的对角线元素求和(等价于cp.trace(y.T @ part_pref_np @ y))。
  • 代码笔误:最后一条约束里用了没定义的变量x,应该是之前写模型的时候留的草稿,对应你实际定义的y变量,不修正的话就算DCP过了也会报变量未定义的错。
首选修正方案(完全等价、无精度损失)

因为你的y本来就是0-1二元整数变量,直接把二次项拆成线性的辅助变量即可,完全不需要调整偏好矩阵的性质,这也是小规模团队分配问题的标准处理方式:

  • 原理:对于0-1变量y[i,j](员工i分到团队j)和y[l,j](员工l分到团队j),两者的乘积y[i,j] * y[l,j]等价于一个新的二元变量z[i,l,j],仅当两个员工同时在团队j时z取1,其他情况取0。通过简单的线性约束就可以绑定z和y的关系,把原来的二次目标完全转化为线性目标,天然符合DCP规则。
  • 规模说明:20个员工的全量两两对只有190个,对应4个团队的辅助变量一共760个二元变量,对求解器来说几乎没有额外计算压力,完全不用担心里程碑爆炸。

具体的修正代码如下:

import numpy as np
import pandas as pd
import cvxpy as cp
from itertools import combinations

# 读取偏好矩阵(原逻辑保留)
part_pref = pd.read_excel('Preferred Partners Updated.xlsx')
part_pref_np = np.array(part_pref)[:,1:21] # 20x20 对称偏好矩阵
n_emp, n_team = 20, 4

# 原分配变量
y = cp.Variable((n_emp, n_team), integer = True)

# 1. 生成所有员工对(i<l 避免重复计数)
pairs = list(combinations(range(n_emp), 2))
n_pairs = len(pairs) # 共190个员工对
# 2. 定义辅助二元变量z:维度(员工对数量, 团队数量)
z = cp.Variable((n_pairs, n_team), integer=True)

# 3. 绑定z和y的等价关系
z_constraints = []
for pair_idx, (i, l) in enumerate(pairs):
    for team_idx in range(n_team):
        # 仅当y[i,team]和y[l,team]都为1时,z[pair_idx, team]才为1
        z_constraints.append(z[pair_idx, team_idx] <= y[i, team_idx])
        z_constraints.append(z[pair_idx, team_idx] <= y[l, team_idx])
        z_constraints.append(z[pair_idx, team_idx] >= y[i, team_idx] + y[l, team_idx] -1)
        z_constraints.append(z[pair_idx, team_idx] >= 0) # 隐含约束,增强数值稳定性

# 4. 构造完全线性的目标函数:
# 原二次项的等价线性展开:同团队内i<l的员工对偏好*2(因为矩阵对称,i,l和l,i是重复计数的)
# 提前把偏好矩阵对角线置0,去掉无意义的自匹配得分
np.fill_diagonal(part_pref_np, 0)
pair_preference_sum = 0
for pair_idx, (i, l) in enumerate(pairs):
    for team_idx in range(n_team):
        pair_preference_sum += part_pref_np[i, l] * z[pair_idx, team_idx] * 2 # 对称矩阵补全i,l双向计数

# 保持你原来的目标方向(最大化负的偏好和,按你原来的业务定义保留)
objective = cp.Maximize(- pair_preference_sum)

# 原有约束部分,修正之前的笔误:把x换成y
constraints = [y >= 0,
               y <= 1,
               cp.sum(y, axis = 1) == 1, # 每个员工仅分到一个团队
               cp.sum(y, axis = 0) >= b,
               cp.sum(y, axis = 0) <= c,
               (skill_np - d).T @ y >= e,
               cp.multiply((skill_np[:,2] -4), y[:,0]) >= 0,  
               cp.multiply((skill_np[:,0] -4), y[:,3]) >= 0,
               f @ y[:,0] >=1 # 原来的x修正为y
               ] + z_constraints # 把z的约束加进去

problem = cp.Problem(objective, constraints)
problem.solve()

方案优势:

  • 没有改动原始偏好矩阵的任何数值,完全保留收集的合作伙伴偏好信息
  • 目标函数和约束全是线性表达式,100%符合DCP规则,求解器无兼容问题
  • 对于20人规模的问题,求解速度和原来的二次形式几乎没有差异
次选方案(近似、不推荐)

如果不想引入辅助变量,可以通过特征值裁剪把偏好矩阵修正为半正定矩阵,让二次型满足凸性要求,但这个方法是有损近似:

  1. 对原始偏好矩阵做特征值分解,把所有负的特征值替换为0,得到半正定的近似矩阵
  2. 用这个近似矩阵代替原来的part_pref_np代入目标函数
  3. 注意:这个方法会丢失原矩阵中负偏好对应的信息,可能导致分配结果和实际偏好排序出现偏差,因为只有20人规模,完全没必要用近似方案。
注意事项
  • 如果你原来的目标确实需要统计跨团队的偏好(比如跨团队协作的偏好),只需要在辅助变量定义时,把团队对也加入维度即可,逻辑和同团队的线性化完全一致
  • 求解时可以优先绑定SCIP、CBC这类开源整数求解器,对小规模二元问题的求解效率比默认的开源求解器更高

内容的提问来源于stack exchange,提问作者Jace Yang

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.13 08:24:02