如何解决CPLEX混合整数锥规划中的非凸变量错误

问题本质 #

二进制变量x(i)与连续变量v(i)的乘积项属于非凸结构，CPLEX的混合整数锥规划求解器不支持这类非凸项，因此必须通过线性化或逻辑拆解将约束转化为可求解的凸/线性形式。

方法1：引入辅助变量线性化乘积项 #

对每个索引i，定义辅助变量w(i) = x(i)*v(i)，添加以下线性约束实现等价转化：

• w(i) ≤ U(i)*x(i)，其中U(i)为v(i)的上界
• w(i) ≥ L(i)*x(i)，其中L(i)为v(i)的下界
• w(i) ≤ v(i) - L(i)*(1 - x(i))
• w(i) ≥ v(i) - U(i)*(1 - x(i))

将原约束替换为：
w(i) - w(j) ≤ 2*(c1 + c2)

方法2：枚举二进制变量组合拆解约束 #

由于x(i)和x(j)均为二进制变量，共有4种取值组合，可直接拆解为线性约束：

1. x(i)=0且x(j)=0：约束恒成立，无需添加
2. x(i)=1且x(j)=0：v(i) ≤ 2*(c1 + c2)
3. x(i)=0且x(j)=1：-v(j) ≤ 2*(c1 + c2)（若v(j)有下界，可结合实际场景简化）
4. x(i)=1且x(j)=1：v(i) - v(j) ≤ 2*(c1 + c2)

方法3：使用CPLEX内置自动线性化工具 #

在OPL语言中，可直接编写乘积项，通过cplex.linearize()自动完成线性化。示例代码：

dvar boolean x[I];
dvar float v[I];
dvar float w[I] = x[i]*v[i];
constraint targetConstraint: w[i] - w[j] <= 2*(c1 + c2);

execute {
  cplex.linearize();
}

注意：自动线性化会引入额外辅助变量，可能增大模型规模，需根据求解效率需求权衡。

关键注意点 #

• 必须为v(i)设定合理的上下界U(i)和L(i)：过松会降低模型松弛性，求解变慢；过紧可能排除可行解，需结合问题实际背景确定。
• 转化后的约束需保证整体模型仍满足混合整数锥规划的凸性要求，避免引入新的非凸结构。

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