| Abstract | In this paper we study the Variable Size Bin Packing Problem (VSBPP) which is a generalization of the Bin Packing Problem where bins of different capacities (and different costs) are available for packing a set of items. The objective is to pack all the items minimizing the total cost associated with the bins. We discuss applications of the VSBPP and propose and discuss one generic (non-linear integer programming) formulation as well as two linear integer programming formulations. One of these formulations overcomes the non-linearity of the original model by simply adding explicitly the class of the bin used. The other, less straightforward, uses a so-called discretized model reformulation technique already proposed for other problems (see Gouveia (1995) and Gouveia and Saldanha da Gama (2006)), and shows that we need not use explicitly the information of the type of bin used provided we know the amount packed in it. These two models are, then, compared in terms of the linear relaxation bounds. New valid inequalities suggested by the decision variables of the discretized models are also proposed to strengthen the original linear relaxation bounds. Computational results are presented showing that the valid inequalities proposed not only enhance the linear programming relaxation bound but may also be extremely helpful when using a commercial package for solving the VSBPP to optimality. |
