We consider a particular Bin Packing Problem in which some pairs of items may be in conflict and cannot be assigned to the same bin. The problem, denoted as the Bin Packing Problem with Conflicts, is of practical and theoretical interest, because of its many real-world applications and because it generalizes both the Bin Packing Problem and the Vertex Coloring Problem. We present new lower bounds, upper bounds and an exact approach, based on a Set Covering formulation solved through a Branch-and-Price algorithm. We investigate the behavior of the proposed procedures by means of extensive computational results on benchmark instances from the literature.
Algorithms for the Bin Packing Problem with Conflicts / A. E., Fernandes Muritiba; Iori, Manuel; E., Malaguti; P., Toth. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 22(2010), pp. 401-415.
Data di pubblicazione: | 2010 |
Titolo: | Algorithms for the Bin Packing Problem with Conflicts |
Autore/i: | A. E., Fernandes Muritiba; Iori, Manuel; E., Malaguti; P., Toth |
Autore/i UNIMORE: | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1287/ijoc.1090.0355 |
Rivista: | |
Volume: | 22 |
Pagina iniziale: | 401 |
Pagina finale: | 415 |
Codice identificativo ISI: | WOS:000280476300005 |
Codice identificativo Scopus: | 2-s2.0-77955505967 |
Citazione: | Algorithms for the Bin Packing Problem with Conflicts / A. E., Fernandes Muritiba; Iori, Manuel; E., Malaguti; P., Toth. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 22(2010), pp. 401-415. |
Tipologia | Articolo su rivista |
File in questo prodotto:
File | Descrizione | Tipologia | |
---|---|---|---|
1526-5528-2010-22-03-0401-2au-copy.pdf | Articolo Principale | Versione dell'editore (versione pubblicata) | Administrator Richiedi una copia |

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris