Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1138.90024
Ribeiro, Glaydston Mattos; Lorena, Luiz Antonio Nogueira
Column generation approach for the point-feature cartographic label placement problem. (English)
[J] J. Comb. Optim. 15, No. 2, 147-164 (2008). ISSN 1382-6905; ISSN 1573-2886/e

Summary: 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 is 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.

MSC 2000:: *90C27 Combinatorial programming
90C10 Integer programming

Keywords: combinatorial optimization; integer programming; column generation; map labeling

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]