CPLEX求解最大化问题时所有变量解恒为0.5的问题排查求助

你的问题核心是目标函数的对称性导致CPLEX始终返回所有变量为0.5的解，以下是具体原因和解决思路：

1. 目标函数的对称性问题 #

先把你的目标函数展开：

objective = sum_{i,j} c[i,j]x[i](1-x[j]) = sum_{i,j} c[i,j]x[i] - sum_{i,j} c[i,j]x[i]x[j]

对任意变量x[k]求偏导，当所有x[i]=0.5时，偏导结果为：

d(obj)/dx[k] = 0.5*(sum_j c[k,j] - sum_j c[j,k])

如果你的c矩阵满足每一行的总和等于对应列的总和（即row_sum[k] = col_sum[k]对所有k成立），那么所有变量取0.5时，梯度为0，满足连续优化的一阶最优条件。如果此时目标函数是凹函数（二次项负定/半正定），这个点就是全局最大值，CPLEX自然会返回它，不管你改c矩阵（只要改完后行和仍等于列和）还是做暖启动都没用。

2. 验证与解决步骤 #

第一步：检查c矩阵的行和与列和 #

计算c矩阵每一行的总和sum(c[i,:])和每一列的总和sum(c[:,j])，如果所有行和等于对应列和，那0.5确实是最优解之一。

第二步：打破对称性，获取不同解 #

如果确认0.5不是你想要的唯一最优解，或者想打破对称得到不同取值的解，可以用以下方法：

• 添加微小扰动项：在目标函数中加入一个带微小差异系数的线性项，打破对称。比如：

  # 给每个变量加不同的微小奖励系数，数值可自行调整
  epsilon = [1e-4 * i for i in range(len(c))]
  objective = mdl.sum(
      [c[i, j] * x[i] * (1 - x[j]) for i in range(len(c)) for j in range(len(c))]
  ) + mdl.sum(epsilon[i] * x[i] for i in range(len(c)))
  

  这样每个变量的“权重”略有差异，CPLEX会返回变量取值不同的最优解。

• 修改c矩阵：调整c矩阵中的部分元素，让行和不等于列和，破坏原有的对称条件。比如修改c[0,1]的值，使得sum(c[0,:])≠sum(c[:,0])。

第三步：优化暖启动设置 #

你的暖启动只设置了x[0]和x[1]的值，其他变量未指定，CPLEX可能会用默认初始值。如果要让暖启动生效，建议给所有变量都设置初始值，比如：

warmstart = mdl.new_solution()
for i in range(len(c)):
    # 给每个变量设置不同的初始值
    warmstart.add_var_value(x[i], 0.1*(i+1))
mdl.add_mip_start(warmstart)

注意：如果0.5是全局最优解，暖启动只能加快收敛，但最终还是会回到这个点，所以核心还是要打破对称性。

第四步：检查求解器设置 #

确保CPLEX使用的是适合连续二次问题的求解器，可以显式设置求解器参数，比如调整收敛容差：

mdl.parameters.optimalitytarget = 3  # 针对QP问题的最优性目标
mdl.parameters.tolerances.optimality = 1e-9  # 缩小最优性容差

代码修改示例 #

以下是添加扰动项后的完整代码：

from docplex.mp.model import Model

# 示例c矩阵，替换为你实际的成本矩阵
c = [[1, 2], [3, 4]]

mdl = Model()
x = [mdl.continuous_var(0,1,name="x%s" % i) for i in range(len(c))]

# 添加扰动项打破对称
epsilon = [1e-4 * i for i in range(len(c))]
objective =  mdl.sum(
    [c[i, j] * x[i] * (1 - x[j]) for i in range(len(c)) for j in range(len(c))]
) + mdl.sum(epsilon[i] * x[i] for i in range(len(c)))

mdl.maximize(objective)

# 全变量暖启动
warmstart=mdl.new_solution()
for i in range(len(c)):
    warmstart.add_var_value(x[i], 0.1*(i+1))
mdl.add_mip_start(warmstart)

sol=mdl.solve(log_output=True)
if sol:
    print([sol[x[i]] for i in range(len(c))])

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