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]

Logic based Benders' decomposition for orthogonal stock cutting problems

IORI, MANUEL;
2017

Abstract

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.
16-set-2016
78
290
298
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]
Delorme, Maxence; Iori, Manuel; Martello, Silvano
File in questo prodotto:
File Dimensione Formato  
Delorme-Iori-Martello-2017-Editorial.pdf

non disponibili

Descrizione: Articolo principale in versione editoriale
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 579.13 kB
Formato Adobe PDF
579.13 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Delorme-Iori-Martello-2017-Postprint.pdf

accesso aperto

Descrizione: Versione post-print
Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 205.61 kB
Formato Adobe PDF
205.61 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1110923
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 31
  • ???jsp.display-item.citation.isi??? 28
social impact