LinearProgramming : Non-overlapping constraint?

Question

I want to write a non overlapping constraint (that is, 2 rectangles don't overlap) in a linear program (or a MIP if necessary). I know how to do it in Constraint programming:

For object i and j:

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] where x and y are the arrays containing the coordinates of the objects and dx and dy are the dimensions of the objects.

Any idea of the best way of doing this in LP/MIP? Thanks!

Answer 1

To summarize: your Constraint Programming constraints are

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] 

In a MIP model you can model this as:

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}

where M is a large enough constant (see link).

If you have compared rectangle i and j you do not have to compare j and i anymore. So in the above equations we can use forall i<j to exploit this symmetry.