线性规划矩形非重叠约束binary variable和≤3的原因咨询

首先明确建模中四个二进制变量的基本定义，配套大M松弛约束的规则：

• 四个0-1变量z1,z2,z3,z4分别对应两个待排布矩形A、B的四个相对位置判定：
  • z1=1：A完全位于B左侧（A的右边界 ≤ B的左边界）
  • z2=1：A完全位于B右侧（A的左边界 ≥ B的右边界）
  • z3=1：A完全位于B下方（A的上边界 ≤ B的下边界）
  • z4=1：A完全位于B上方（A的下边界 ≥ B的上边界）
• 每个变量对应一条带大M的松弛约束：变量取0时，对应方位的约束会被大M松弛，不产生限制；变量取1时，对应方位的位置约束生效。

这里的核心误解有两点：

1. 矩形非重叠仅需要满足任意1个方位关系即可，不需要同时满足2个。比如A完全在B左侧时，不管上下位置是在B上方、下方，还是和B的上下范围有重叠，两个矩形都已经不存在重叠区域。
2. 合法的非重叠状态下，完全可以同时有2个变量取1：比如A位于B的左下方时，z1=1（A在B左）和z3=1（A在B下）会同时成立，此时变量和为2，属于完全合法的可行解，因此把上界设为2本身就是错误的，会切掉大量可行解。

资料里把约束设为和≤3，本质是一个零成本的冗余有效割，不会改变模型的可行域，核心作用是减少求解器的无效计算：

1. 从基本逻辑就能判断，四个方位关系全部成立（四个变量全为1，和为4）是绝对不可能的——不存在矩形A同时在B的左、右、上、下四个方向的情况，这个取值组合没有任何可行解。
2. 这份参考资料属于入门向演示，没有额外添加z1+z2≤1（左右方位互斥）、z3+z4≤1（上下方位互斥）这两个约束：因为只要矩形的宽、高为正，即使出现z1=1,z2=1这类和为2或3的矛盾取值，对应的x、y方向约束会自然推导出宽/高≤0的矛盾结果，求解器会自动判定这些分支不可行，不需要额外写约束排除，能降低入门者的理解成本。
3. 加上z1+z2+z3+z4 ≤3的约束，只需要一行代码就可以直接把“四个变量全为1”这个完全无意义的不可行分支提前剪掉，几乎没有建模成本，还能小幅提升求解效率，完全适配入门演示的小规模问题场景。

补充说明：如果是工业级大规模排布问题，一般不会只用这个宽松的≤3约束，会补充更紧的互斥约束z1+z2≤1、z3+z4≤1，此时变量和的自然上界就是2，模型线性松弛的界更紧，求解速度会更快。入门资料里写≤3只是为了简化建模逻辑，降低理解门槛，不是什么必须严格遵守的标准形式。

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