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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2017
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
Delorme-Iori-Martello-2017-Editorial.pdf

Accesso riservato

Descrizione: Articolo principale in versione editoriale
Tipologia: Versione pubblicata dall'editore
Dimensione 579.13 kB
Delorme-Iori-Martello-2017-Postprint.pdf

Open access

Descrizione: Versione post-print
Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 205.61 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1110923`