### 3.7.115.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 dichotomic 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{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ constraint involved by the non -overlapping constraint, even if 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{𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝}\mathtt{2}$ and $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ 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.