This paper considers the two-dimensional strip-packing problem (2SP) in which a set of rectangular items have to be orthogonally packed, without overlapping, into a strip of a given width and infinite height by minimizing the overall height of the packing. The 2SP is NP-hard in the strong sense and finds many practical applications. We propose reduction procedures, lower and upper bounds, and an exact algorithm for the 2SP. The new lower bounds are both combinatorial bounds and bounds derived from different relaxations of mathematical formulations of the 2SP. The new upper bounds are obtained by constructive heuristics based on different strategies to place the items into the strip. The new exact method is based on a branch-and-bound approach. Computational results on different sets of test problems derived from the literature show the effectiveness of the new lower and upper bounds and of the new exact algorithm.

M.A. Boschetti, L. Montaletti (2010). An Exact Algorithm for the Two-Dimensional Strip Packing Problem. OPERATIONS RESEARCH, 58(6), 1774-1791 [10.1287/opre.1100.0833].

An Exact Algorithm for the Two-Dimensional Strip Packing Problem

BOSCHETTI, MARCO ANTONIO;
2010

Abstract

This paper considers the two-dimensional strip-packing problem (2SP) in which a set of rectangular items have to be orthogonally packed, without overlapping, into a strip of a given width and infinite height by minimizing the overall height of the packing. The 2SP is NP-hard in the strong sense and finds many practical applications. We propose reduction procedures, lower and upper bounds, and an exact algorithm for the 2SP. The new lower bounds are both combinatorial bounds and bounds derived from different relaxations of mathematical formulations of the 2SP. The new upper bounds are obtained by constructive heuristics based on different strategies to place the items into the strip. The new exact method is based on a branch-and-bound approach. Computational results on different sets of test problems derived from the literature show the effectiveness of the new lower and upper bounds and of the new exact algorithm.
2010
M.A. Boschetti, L. Montaletti (2010). An Exact Algorithm for the Two-Dimensional Strip Packing Problem. OPERATIONS RESEARCH, 58(6), 1774-1791 [10.1287/opre.1100.0833].
M.A. Boschetti; L. Montaletti
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/87217
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 45
  • ???jsp.display-item.citation.isi??? 39
social impact