Efficient Lower Bounds for Packing Problems in Heterogeneous Bins with Conflicts Constraint

International audienceIn this paper we discuss a version of the classical one dimensional bin-packing problem, where the objective is to minimize the total cost of heterogeneous bins needed to store given items, each with some space requirements. In this version, some of the items are incompatible with each other, and cannot be packed together. This problem with various real world applications generalizes both the Variable Sized Bin Packing Problem and the Vertex Coloring Problem. We propose two lower bounds for this problem based on both the relaxation of the integrity constraints and the computation of the large clique in the conflicts graph.\n\