3.7.208. 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 diffn 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.41 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.41. Smallest square (of size 123) for packing squares of size 1,2,...,35
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.42 gives the solution found for n=27 by H. Simonis and B. O'Sullivan.
Figure 3.7.42. Rectangle with the smallest surface (of size 148×47) for packing squares of size 1,2,...,27
Download the geost instance for this example in XML or PROLOG format.