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人规模的问题,求解速度和原来的二次形式几乎没有差异
次选方案(近似、不推荐)
如果不想引入辅助变量,可以通过特征值裁剪把偏好矩阵修正为半正定矩阵,让二次型满足凸性要求,但这个方法是有损近似:
- 对原始偏好矩阵做特征值分解,把所有负的特征值替换为0,得到半正定的近似矩阵
- 用这个近似矩阵代替原来的
part_pref_np代入目标函数 - 注意:这个方法会丢失原矩阵中负偏好对应的信息,可能导致分配结果和实际偏好排序出现偏差,因为只有20人规模,完全没必要用近似方案。
注意事项
- 如果你原来的目标确实需要统计跨团队的偏好(比如跨团队协作的偏好),只需要在辅助变量定义时,把团队对也加入维度即可,逻辑和同团队的线性化完全一致
- 求解时可以优先绑定SCIP、CBC这类开源整数求解器,对小规模二元问题的求解效率比默认的开源求解器更高
内容的提问来源于stack exchange,提问作者Jace Yang
相关产品推荐
相关产品推荐

