%0 Journal Article
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@tertiarymark Trabalho Vinculado à Tese/Dissertação
%@nexthigherunit 8JMKD3MGPCW/3ESGTTP
%@resumeid
%@resumeid 8JMKD3MGP5W/3C9JHMQ
%@archivingpolicy denypublisher denyfinaldraft36
%@usergroup administrator
%@usergroup simone
%3 lagrangean relaxation.pdf
%X This paper presents two new mathematical formulations for the point-feature cartographic label placement problem (PFCLP) and a new Lagrangean relaxation with clusters (LagClus) to provide bounds to these formulations. The PFCLP can be represented by a conflict graph and the relaxation divides the graph in small subproblems (clusters) that are easily solved. The edges connecting clusters are relaxed in a Lagrangean way and a subgradient algorithm improves the bounds. The LagClus was successfully applied to a set of instances up to 1000 points providing the best results of those reported in the literature.
%8 July
%N 7
%T Lagrangean relaxation with clusters for point-feature cartographic label placement problems
%@secondarytype PRE PI
%K Lagrangean relaxation, Integer programming, Label placement.
%@visibility shown
%@group LAC-CTE-INPE-MCT-BR
%@group LAC-CTE-INPE-MCT-BR
%@secondarykey INPE--PRE/
%@issn 0305-0548
%2 sid.inpe.br/mtc-m17@80/2006/12.01.18.12.42
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%B Computers and Operations Research
%P 2129-140
%4 sid.inpe.br/mtc-m17@80/2006/12.01.18.12
%D 2008
%V 35
%@doi 10.1016/j.cor.2006.09.024
%A Ribeiro, Glaydston Mattos,
%A Lorena, Luiz Antonio Nogueira,
%@dissemination WEBSCI; PORTALCAPES.
%@area COMP