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 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. [10.1287/ijoc.2018.0806]

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

Iori, Manuel
2018

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.
2018
2-nov-2018
30
4
646
661
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. [10.1287/ijoc.2018.0806]
Côté, Jean-François; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
CIRRELT-2016-28.pdf

Open access

Descrizione: Versione pre print
Tipologia: Versione originale dell'autore proposta per la pubblicazione
Dimensione 961.6 kB
Formato Adobe PDF
961.6 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/1168938
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 37
  • ???jsp.display-item.citation.isi??? 35
social impact