CPLEX 12.10 OPL求解MILP时报错5002约束非凸如何解决

CPLEX返回5002非凸错误和你推测的t=0初始值设置没有关系，核心问题出在co01约束的x[s][t] * R[s][t]项：x[s][t]是0-1布尔决策变量，R[s][t]是连续决策变量，两个决策变量直接相乘构成双线性项，属于典型的非凸结构。CPLEX默认的MILP求解器仅支持线性/凸模型，遇到这类非凸项会直接抛出异常，和初始值、索引写法无关。

这类0-1变量与连续变量相乘的双线性项可以通过大M线性化完全等价转换为线性约束，转换后模型为标准混合整数线性规划，可直接被CPLEX求解，不需要开启非凸求解模式，求解效率远高于直接调用非凸求解器。
线性化步骤如下：

• 新增辅助连续变量w[s][t]，用于等价替换x[s][t] * R[s][t]
• 根据现有约束推导R[s][t]的上下界：
  • 下界R_LB[s] = alfa * d[s] + beta：因SDLL是非负变量，最小值为0
  • 上界R_UB[s] = alfa * (SDLLumt + d[s]) + beta：因SDLL有硬上界SDLLumt
    注：如果参数alfa为负值，交换上述上下界计算式即可
• 为辅助变量w添加4组线性约束，保证w和x*R完全等价：
  • w[s][t] <= R_UB[s] * x[s][t]：x=0时w必须为0，x=1时w不超过R的上界
  • w[s][t] >= R_LB[s] * x[s][t]：x=0时w必须为0，x=1时w不低于R的下界
  • w[s][t] <= R[s][t] - R_LB[s] * (1 - x[s][t])：x=1时w与R相等
  • w[s][t] >= R[s][t] - R_UB[s] * (1 - x[s][t])：x=1时w与R相等
• 将co01约束中的乘积项替换为w[s][t]
• 优化原初始值约束写法：直接给SDLL[s][0]赋初值，不需要通过t=1时的t-1索引间接赋值，避免不必要的索引判断。

// Define Indecies
int S=...;   
int T=...;   
range Segments = 1..S;
range Time = 0..T;

// Define Parameters and Data
float f = ...;
float Cpm = ...;
float L = ...;
float SDLL0[Segments]=...;
float d[Segments] = ...;  
float alfa = ...;   
float beta = ...;   
float SDLLumt=...;

// 预计算R的上下界用于线性化
float R_LB[s in Segments] = alfa * d[s] + beta;
float R_UB[s in Segments] = alfa * (SDLLumt + d[s]) + beta;

// variables
dvar boolean z [Time];
dvar boolean x [Segments][Time];
dvar boolean y [Segments][Time];
dvar float+ SDLL[Segments][Time];
dvar float R[Segments][Time];
dvar float+ w[Segments][Time]; // 线性化辅助变量，等价于x[s][t]*R[s][t]

// Objective Function
minimize 
    sum( t in Time ) ( z[t] * f + sum (s in Segments) x[s][t] * L * Cpm) ;
    
// Constraints
subject to {
   // 初始条件直接赋值，逻辑更清晰
   forall(s in Segments)
     init_SDLL: SDLL[s][0] == SDLL0[s];
          
   forall(s in Segments, t in Time: t>=1)   
     co01:    SDLL[s][t] == SDLL[s][t-1] + d[s] - w[s][t] ;  

   forall(s in Segments, t in Time: t>=1)
     co03:    R[s][t] == alfa * ( SDLL[s][t-1] + d[s] ) + beta;

   forall(s in Segments, t in Time: t>=1)    
     co04:    SDLL[s][t] <= SDLLumt ;     
     
   forall(t in Time: t>=1, s in 1..(S-1))    
     co05:    y[s][t] >= x[s][t] - x[s+1][t] ;         
     
   forall(t in Time: t>=1 , s in Segments : s==S)    
     co06:    y[s][t] >= x[s][t] ;      
     
   forall(s in Segments, t in Time: t>=1)   
     co07:    z[t] >= x[s][t] ;

   // 双线性项线性化约束
   forall(s in Segments, t in Time: t>=1){
     c_w1: w[s][t] <= R_UB[s] * x[s][t];
     c_w2: w[s][t] >= R_LB[s] * x[s][t];
     c_w3: w[s][t] <= R[s][t] - R_LB[s] * (1 - x[s][t]);
     c_w4: w[s][t] >= R[s][t] - R_UB[s] * (1 - x[s][t]);
   }                                                               
 }

• 将optimality target设置为3无法解决问题：该参数仅控制求解的最优性目标，不会自动处理非凸结构。只有将参数设为2时CPLEX才会启动非凸全局求解模块，但非凸求解的效率远低于线性化后的MILP模型，不推荐使用。
• 调用CPO求解器时将dvar float改为dexpr float报错：本质是没有消除双线性非凸项，仅修改变量类型无法解决结构上的非凸问题，按上述方法线性化后无论调用CPLEX MIP求解器还是CPO求解器都可正常运行。

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