Lagrangean relaxation bounds for point-feature cartographic label placement problem



Document title: Lagrangean relaxation bounds for point-feature cartographic label placement problem
Journal: Pesquisa operacional
Database: PERIÓDICA
System number: 000313128
ISSN: 0101-7438
Authors: 1
1
Institutions: 1Instituto Nacional de Pesquisas Espaciais, Laboratorio de Computacao e Matematica Aplicada, Sao Jose dos Campos, Sao Paulo. Brasil
Year:
Season: Sep-Dic
Volumen: 26
Number: 3
Pages: 459-471
Country: Brasil
Language: Inglés
Document type: Artículo
Approach: Analítico, descriptivo
English abstract The objective of the point-feature cartographic label placement problem (PFCLP) is to give more legibility to an automatic map creation, placing point labels in clear positions. Many researchers consider distinct approaches for PFCLP, such as to obtain the maximum number of labeled points that can be placed without overlapping or to obtain the maximum number of labeled points without overlaps considering that all points must be labeled. This paper considers another variant of the problem in which one has to minimize the number of overlaps while all points are labeled in the map. A conflict graph is initially defined and a mathematical formulation of binary integer linear programming is presented. Commercial optimization packages could not solve large instances exactly using this formulation over instances proposed in the literature. A heuristic is then examined considering a Lagrangean relaxation performed after an initial partition of the conflict graph into clusters. This decomposition allowed us to introduce tight lower and upper bounds for PFCLP
Portuguese abstract O Problema Rotulação Cartográfica de Pontos (PRCP) tem como objetivo dar maior legibilidade a um mapa, colocando os rótulos dos pontos em posições legíveis. Existem abordagens distintas para o PRCP direcionadas a obter o máximo número de pontos rotulados que podem ser colocados sem sobreposição ou ainda obter o máximo número de pontos rotulados sem sobreposição considerando que todos os pontos devem ser rotulados. Esse artigo aborda o problema de uma outra forma, minimizando o número de sobreposições existentes em uma rotulação de todos os pontos. Um grafo de conflitos é definido inicialmente e uma formulação matemática de programação linear inteira binária é apresentada. Instâncias de grande porte propostas na literatura não puderam ser resolvidas por um software comercial de otimização, com isso, uma heurística é examinada considerando uma relaxação Lagrangeana feita após um particionamento inicial do grafo de conflitos em clusters. Essa decomposição permitiu obter bons limitantes inferiores e superiores para o PRCP
Disciplines: Matemáticas,
Geografía
Keyword: Matemáticas aplicadas,
Cartografía,
Rotulación de puntos,
Relajación lagrangiana,
Modelos matemáticos,
Programación lineal
Keyword: Mathematics,
Geography,
Applied mathematics,
Cartography,
Label placement,
Mathematical models,
Lagrangian relaxation,
Linear programming
Full text: Texto completo (Ver HTML)