### 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 $x$-coordinates and then, in the second phase, all $y$-coordinates without fixing them immediately. Then in the third phase we fix all the $x$-coordinates by trying each value (or by making a binary search). Finally in the last phase we fix all the $y$-coordinates as in the third phase. The intuitions behind this heuristics are:

• To restrict the $x$-coordinate of each rectangle $R$ in order to just create some compulsory part for $R$ on the $x$ axis. The hope is that it will trigger the filtering algorithm associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint involved by the non-overlapping constraint, even though the starts of the rectangles on the $x$ 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 $x$-coordinates.

Restricting gradually the $x$-coordinates in phase one is done by partitioning the domain of the $x$-coordinate of each rectangle $R$ into intervals whose sizes induce a compulsory part on the $x$ axis for rectangle $R$. To achieve this, the size of an interval has to be less than or equal to the size of rectangle $R$ on the $x$ axis. Picking the best fraction of the size of a rectangle on the $x$ 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 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}$ and $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ H.Β Simonis and B.Β O'Sullivan have shown empirically that the best fraction was located within interval $\left[0.2,0.3\right]$. Restricting the $y$-coordinates in phase two can be done in a way similar to restricting the $x$-coordinates in phase one.