Using Cumulative function for Rectangular Placement

user_13872671 0
Viewed 188

I have a rectangular placement problem. What I want is to place rectangles of size x by y into another rectangle without overlapping. What I want in the end is the starting point of each rectange.

I made this part OF code for it, the logic was that it would cumulatively check for x and y axis along the height and width of the function. However, when I run this, it works for a few instances but not for others. So I posted one of the specific instances for which it gives repeat points here to ask what the issue is and what changes can be made.

Thank you

constraint cumulative(start, x, y, height);
constraint cumulative(starty, y, x, width);
minizinc constraint-programming
2 Answers

It should work if you add the diffn constraint which constraint the boxes to be non overlapping, i.e.

include(globals.mzn);
....
constraint diffn(start,starty,x,y);
...

See https://www.minizinc.org/doc-2.4.3/en/lib-globals.html?highlight=diffn for more about diffn.

One of the 10752 solutions is:

15  15
10
1: 3 3  0 9
2: 3 4  12 0
3: 3 5  12 10
4: 3 6  12 4
5: 3 7  9 8
6: 3 8  9 0
7: 3 9  0 0
8: 3 12 3 0
9: 3 15 6 0
10: 6 3 0 12

I checked on paper that this is a proper solution, i.e. no overlapping and all cells in the 15x15 box are covered.

user_1956360

Cumulative will only check the resource usage in it's single dimension (which is useful and can give good pruning sometimes), it does not ensure the no-overlaps property. The diffn global constraint is the canonical one to use for ensuring no-overlap.

user_339650
Related