We are given a set of items, each characterized by a weight and a fragility, and a large number of uncapacitated bins. Our aim is to find the minimum number of bins needed to pack all items, in such a way that in each bin the sum of the item weights is less than or equal to the smallest fragility of an item in the bin. The problem is known in the literature as the Bin Packing Problem with Fragile Objects, and appears in the telecommunication field, when one has to assign cellular calls to available channels by ensuring that the total noise in a channel does not exceed the noise acceptance limit of a call.We propose several techniques to compute lower and upper bounds for this problem. For what concerns lower bounds, we present combinatorial techniques with guaranteed worst case and a more complex bound based on a column generation algorithm. We also present a technique to compute, in a fast heuristic way, dual information that is used to strengthen the convergence of the column generation. For what concerns upper bounds, we present a large set of constructive heuristics followed by a Variable Neighborhood Search algorithm. Our heuristic techniques are aimed at both computing upper bounds and strengthening the behavior of the lower bounds in a matheuristic fashion. Extensive computational tests show the effectiveness of the proposed algorithms.

Lower and upper bounds for the Bin Packing Problem with Fragile Objects / F., Clautiaux; Dell'Amico, Mauro; Iori, Manuel; A., Khanafer. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 163:1(2014), pp. 73-86. [10.1016/j.dam.2012.04.010]

Lower and upper bounds for the Bin Packing Problem with Fragile Objects

DELL'AMICO, Mauro;IORI, MANUEL;
2014

Abstract

We are given a set of items, each characterized by a weight and a fragility, and a large number of uncapacitated bins. Our aim is to find the minimum number of bins needed to pack all items, in such a way that in each bin the sum of the item weights is less than or equal to the smallest fragility of an item in the bin. The problem is known in the literature as the Bin Packing Problem with Fragile Objects, and appears in the telecommunication field, when one has to assign cellular calls to available channels by ensuring that the total noise in a channel does not exceed the noise acceptance limit of a call.We propose several techniques to compute lower and upper bounds for this problem. For what concerns lower bounds, we present combinatorial techniques with guaranteed worst case and a more complex bound based on a column generation algorithm. We also present a technique to compute, in a fast heuristic way, dual information that is used to strengthen the convergence of the column generation. For what concerns upper bounds, we present a large set of constructive heuristics followed by a Variable Neighborhood Search algorithm. Our heuristic techniques are aimed at both computing upper bounds and strengthening the behavior of the lower bounds in a matheuristic fashion. Extensive computational tests show the effectiveness of the proposed algorithms.
2014
163
1
73
86
Lower and upper bounds for the Bin Packing Problem with Fragile Objects / F., Clautiaux; Dell'Amico, Mauro; Iori, Manuel; A., Khanafer. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 163:1(2014), pp. 73-86. [10.1016/j.dam.2012.04.010]
F., Clautiaux; Dell'Amico, Mauro; Iori, Manuel; A., Khanafer
File in questo prodotto:
File Dimensione Formato  
Clautiaux-DellAmico-Iori-Khanafer-DAM-2014.pdf

Accesso riservato

Descrizione: Articolo principale
Tipologia: Versione pubblicata dall'editore
Dimensione 276.72 kB
Formato Adobe PDF
276.72 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

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