Paper Info
Title
Column generation approach for the point-feature cartographic label placement problem
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.
Year
DOI
Venue
2008
10.1007/s10878-007-9073-5
J. Comb. Optim.
Keywords
Field
DocType
Combinatorial optimization,Integer programming,Column generation,Map labeling
Graph theory,Mathematical optimization,Column generation,Combinatorics,Vertex (geometry),Combinatorial optimization,Integer programming,Diagonal matrix,Cartography,Mathematics,Block matrix,Constrained optimization
Journal
Volume
Issue
ISSN
15
2
1382-6905
Citations 
PageRank 
References 
6
0.50
16
Authors
2
Name
Order
Citations
PageRank
Glaydston Mattos Ribeiro120213.79
Luiz Antonio Nogueira Lorena249836.72