We consider the problem of packing a set of rectangular items into a strip of fixed width, without overlapping, using minimum height. Items must be packed with their edges parallel to those of the strip, but rotation by 90° is allowed. The problem is usually solved through branch-and-bound algorithms. We propose an alternative method, based on Benders' decomposition. The master problem is solved through a new ILP model based on the arc flow formulation, while constraint programming is used to solve the slave problem. The resulting method is hybridized with a state-of-the-art branch-and-bound algorithm. Computational experiments on classical benchmarks from the literature show the effectiveness of the proposed approach. We additionally show that the algorithm can be successfully used to solve relevant related problems, like rectangle packing and pallet loading.
Logic based Benders' decomposition for orthogonal stock cutting problems / Delorme, Maxence; Iori, Manuel; Martello, Silvano. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 78(2017), pp. 290-298. [10.1016/j.cor.2016.09.009]
Data di pubblicazione: | 2017 | |
Data di prima pubblicazione: | 16-set-2016 | |
Titolo: | Logic based Benders' decomposition for orthogonal stock cutting problems | |
Autore/i: | Delorme, Maxence; Iori, Manuel; Martello, Silvano | |
Autore/i UNIMORE: | ||
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.cor.2016.09.009 | |
Rivista: | ||
Volume: | 78 | |
Pagina iniziale: | 290 | |
Pagina finale: | 298 | |
Codice identificativo ISI: | WOS:000390071400024 | |
Codice identificativo Scopus: | 2-s2.0-84990234529 | |
Citazione: | Logic based Benders' decomposition for orthogonal stock cutting problems / Delorme, Maxence; Iori, Manuel; Martello, Silvano. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 78(2017), pp. 290-298. [10.1016/j.cor.2016.09.009] | |
Tipologia | Articolo su rivista |
File in questo prodotto:
File | Descrizione | Tipologia | |
---|---|---|---|
Delorme-Iori-Martello-2017-Editorial.pdf | Articolo principale in versione editoriale | Versione dell'editore (versione pubblicata) | Administrator Richiedi una copia |
Delorme-Iori-Martello-2017-Postprint.pdf | Versione post-print | Post-print dell'autore (bozza post referaggio) | Open Access Visualizza/Apri |
Pubblicazioni consigliate

I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris