Models and algorithms for packing rectangles into the smallest square

We consider the problem of determining the smallest square into which a given set of rectangular items can be packed without overlapping. We present an ILP model, an exact approach based on the iterated execution of a two-dimensional packing algorithm, and a randomized metaheuristic. Such approaches are valid both for the case where the rectangles have fixed orientation and the case where they can be rotated by 90°. We computationally evaluate the performance and the limits of the proposed approaches on a large set of instances, including a number of classical benchmarks from the literature, for both cases above, and for the special case where the items are squares.