Hybridizing population heuristics and column generation for the Bin Packing Problem with
Conflicts

Albert E. Fernandes Muritiba 1, Manuel Iori 2, Enrico Malaguti 1 and
Paolo Toth 1

1 DEIS, University of Bologna, 40136 Bologna, Italy

2 DISMI, University of Modena and Reggio Emilia, 42100 Reggio Emilia, Italy

Abstract. We address a particular Bin Packing Problem in which some
couples of items may be incompatible and cannot be assigned to the same
bin. The problem is denoted as the Bin Packing Problem with Conflicts.
It is of practical and theoretical interest, because of its many real-world
applications and because it generalizes well-known combinatorial prob-
lems, such as the Bin Packing Problem and the Vertex Coloring Problem.
We first present a population metaheuristic, in which a Tabu Search tech-
nique is nested into a genetic diversification operator. We then propose a
classical set covering formulation, solved by column generation. We show
how the columns found by the heuristics may consistently improve the
column generation behavior, leading to results that largely outperforms
the state of the art of the literature on the problem.