Paper Info
Title
Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem
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.
Year
DOI
Venue
2007
10.1016/j.cor.2005.10.008
Computers & OR
Keywords
DocType
Volume
Maximum Independent Set Problem,conflict graph,column generation approach,lagrangean fashion,Lagrangean relaxation,Pallet Loading Problem,computational test,lagrangean relaxation,pallet loading problem,successful approach,new lagrangean relaxation,edges inter cluster
Journal
34
Issue
ISSN
Citations 
9
Computers and Operations Research
9
PageRank 
References 
Authors
0.65
19
2
Name
Order
Citations
PageRank
Glaydston Mattos Ribeiro120213.79
Luiz Antonio Nogueira Lorena249836.72