In the Bin Packing Problem with Item Fragmentation a set of items of known weight and a set of bins of limited capacity are given; the task is to find the minimum cost assignment of items to bins without exceeding their capacity. However, contrary to the classical Bin Packing Problem, items can be split and fractionally assigned to different bins at a cost. In this paper we generalize models and properties from the literature by considering a set of heterogeneous bins, possibly having different cost and capacity. We prove that such a natural extension changes substantial features of the problem. We propose both compact and extended formulations and a branch-and-price algorithm that combines column generation techniques and implicit enumeration strategies to achieve guarantees on the optimality of the solutions. We present the results of an extensive experimental campaign proving that our algorithm outperforms general purpose commercial solvers by orders of magnitude.
New formulations for variable cost and size bin packing problems with item fragmentation / M. Casazza. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - 13:2(2019 Mar), pp. 379-398.
|Titolo:||New formulations for variable cost and size bin packing problems with item fragmentation|
|Parole Chiave:||bin packing; column generation; item fragmentation; variable cost and size; control and optimization|
|Settore Scientifico Disciplinare:||Settore MAT/09 - Ricerca Operativa|
Settore INF/01 - Informatica
|Data di pubblicazione:||mar-2019|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/s11590-018-1327-x|
|Appare nelle tipologie:||01 - Articolo su periodico|
File in questo prodotto:
|main.pdf||Articolo principale||Post-print, accepted manuscript ecc. (versione accettata dall'editore)||Open Access Visualizza/Apri|
|Casazza2019_Article_NewFormulationsForVariableCost.pdf||Publisher's version/PDF||Administrator Richiedi una copia|