Dual strategy for rectangle placement problems with no slack

When the available space is equal to the total area of the rectangles to place (i.e.,Β we have no slack) this is a two-phase search procedure originally introduced inΒ [AggounBeldiceanu93] where we first fix all the x -coordinates and then, in the second phase, all the y -coordinates. The intuitions behind this heuristics are:

  • To systematically fill the Β placement space from right to left in order to avoid creating small holes that cannot be filled.

  • To decrease the combinatorial aspect of the problem by focussing first on all x -coordinates. This stems from the fact that it is usually easy to extend a partial solution, where all x -coordinates are fixed, to a full solution.

Fixing the x -coordinates is done by:

  • First, compute the minimum min x over the minimum values of the x -coordinates of the rectangles for which the x-coordinate is not already fixed.

  • Second, create a choice point and, in each branch:

    • Fix the x-coordinate of a rectangle R for which the x -coordinates is not already fixed to value min x . Usually rectangles are considered by decreasing height (and decreasing width in case of tie).

    • On backtracking, enforce the fact that the x -coordinate of rectangle R is strictly greater than min x .

  • Third, fail when all branches issued from a choice point have been tried (since otherwise we would create a hole at position min x because, on the x axis all rectangles that could start at position min x were delayed after min x ; in order to not cut valid choices, this third part assumes that the minimum value of the x -coordinate of each rectangle is pruned with respect to the compulsory part profile of the corresponding πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraint.).

Since, as we said early on, it is usually easy to extend a partial solution, where all x -coordinates are fixed, to a full solution where all y-coordinates are also fixed, the search strategy used for fixing the y -coordinates is usually not so important, at least when strong filtering algorithms are usedΒ [BeldiceanuCarlssonPoder08].