In this paper, we consider a recently introduced packing problem in which a given set of weighted items with colors has to be packed into a set of identical bins, while respecting capacity constraints and minimizing the total number of times that colors appear in the bins.
We review exact methods from the literature and present a fast lower bounding procedure that, in some cases, can also provide an optimal solution.
We theoretically study the worst-case performance of the lower bound and computationally test our solution method on a large benchmark of instances from the literature: quite surprisingly, all of them are optimally solved by our procedure in a few seconds, including those for which the optimal solution value was still unknown. Thus, we introduce additional harder instances, which are used to evaluate the performance of a constructive heuristic method and of a tabu search algorithm. Results on the new instances show that the tabu search produces considerable improvements over the heuristic solution, with a limited computational effort.