Our team is trying out the or-tools cp-sat solver for a geometric puzzle. Here we have a 2D matrix with n x n size where rectangles of varying horizontal size and a fixed vertical size, are placed on. These rectangles have certain constraints i.e. only 2 of a certain size can be placed next to each other or the joints between rectangles cannot be placed above each other.
When we setup and run our model, if the matrix size becomes large > 20x20 rows/columns, performance drops exponentially. This is only with a 2D interval constraint. We are curious if this is too large of a problem for the cp solver to complete in a reasonable time or that we have setup our model incorrectly.
Our model is setup in such a way that there are more rectangles than could be needed in the matrix. As such rectangles can take a horizontal size 0. The other horizontal sizes are 2,3 and 4. The vertical size of each rectangle is always 1. So if we have 20x20 rows/columns of the matrix our number of rectangles is rows*(columns/2) = 200. Now an IntVar of the horizontal size, start column, end column and start row is created. Furthermore, horizontal and vertical interval vars are created.
The constraints are then:
model.AddNoOverlap2D(horizontal_intervals, vertical_intervals)
model.Add(LinearExpr.Sum(rectangle_sizes) == (columns * rows))
Solving this problem, where the matrix is filled with rectangles of size 4, already takes 20 seconds to complete.