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.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.