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 with Conflicts
Tiziano Bacci;Sara Nicoloso
2018
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:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
