%0 Journal Article
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3ESGTTP
%@resumeid
%@resumeid 8JMKD3MGP5W/3C9JHMQ
%@archivingpolicy denypublisher denyfinaldraft12
%@usergroup administrator
%@usergroup rosemary
%@usergroup simone
%3 glaydston-lorena-jco.pdf
%X This paper proposes a column generation approach for the Point-Feature Cartographic Label Placement problem (PFCLP). The column generation is based on a Lagrangean relaxation with clusters proposed for problems modeled by conflict graphs. The PFCLP can be represented by a conflict graph where vertices are positions for each label and edges are potential overlaps between labels (vertices). The conflict graph is decomposed into clusters forming a block diagonal matrix with coupling constraints that is known as a restricted master problem (RMP) in a Dantzig-Wolfe decomposition context. The clusters sub-problems are similar to the PFCLP and are used to generate new improved columns to RMP. This approach was tested on PFCLP instances presented in the literature providing in reasonable times better solutions than all those known and determining optimal solutions for some difficult large-scale instances.
%8 Feb.
%N 2
%T Column Generation Approach for the Point-feature Cartographic Label Placement Problem
%@secondarytype PRE PI
%K Combinatorial optimization, Integer programming, Column generation, Map labeling, COMPUTAÇÂO APLICADA.
%@visibility shown
%@group
%@group LAC-CTE-INPE-MCT-BR
%@secondarykey INPE--PRE/
%@issn 1382-6905
%2 sid.inpe.br/mtc-m17@80/2007/06.04.19.22.30
%@affiliation
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%B Journal of Combinatorial Optimization
%P 147-164
%4 sid.inpe.br/mtc-m17@80/2007/06.04.19.22
%D 2008
%V 15
%@doi 10.1007/s10878-007-9073-5
%A Ribeiro, G. M.,
%A Lorena, Luiz Antonio Nogueira,
%@dissemination WEBSCI; PORTALCAPES.
%@area COMP