A special case of Variable-Sized Bin Packing Problem with Color Constraints

The Variable-Sized Bin Packing Problem with Color Constraints (VSBPP-CC) is a generalization of the classical one-dimensional Bin Packing Problem, where bins of different capacities are available for packing a set of items each characterized by a weight and a color. The objective is to pack all the items while minimizing the total residual capacity, and such that each bin contains at most two different colors. In this paper we consider a special case of VSBPP-CC where each color is assigned to only one item. We first describe the problem, its practical context and survey related works. We then propose several original mathematical formulations for the problem. Preliminary computational results show the efficiency of our formulations, mainly the so-called matching formulation, in solving CSPLIB-based instances.