Column generation approach for the point-feature cartographic label placement problem

Glaydston Mattos Ribeiro () and Luiz Antonio Nogueira Lorena ()
Additional contact information
Glaydston Mattos Ribeiro: UFES—Universidade Federal do Espírito Santo, CEUNES—Centro Universitário Norte do Espírito Santo
Luiz Antonio Nogueira Lorena: INPE—Insituto Nacional de Pesquisas Espaciais, LAC—Laboratório Associado de Computação e Matemática Aplicada

Journal of Combinatorial Optimization, 2008, vol. 15, issue 2, No 2, 147-164

Abstract: Abstract This paper proposes a column generation approach for the Point-Feature Cartographic Label Placement problem (PFCLP). The column generation is based on a Lagrangean relaxation with clusters proposed for problems modeled by conflict graphs. The PFCLP can be represented by a conflict graph where vertices are positions for each label and edges are potential overlaps between labels (vertices). The conflict graph is decomposed into clusters forming a block diagonal matrix with coupling constraints that is known as a restricted master problem (RMP) in a Dantzig-Wolfe decomposition context. The clusters’ sub-problems are similar to the PFCLP and are used to generate new improved columns to RMP. This approach was tested on PFCLP instances presented in the literature providing in reasonable times better solutions than all those known and determining optimal solutions for some difficult large-scale instances.

Keywords: Combinatorial optimization; Integer programming; Column generation; Map labeling (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9073-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:15:y:2008:i:2:d:10.1007_s10878-007-9073-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9073-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().