Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem

We consider in this paper a new Lagrangean relaxation with clusters for the Manufacturer's Pallet Loading Problem (MPLP). The relaxation is based on the MPLP formulated as a Maximum Independent Set Problem (MISP) and represented in a conflict graph that can be partitioned in clusters. The edges inter clusters are relaxed in a Lagrangean fashion. Computational tests attain the optimality for some instances considered difficult for a Lagrangean relaxation. Our results show that this relaxation can be a successful approach for hard combinatorial problems modeled in conflict graphs. Moreover, we propose a column generation approach for the MPLP derived from the idea behind the Lagrangean relaxation proposed.