Combinatorial Benders' Cuts for the Strip Packing Problem

Jean-François Côté (), Mauro Dell'Amico () and Manuel Iori ()
Additional contact information
Jean-François Côté: CIRRELT, Université Laval, Québec, Canada G1V 0A6
Mauro Dell'Amico: DISMI, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy
Manuel Iori: DISMI, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy

Operations Research, 2014, vol. 62, issue 3, 643-661

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. 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 reiterated.We show that both the master and the slave are strongly (N-script)(P-script)-hard problems and solve them with tailored preprocessing, 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.

Keywords: strip packing problem; exact algorithm; Benders' decomposition; combinatorial Benders' cut (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1248 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:62:y:2014:i:3:p:643-661

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().