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.
bin packing; column generation; item fragmentation; variable cost and size; control and optimization
Settore MAT/09 - Ricerca Operativa
Settore INF/01 - Informatica
mar-2019
Article (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/640807
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact