Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475994 | Computers & Operations Research | 2008 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Glaydston Mattos Ribeiro, Luiz Antonio Nogueira Lorena,