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.
|Titolo:||Mathematical programming algorithms for bin packing problems with item fragmentation|
|Parole Chiave:||Bin packing; Item fragmentation; Mathematical programming; Branch-and-price|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
Settore MAT/09 - Ricerca Operativa
|Data di pubblicazione:||giu-2014|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.cor.2013.12.008|
|Appare nelle tipologie:||01 - Articolo su periodico|