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.
New formulations for variable cost and size bin packing problems with item fragmentation
M. Casazza
2019
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
main.pdf
Open Access dal 04/06/2020
Descrizione: Articolo principale
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
177.37 kB
Formato
Adobe PDF
|
177.37 kB | Adobe PDF | Visualizza/Apri |
Casazza2019_Article_NewFormulationsForVariableCost.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
427.19 kB
Formato
Adobe PDF
|
427.19 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.