整数线性规划（ILP）中如何定义变量z表示x与y是否相等？

当然可以通过添加线性约束来实现这个逻辑，z需要定义为0-1整数变量（即z ∈ {0, 1}），具体分两种情况给出约束方案：

方案1：无辅助变量（需配合目标函数） #

如果你的目标函数会隐式引导z取正确值（比如最大化z时，x=y的情况下z自然取1；最小化z时x=y取0），可以只用以下两个约束：

x - y ≤ M*(1 - z)
y - x ≤ M*(1 - z)

• 当z=1时，约束简化为 x - y ≤ 0 和 y - x ≤ 0，直接强制x=y；
• 当x≠y时，比如x=1、y=2、M=5，代入第二个约束得 1 ≤ 5*(1-z)，推导得z≤0.8，因z是整数，故z只能为0。

这个方案的局限性是：当x=y时，z理论上可以取0，需要目标函数引导z取1。

方案2：带辅助变量（严格强制z=(x==y)） #

如果需要严格保证x=y时z必须为1，x≠y时z必须为0，需要引入两个额外的0-1变量a和b，添加以下约束：

z ∈ {0, 1}
a ∈ {0, 1}
b ∈ {0, 1}
x - y ≤ M*(1 - z)
y - x ≤ M*(1 - z)
x ≥ y + 1 - M*b
y ≥ x + 1 - M*a
a + b = 1 - z

约束逻辑说明：

• 当z=1时，a + b = 0 强制a=b=0，此时后两个约束变为 x ≥ y+1 和 y ≥ x+1，这显然矛盾，结合前两个约束的x=y要求，最终只能满足x=y；
• 当z=0时，a + b = 1，即a和b中一个为1、一个为0：
  • 若a=1、b=0，约束变为y ≥ x+1，强制x<y；
  • 若a=0、b=1，约束变为x ≥ y+1，强制x>y；
    两种情况都保证x≠y；
• 当x=y时，若假设z=0，会触发a+b=1，进而要求x≥y+1或y≥x+1，与x=y矛盾，因此z只能取1；
• 当x≠y时，若假设z=1，会触发a+b=0，进而要求x≥y+1且y≥x+1，矛盾，因此z只能取0。

这样就严格实现了z=(x==y)的逻辑。

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