3.7.223. Smallest rectangle area

Denotes the fact that a constraint can be used for finding the smallest rectangle area where one can pack a given set of rectangles (or squares). A first example of such packing problem attributed to S.Β W.Β Golomb is to find the smallest square that can contain the set of consecutive squares from 1Γ—1 up to nΓ—n so that these squares do not overlap each other. A program using the πšπš’πšπšπš— constraint was used to construct such a table for n∈{1,2,...,25,27,29,30} inΒ [BeldiceanuBourreauChanRivreau97]. New optimal solutions for this problem were found inΒ [SimonisSullivan08] for n=26,31,35. FigureΒ 3.7.54 gives the solution found for n=35 by H.Β Simonis and B.Β O'Sullivan. Algorithms and lower bounds for solving the same problem can also be respectively found inΒ [CapraraLodiMartelloMonaci06] and inΒ [Korf04].

Figure 3.7.54. Smallest square (of size 123) for packing squares of size 1,2,...,35
figpstrick/squares_in_square35_example

Download the geost instance for this example in XML or PROLOG format.

In his paper (i.e.,Β [Korf04]), RichardΒ E.Β Korf also considers the problem of finding the minimum -area rectangle that can contain the set of consecutive squares from 1Γ—1 up to nΓ—n and solve it up to n=25. In 2008 this value was improved up to n=27 by H.Β Simonis and B.Β O'SullivanΒ [SimonisSullivan08]. FigureΒ 3.7.55 gives the solution found for n=27 by H.Β Simonis and B.Β O'Sullivan.

Figure 3.7.55. Rectangle with the smallest surface (of size 148Γ—47) for packing squares of size 1,2,...,27
figpstrick/squares_in_rectangle27_example

Download the geost instance for this example in XML or PROLOG format.