  We propose an iterated local search based on several classes of local and
large neighborhoods for the bin packing problem with conflicts. This problem,
which combines the characteristics of both bin packing and vertex coloring,
arises in various application contexts such as logistics and transportation,
timetabling, and resource allocation for cloud computing. We introduce $O(1)$
evaluation procedures for classical local-search moves, polynomial variants of
ejection chains and assignment neighborhoods, an adaptive set covering-based
neighborhood, and finally a controlled use of 0-cost moves to further diversify
the search. The overall method produces solutions of good quality on the
classical benchmark instances and scales very well with an increase of problem
size. Extensive computational experiments are conducted to measure the
respective contribution of each proposed neighborhood. In particular, the
0-cost moves and the large neighborhood based on set covering contribute very
significantly to the search. Several research perspectives are open in relation
to possible hybridizations with other state-of-the-art mathematical programming
heuristics for this problem.
