The Meet-in-the-Middle Principle for Cutting and Packing Problems

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

INFORMS Journal on Computing, 2018, vol. 30, issue 4, 646-661

Abstract: Cutting and packing (C&P) is a fundamental research area that models a large number of managerial and industrial optimization issues. A solution to a C&P problem basically consists of a set of one-dimensional or multidimensional items packed in/cut from one or more bins, by satisfying problem constraints and minimizing a given objective function. Normal patterns are a well-known C&P technique used to build solutions where each item is aligned to the bottom of the bin along each dimension. They are used in several C&P techniques because they can reduce the search space while preserving optimality, but their limit is that their number grows consistently when number of items and size of the bin increase. In this paper we propose a new set of patterns, called meet in the middle, that preserves optimality and leads to several interesting results. Their computation is achieved with the same time complexity as that of the normal patterns, but their number is never higher, and in practical applications it frequently shows reductions of about 50%. These new patterns are applied to improve some exact state-of-the-art C&P techniques, including arc-flow formulations, combinatorial branch-and-bound algorithms, and mixed-integer linear programs. The efficacy of the improved techniques is assessed by extensive computational tests on a number of relevant applications. The online appendix is available at https://doi.org/10.1287/ijoc.2018.0806 .

Keywords: cutting and packing; normal patterns; meet in the middle; cutting stock • orthogonal packing (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0806 (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:orijoc:v:30:y:2018:i:4:p:646-661

Access Statistics for this article

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