3.7.120.2. Strategy that gradually creates a compulsory part
This is a four-phase search procedure that can be used even when the slack is not equal to zero. We first gradually restrict all the -coordinates and then, in the second phase, all -coordinates without fixing them immediately. Then in the third phase we fix all the -coordinates by trying each value (or by making a binary search). Finally in the last phase we fix all the -coordinates as in the third phase. The intuitions behind this heuristics are:
To restrict the -coordinate of each rectangle in order to just create some compulsory part for on the axis. The hope is that it will trigger the filtering algorithm associated with the constraint involved by the non-overlapping constraint, even though the starts of the rectangles on the axis are not yet completely fixed.
Again, as in the previous heuristics, to decrease the combinatorial aspect of the problem by first focussing on all -coordinates.
Restricting gradually the -coordinates in phase one is done by partitioning the domain of the -coordinate of each rectangle into intervals whose sizes induce a compulsory part on the axis for rectangle . To achieve this, the size of an interval has to be less than or equal to the size of rectangle on the axis. Picking the best fraction of the size of a rectangle on the axis depends on the problem as well as on the filtering algorithms behind the scene. Within the context of the smallest rectangle area problemΒ [SimonisSullivan08] and of the SICStus implementation of and H.Β Simonis and B.Β O'Sullivan have shown empirically that the best fraction was located within interval . Restricting the -coordinates in phase two can be done in a way similar to restricting the -coordinates in phase one.