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!

Linear programming, and mixed integer programming are part of operations research, which is part of computer science... Granted that the question may fit a bit better in Mathematical SE or Computer Science SE but I actually found many more questions of LP and MIP in SO than in those SE — excalibur1491
– excalibur1491, Commented Nov 21, 2017 at 6:12

Erwin Kalvelagen · Accepted Answer · 2017-11-21 06:42:39Z

5

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.

answered Nov 21, 2017 at 6:42

Erwin Kalvelagen

16.9k3 gold badges17 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

excalibur1491 Over a year ago

That makes sense! Thanks!

Collectives™ on Stack Overflow

LinearProgramming : Non-overlapping constraint?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related