This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Fernandes Muritiba, A. E. Articles by Toth, P.

Algorithms for the Bin Packing Problem with Conflicts

Department of Electronics, Computer Sciences and Systems, University of Bologna, 40136 Bologna, Italy
Department of Science and Methods of Engineering, University of Modena and Reggio Emilia, 42100 Reggio Emilia, Italy
Department of Electronics, Computer Sciences and Systems, University of Bologna, 40136 Bologna, Italy
Department of Electronics, Computer Sciences and Systems, University of Bologna, 40136 Bologna, Italy
albert.fernandes{at}unibo.it
manuel.iori{at}unimore.it
enrico.malaguti{at}unibo.it
paolo.toth{at}unibo.it

We consider a particular bin packing problem in which some pairs of items may be in conflict and cannot be assigned to the same bin. The problem, denoted as the bin packing problem with conflicts, is of practical and theoretical interest because of its many real-world applications and because it generalizes both the bin packing problem and the vertex coloring problem. We present new lower bounds, upper bounds, and an exact approach, based on a set covering formulation solved through a branch-and-price algorithm. We investigate the behavior of the proposed procedures by means of extensive computational results on benchmark instances from the literature.

Key words: bin packing with conflicts; vertex coloring; lower bounds; heuristics; branch and price
History: received September 2008; revised April 2009; accepted May 2009.