Many authors, mainly in the context of the Bin Packing Problem with Conflicts, used the random graph generator proposed in “Heuristics and lower bounds for the bin packing problem with conflicts” [M. Gendreau, G. Laporte, and F. Semet, Computers & Operations Research, 31:347–358, 2004]. In this paper we show that the graphs generated in this way are not arbitrary but threshold ones. Computational results show that instances of the Bin Packing Problem with Conflicts on threshold graphs are easier to solve w.r.t. instances on arbitrary graphs.
On the Benchmark Instances for the Bin Packing Problem with Conflicts
Bacci, Tiziano;Nicoloso, Sara
2021
Abstract
Many authors, mainly in the context of the Bin Packing Problem with Conflicts, used the random graph generator proposed in “Heuristics and lower bounds for the bin packing problem with conflicts” [M. Gendreau, G. Laporte, and F. Semet, Computers & Operations Research, 31:347–358, 2004]. In this paper we show that the graphs generated in this way are not arbitrary but threshold ones. Computational results show that instances of the Bin Packing Problem with Conflicts on threshold graphs are easier to solve w.r.t. instances on arbitrary graphs.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
6.pdf
solo utenti autorizzati
Descrizione: On the Benchmark Instances for the Bin Packing Problem with Conflicts
Tipologia:
Versione Editoriale (PDF)
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
251.58 kB
Formato
Adobe PDF
|
251.58 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
