Minimum tiling of a rectangle by squares

Abstract

We consider a two-dimensional problem in which one is required to split a given rectangular bin into the smallest number of items. The resulting items must be squares to be packed, without overlapping, into the bin so as to cover all the given rectangle. We present a mathematical model and a heuristic algorithm that is proved to find the optimal solution in some special cases. Then, we introduce a relaxation of the problem and present different exact approaches based on this relaxation. Finally, we report computational experiments on the performances of the algorithms on a large set of randomly generated instances.