%0 Journal Article
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3ESGTTP
%@archivingpolicy denypublisher denyfinaldraft6
%@resumeid
%@resumeid
%@resumeid 8JMKD3MGP5W/3C9JHMQ
%@issn 0028-0836
%X This paper proposes a 0-1 integer linear programming model for the point-feature cartographic label placement problem based on labeling of the largest number of free labels. In addition, one non-trivial valid inequality is presented to strengthen this proposed model. Even with the strengthened model, a commercial solver was not able to solve a representative sample of known instances presented in the literature. Thus, we also present a Lagrangean decomposition technique based on graph partitioning. Our added approaches established optimal solutions for practically all the used instances and the results significantly improved the ones presented in recent studies concerning the problem.
%@mirrorrepository sid.inpe.br/mtc-m19@80/2009/08.21.17.02.53
%8 Dec.
%N 12
%T A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem
%@secondarytype PRE PI
%K Combinatorial optimization, Label placement, Lagrangean decomposition.
%@usergroup administrator
%@usergroup banon
%@usergroup simone
%@group LAC-CTE-INPE-MCT-BR
%3 a new mathematical.pdf
%@secondarykey INPE--PRE/
%2 sid.inpe.br/mtc-m19@80/2010/06.01.17.33.55
%@affiliation Universidade Federal do Espírito Santo
%@affiliation Universidade Federal do Espírito Santo
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%B Nature
%P 2164-2172
%4 sid.inpe.br/mtc-m19@80/2010/06.01.17.33
%D 2010
%V 37
%@doi 10.1016/j.cor.2010.03.005
%A Mauri, Geraldo R.,
%A Ribeiro, Glaydston M.,
%A Lorena, Luiz Antonio Nogueira,
%@dissemination WEBSCI; PORTALCAPES.
%@area COMP