linear-programming - 线性规划 : Non-overlapping constraint?

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 是一个足够大的常数(参见 link)。

如果你已经比较过矩形 i 和 j，你就不必再比较 j 和 i 了。所以在上面的等式中我们可以使用forall i<j利用这种对称性。