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 πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ 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 πšπš’πšœπš“πš˜πš’πš—πš2 and πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ H.Β Simonis and B.Β O'Sullivan have shown empirically that the best fraction was located within interval [0.2,0.3]. Restricting the y-coordinates in phase two can be done in a way similar to restricting the x-coordinates in phase one.