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.
Minimum tiling of a rectangle by squares / Monaci, Michele*; dos Santos, André Gustavo. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - STAMPA. - 271:2(2018), pp. 831-851. [10.1007/s10479-017-2746-2]
Minimum tiling of a rectangle by squares
Monaci, Michele;
2018
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
minimum tiling of a rectangle by squares post-print.pdf
accesso aperto
Tipo:
Postprint
Licenza:
Licenza per accesso libero gratuito
Dimensione
455.87 kB
Formato
Adobe PDF
|
455.87 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
