线性规划中二值与整数变量乘积线性化及CPLEX实现求助

你原有约束存在笔误，正确的每日到岗人数约束应为所有入职批次的到岗人数总和满足当日需求，即 sum(i in 1..7) (x_i * y_ij) >= Required_j 对全部日期j成立。针对其中x_i * y_ij的二值变量乘整数变量的乘积项，可通过引入中间变量的方式完成线性化：

1. 引入正整数中间变量z_ij，等价表示x_i * y_ij，含义为第i天入职的员工中第j天实际到岗的人数
2. 添加以下4条线性约束即可完成等价转换，其中M为x_i的合理上界（可直接取所有日期最大人力需求的2倍，或你预估的最大招聘人数，取值越小求解速度越快）：

• z_ij <= x_i
• z_ij <= M * y_ij
• z_ij >= x_i - M * (1 - y_ij)
• z_ij >= 0

转换后原需求约束可替换为完全线性的形式：sum(i in 1..7) z_ij >= Required_j #

// 基础参数定义
int Days = 7;
int Required[1..Days] = [10, 12, 9, 8, 11, 7, 6]; // 替换为你的实际每日人力需求
int MaxEmp = max(r in Required) * 2; // x_i上界，可根据实际情况调整

// 决策变量定义
dvar int+ x[1..Days]; // 第i天入职的员工人数，非负整数
dvar boolean y[1..Days][1..Days]; // 二值变量，第i批次员工第j天是否上班，1=上班0=休假
dvar int+ z[1..Days][1..Days]; // 线性化中间变量

// 目标函数：最小化总招聘人数
minimize sum(i in 1..Days) x[i];

subject to {
    // 每批次员工每周固定休假2天，即每周上班5天
    forall(i in 1..Days)
        sum(j in 1..Days) y[i][j] == 5;
    
    // 乘积项线性化约束组
    forall(i in 1..Days, j in 1..Days) {
        z[i][j] <= x[i];
        z[i][j] <= MaxEmp * y[i][j];
        z[i][j] >= x[i] - MaxEmp * (1 - y[i][j]);
        z[i][j] >= 0;
    }

    // 每日到岗人数满足需求
    forall(j in 1..Days)
        sum(i in 1..Days) z[i][j] >= Required[j];
}

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