Article ID: | iaor20106138 |
Volume: | 179 |
Issue: | 1 |
Start Page Number: | 221 |
End Page Number: | 241 |
Publication Date: | Sep 2010 |
Journal: | Annals of Operations Research |
Authors: | Righini Giovanni, Ceselli Alberto, Bettinelli Andrea |
Keywords: | packing, branch and price |
In this paper we consider a variation of the bin packing problem in which bins of different types have different costs and capacities. Furthermore, each bin has to be filled at least to a certain level, which depends on its type. We present a set partitioning formulation and an exact optimization algorithm which exploits column generation and specialized heuristics. We compare our algorithm with the general purpose solver ILOG CPLEX, running on two compact ILP formulations and we report on experimental results on instances we have generated from data-sets for the variable size bin packing problem.