We study the strip packing problem, in which a set of two-dimensional rectangular items has to be packed in a rectangular strip of fixed width and infinite height, with the aim of minimizing the height used. The problem is important because it models a large number of real-world applications, including cutting operations where stocks of materials such as paper or wood come in large rolls and have to be cut with minimum waste, scheduling problems in which tasks require a contiguous subset of identical resources, and container loading problems arising in the transportation of items that cannot be stacked one over the other. The strip packing problem has been attacked in the literature with several heuristic and exact algorithms, nevertheless, benchmark instances of small size remain unsolved to proven optimality since many years. In this paper we propose a new exact method, that solves a large number of the open benchmark instances within a limited computational effort. Our method is based on a Benders’ decomposition, in which in the master we cut items into unit-width slices and pack them contiguously in the strip, and in the slave we attempt to reconstruct the rectangular items by fixing the vertical positions of their unit-width slices. If the slave proves that the reconstruction of the items is not possible, then a cut is added to the master, and the algorithm is re-iterated. We show that both the master and the slave are strongly NP-hard problems, and solve them with tailored pre-processing, lower and upper bounding techniques, and exact algorithms. We also propose several new techniques to improve the standard Benders’ cuts, using the so-called combinatorial Benders’ cuts, and an additional lifting procedure. Extensive computational tests show that the proposed algorithm provides a substantial breakthrough with respect to previously published algorithms.

Combinatorial Benders’ Cuts for the Strip Packing Problem / Coté Jean, François; Dell'Amico, Mauro; Iori, Manuel. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - STAMPA. - 62:3(2014), pp. 643-661. [10.1287/opre.2013.1248]

Combinatorial Benders’ Cuts for the Strip Packing Problem

DELL'AMICO, Mauro;IORI, MANUEL
2014

Abstract

We study the strip packing problem, in which a set of two-dimensional rectangular items has to be packed in a rectangular strip of fixed width and infinite height, with the aim of minimizing the height used. The problem is important because it models a large number of real-world applications, including cutting operations where stocks of materials such as paper or wood come in large rolls and have to be cut with minimum waste, scheduling problems in which tasks require a contiguous subset of identical resources, and container loading problems arising in the transportation of items that cannot be stacked one over the other. The strip packing problem has been attacked in the literature with several heuristic and exact algorithms, nevertheless, benchmark instances of small size remain unsolved to proven optimality since many years. In this paper we propose a new exact method, that solves a large number of the open benchmark instances within a limited computational effort. Our method is based on a Benders’ decomposition, in which in the master we cut items into unit-width slices and pack them contiguously in the strip, and in the slave we attempt to reconstruct the rectangular items by fixing the vertical positions of their unit-width slices. If the slave proves that the reconstruction of the items is not possible, then a cut is added to the master, and the algorithm is re-iterated. We show that both the master and the slave are strongly NP-hard problems, and solve them with tailored pre-processing, lower and upper bounding techniques, and exact algorithms. We also propose several new techniques to improve the standard Benders’ cuts, using the so-called combinatorial Benders’ cuts, and an additional lifting procedure. Extensive computational tests show that the proposed algorithm provides a substantial breakthrough with respect to previously published algorithms.
2014
62
3
643
661
Combinatorial Benders’ Cuts for the Strip Packing Problem / Coté Jean, François; Dell'Amico, Mauro; Iori, Manuel. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - STAMPA. - 62:3(2014), pp. 643-661. [10.1287/opre.2013.1248]
Coté Jean, François; Dell'Amico, Mauro; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
SPP-Paper-Appeared.pdf

Accesso riservato

Descrizione: Main article
Tipologia: Versione pubblicata dall'editore
Dimensione 374.18 kB
Formato Adobe PDF
374.18 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
opre.2013.1248-sm.pdf

Open access

Descrizione: On-line addendum to the article
Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 108.13 kB
Formato Adobe PDF
108.13 kB Adobe PDF Visualizza/Apri
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/979299
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 78
  • ???jsp.display-item.citation.isi??? 69
social impact