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.
|Data di pubblicazione:||2018|
|Titolo:||The Meet-in-the-Middle Principle for Cutting and Packing Problems|
|Autore/i:||Côté, Jean-François; Iori, Manuel|
|Digital Object Identifier (DOI):||10.1287/ijoc.2018.0806|
|Codice identificativo ISI:||WOS:000458386100003|
|Codice identificativo Scopus:||2-s2.0-85056729583|
|Citazione:||The Meet-in-the-Middle Principle for Cutting and Packing Problems / Côté, Jean-François; Iori, Manuel. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 30:4(2018), pp. 646-661.|
|Tipologia||Articolo su rivista|
I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris