A Hybrid Heuristic Based on Column Generation for Two- and Three- Stage Bin Packing Problems

Abstract

We address two two-dimensional bin packing problems where the bins are rectangular and have the same size. The items are also rectangular and all of them must be packed with the objective of minimizing the number of bins. In the first problem, the two-stage problem, the items must be packed in levels. In the second problem, the restricted 3-stage problem, items can be grouped in stacks which are packed in levels. We propose a new decomposition model where subproblems are associated with the item that initializes a bin. The decomposition is solved by a heuristic which combines (perturbed) column generation, local search, beam branch-and-price, and the use of a general purpose mixed integer programming solver. This approach is closely related with SearchCol, a framework for solving integer programming / combinatorial optimization decomposition models. Computational results with 500 instances from the literature show that the proposed hybrid heuristic is efficient in obtaining high quality solutions. It uses more 8 and 17 bins than the 7364 and 7340 bins of a compact model from the literature for the 2 and 3-stage problems, respectively, while the sum of the time spent for all instances is 35% and 58% of the time spent by the compact model.