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:3(2010), pp. 401-415. [10.1287/ijoc.1090.0355]

Algorithms for the Bin Packing Problem with Conflicts

IORI, MANUEL;
2010

Abstract

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.
22
3
401
415
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:3(2010), pp. 401-415. [10.1287/ijoc.1090.0355]
A. E., Fernandes Muritiba; Iori, Manuel; E., Malaguti; P., Toth
File in questo prodotto:
File Dimensione Formato  
1526-5528-2010-22-03-0401-2au-copy.pdf

non disponibili

Descrizione: Articolo Principale
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 294.34 kB
Formato Adobe PDF
294.34 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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/618396
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 72
  • ???jsp.display-item.citation.isi??? 50
social impact