Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
474209 | Computers & Operations Research | 2007 | 14 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Glaydston Mattos Ribeiro, Luiz Antonio Nogueira Lorena,