Exact algorithms for the bin packing problem with fragile objects
| hal.structure.identifier | Università degli Studi di Modena e Reggio Emilia = University of Modena and Reggio Emilia [UNIMORE] | |
| dc.contributor.author | ALBA MARTÍNEZ, Manuel | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | CLAUTIAUX, François | |
| hal.structure.identifier | Università degli Studi di Modena e Reggio Emilia = University of Modena and Reggio Emilia [UNIMORE] | |
| dc.contributor.author | DELL'AMICO, Mauro | |
| hal.structure.identifier | Università degli Studi di Modena e Reggio Emilia = University of Modena and Reggio Emilia [UNIMORE] | |
| dc.contributor.author | IORI, Manuel | |
| dc.date.accessioned | 2024-04-04T02:20:54Z | |
| dc.date.available | 2024-04-04T02:20:54Z | |
| dc.date.created | 2013 | |
| dc.date.issued | 2013-08-31 | |
| dc.identifier.issn | 1572-5286 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/189529 | |
| dc.description.abstractEn | We are given a set of objects, 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 objects, in such a way that in each bin the sum of the object weights is less than or equal to the smallest fragility of an object 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 a branch-and-bound and several branch-and-price algorithms for the exact solution of the problem, and improve their performance by the use of lower bounds and tailored optimization techniques. In addition we also develop algorithms for the optimal solution of the related knapsack problem with fragile objects. We conduct an extensive computational evaluation on the benchmark set of instances, and show that the proposed algorithms perform very well. | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.title.en | Exact algorithms for the bin packing problem with fragile objects | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1016/j.disopt.2013.06.001 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | Discrete Optimization | |
| bordeaux.page | 210-223 | |
| bordeaux.volume | 10 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 3 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00909480 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00909480v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Discrete%20Optimization&rft.date=2013-08-31&rft.volume=10&rft.issue=3&rft.spage=210-223&rft.epage=210-223&rft.eissn=1572-5286&rft.issn=1572-5286&rft.au=ALBA%20MART%C3%8DNEZ,%20Manuel&CLAUTIAUX,%20Fran%C3%A7ois&DELL'AMICO,%20Mauro&IORI,%20Manuel&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||