Lagrangean relaxation with clusters for point-feature cartographic label placement problems

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 gr...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2008-07, Vol.35 (7), p.2129-2140
Main Authors: Ribeiro, Glaydston Mattos, Lorena, Luiz Antonio Nogueira
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Exact sciences and technology
Graphs
Hierarchies
Integer programming
Label placement
Lagrange multiplier
Lagrangean relaxation
Mathematical problems
Operational research. Management science
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2006.09.024