Originally posted by: excalibur1491

Hi,

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? The OR's are throwing me out... 

Thanks!

Unless you are using the callable library or Python, there is direct support for OR constraints in the CPLEX modeling APIs: class IloOr in C++/Java/C#-Concert, operator '||' (see here) in OPL. These things will automatically be linearized for the engine.

If you like to see how this linearization is done then just export to an LP file. That will have the linearized constraints instead of the OR constraints.

Originally posted by: excalibur1491

Thanks for your reply!

I'm actually not using CPLEX, thats why I posted this in the "Matematical Prog" section. I have used Cplex and these forums before, and now I am forced to use something else (due to licencing issues as I am not a student anymore), but I thought I could still get some help from here :)

OK, then the question is what modeling devices you have available in your new environment. Do you have indicator constraints or any other sort of logical constraints?

The linearization in CPLEX roughly works like this:

1. for each term in the OR create an auxiliary binary variable that is 1 if and only if the term is satisfied
2. add a constraint that forces the sum of auxiliary binary variables to be >= 1

Step 1 is easily done with indicator constraints but may be more complicated if you don't have them.

Originally posted by: excalibur1491

Thanks for your prompt response again!

I am using Google OR-Tools, which is open source, and is a wrapper for some MIP solvers.

As far as I can tell, it does not support indicators, but actually, I think I found how to do it, in this link:

http://yetanothermathprogrammingconsultant.blogspot.com.au/2017/07/rectangles-no-overlap-constraints.html

I leave it here, in case someone wonders how to do it.

I think that solution is probably what you had in mind, as there is exactly one binary for each constraint; but in their case the sum of the binaries has to be at most 3, because the binaries mean "which constraint is not enforce" (so at least one is enforced).

Thanks again :)