如何对整数变量x、y对应的约束蕴含式进行线性化处理

以下方案默认x、y为非负整数，若变量允许取负值，可先对变量做非负偏移转换：令x' = x - min_x、y' = y - min_y（min_x、min_y分别为x、y的最小可行取值），将x'、y'转换为非负整数后再套用对应方案即可。

情况1：x、y为0-1变量 #

无需引入额外辅助变量，直接添加单条约束即可完全匹配要求：
x + y ≤ 1

情况2：x、y为普通非负整数 #

需要引入1个二进制0-1辅助变量z，提前确认x的最大可行上界为M_x、y的最大可行上界为M_y，添加以下3条约束：

• x ≤ M_x * z
• y ≤ M_y * (1 - z)
• z ∈ {0, 1}

约束验证 #

1. 若x ≥ 1，由第一条约束可推导出z必须取1，代入第二条约束得y ≤ 0，非负整数y只能取0，满足x ≥ 1 → y = 0的规则
2. 若y ≥ 1，由第二条约束可推导出1-z必须取1即z=0，代入第一条约束得x ≤ 0，非负整数x只能取0，满足y ≥ 1 → x = 0的规则

注意事项 #

M_x、M_y取实际业务场景中x、y的最大可行值即可，无需设置过大的数值，避免整数规划求解时出现数值不稳定问题。

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