linear-programming - 线性规划：非重叠约束？

Question

我想在线性程序（或必要时的 MIP）中编写一个非重叠约束（即 2 个矩形不重叠）。我知道如何在约束编程中做到这一点：

对于对象 i 和 j：

x[i]+dx[i]<=x[j] 或 y[i]+dy[i]<=y[j] 或 x[j]+dx[j]<=x[i] 或 y[ j]+dy[j]<=y[i] 其中 x 和 y 是包含对象坐标的数组，dx 和 dy 是对象的维度。

知道在 LP/MIP 中执行此操作的最佳方法吗？谢谢！

Answer 1

总结一下：您的约束编程约束是

x[i]+dx[i]<=x[j] OR 
y[i]+dy[i]<=y[j] OR 
x[j]+dx[j]<=x[i] OR 
y[j]+dy[j]<=y[i] 

在 MIP 模型中，您可以将其建模为：

x[i]+dx[i]<=x[j] + M*b[i,j,1] 
y[i]+dy[i]<=y[j] + M*b[i,j,2] 
x[j]+dx[j]<=x[i] + M*b[i,j,3]
y[j]+dy[j]<=y[i] + M*b[i,j,4]
sum(k, b[i,j,k])<=3
b[i,j,k] in {0,1}

其中 M 是一个足够大的常数（参见链接）。

如果您比较了矩形 i 和 j，则不必再比较 j 和 i。所以在上面的方程中，我们可以forall i<j利用这种对称性。