In this paper we consider a class of bin packing problems from the literature having the following distinctive feature: items may be fragmented at a price. Problems of this kind arise in diverse application fields like logistics and telecommunications, and have already been extensively tackled from an approximation point of view. We focus on the case in which splitting produces no overhead, a fixed number of bins is given and the number of fragments or fragmentations needs to be minimized. We first investigate the theoretical properties of the problem. Then we elaborate on them to devise mathematical programming models and algorithms, yielding both exact optimization algorithms and effective heuristics. An extensive experimental campaign proves that our approach is very effective, and highlights which features make an instance computationally harder to solve.

Mathematical programming algorithms for bin packing problems with item fragmentation / M. Casazza, A. Ceselli. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 46(2014 Jun), pp. 1-11. [10.1016/j.cor.2013.12.008]

Mathematical programming algorithms for bin packing problems with item fragmentation

M. Casazza;A. Ceselli
2014

Abstract

In this paper we consider a class of bin packing problems from the literature having the following distinctive feature: items may be fragmented at a price. Problems of this kind arise in diverse application fields like logistics and telecommunications, and have already been extensively tackled from an approximation point of view. We focus on the case in which splitting produces no overhead, a fixed number of bins is given and the number of fragments or fragmentations needs to be minimized. We first investigate the theoretical properties of the problem. Then we elaborate on them to devise mathematical programming models and algorithms, yielding both exact optimization algorithms and effective heuristics. An extensive experimental campaign proves that our approach is very effective, and highlights which features make an instance computationally harder to solve.
Bin packing; Item fragmentation; Mathematical programming; Branch-and-price
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
giu-2014
Article (author)
File in questo prodotto:
File Dimensione Formato  
2014_COR_BPPIF_Casazza_Ceselli.pdf

accesso riservato

Descrizione: Articolo principale, versione finale
Tipologia: Publisher's version/PDF
Dimensione 356.85 kB
Formato Adobe PDF
356.85 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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/2434/231198
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 22
social impact