A new mathematical model and a Lagrangean decompos... - BV FAPESP
Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem

Full text
Author(s):
Mauri, Geraldo R. [1] ; Ribeiro, Glaydston M. [2] ; Lorena, Luiz A. N. [3]
Total Authors: 3
Affiliation:
[1] UFES, BR-29500000 Alegre, ES - Brazil
[2] UFES, BR-29933415 Sao Mateus, ES - Brazil
[3] Natl Inst Space Res INPE, BR-12210970 Sao Jose Dos Campos, SP - Brazil
Total Affiliations: 3
Document type: Journal article
Source: Computers & Operations Research; v. 37, n. 12, p. 2164-2172, DEC 2010.
Web of Science Citations: 13
Abstract

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. (C) 2010 Elsevier Ltd. All rights reserved. (AU)