On the Benchmark Instances for the Bin Packing Problem with Conflicts

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.