Column generation approach for the point-feature cartographic label placement problem. (English) Zbl 1138.90024

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.


90C27 Combinatorial optimization
90C10 Integer programming


Full Text: DOI Link


[1] Christensen J, Marks J, Shieber S (1994) Placing text labels on maps and diagrams. In: Heckbert P (ed) Graphics gems IV. Academic, New York, pp 497–504
[2] Christensen J, Marks J, Shieber S (1995) An empirical study of algorithms for point-feature label placement. ACM Trans Graph 14(3):203–232
[3] Côrrea FA, Lorena LAN, Senne ELF (2006) Lagrangean relaxation with clusters for the uncapacitated facility location problem. In: XIII CLAIO–congreso latino–iberoamericano de investigación operativa, Uruguay, Motevideo
[4] Desrosiers J, Lübbecke ME (2005) A primer in column generation. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation (GERAD 25th anniversary series). Springer, New York, pp 1–32 · Zbl 1246.90093
[5] Doddi S, Marathe MV, Mirzaian A, Moret BME, Zhu B (1998) Map labeling and its generalizations. In: Proceedings of the 8th ACM-SIAM symposium on discrete algorithms (SODA’97), pp 148–157 · Zbl 1321.68435
[6] Formann M, Wagner F (1991) A packing problem with applications to lettering of maps. In: Proceedings of the seventh annual ACM symposium on computational geometry. New Hampshire, pp 281–288
[7] Hirsch SA (1982) An algorithm for automatic name placement around point data. Am Cartogr 9(1):5–17
[8] ILOG (2006) CPLEX 10, Reference Manual. Mountain View, CA
[9] Karypis G, Kumar V (1998) Multilevel k-way partitioning scheme for irregular graphs. J Parallel Distributed Comput 48(1):96–129 · Zbl 0918.68073
[10] Klau GW, Mutzel P (2000) Optimal labeling of point features in the slider model. In: Du DZ, Eades P, Estivill-Castro V, Lin X, Sharma A (eds) Proceedings of the 6th annual international computing and combinatorics conference (COCOON’00). Lecture notes in computer science, vol 1858. Springer, Berlin, pp 340–350
[11] Klau GW, Mutzel P (2003) Optimal labeling of point features in rectangular labeling models. Math Program Ser B 94:435–458 · Zbl 1030.90129
[12] Lorena LAN, Furtado JC (2001) Constructive genetic algorithm for clustering problems. Evol Computat 9(3):309–327 · Zbl 05412747
[13] Marks J, Shieber S (1991) The computational complexity of cartographic label placement. Technical Report TR-05-91, Advanced Research in Computing Technology, Harvard University
[14] Moon ID, Chaudhry S (1984) An analysis of network location problems with distance constraints. Manag Sci 30:290–307 · Zbl 0553.90034
[15] Murray AT, Church RL (1996) Solving the anti-covering location problem using Lagrangian relaxation. Comput Oper Res 24(2):127–140 · Zbl 0890.90124
[16] Ribeiro GM, Lorena LAN (2006a) Lagrangean relaxation with clusters for point-feature cartographic label placement problems. Comput Oper Res. doi: 10.1016/j.cor.2006.09.024
[17] Ribeiro GM, Lorena LAN (2006b) Heuristics for cartographic label placement problems. Comput Geosci 32(6):739–748
[18] Ribeiro GM, Lorena LAN (2007a) Optimizing the woodpulp stowage using Lagrangean relaxation with clusters. J Oper Res Soc advance online publication, February 14, 2007. doi: 10.1057/palgrave.jors.2602367 · Zbl 1153.90328
[19] Ribeiro GM, Lorena LAN (2007b) Lagrangean relaxation with clusters and column generation for the manufacturer’s pallet loading problem. Comput Oper Res 34:2695–2708 · Zbl 1141.90514
[20] Schreyer M, Raidl GR (2002) Letting ants labeling point features. In: Proceedings of the 2002 IEEE congress on evolutionary computation at the IEEE world congress on computational intelligence, pp 1564–1569
[21] Strijk T, Verweij B, Aardal K (2000) Algorithms for maximum independent set applied to map labeling. Available at ftp://ftp.cs.uu.nl/pub/RUU/CStechreps/CS-2000/2000-22.ps.gz
[22] van Kreveld M, Strijk T, Wolff A (1998) Point set labeling with sliding labels. In: Proceedings of the 14th annual ACM symposium on computational geometry (SoCG’98), pp 337–346 · Zbl 0930.68153
[23] Verner OV, Wainwright RL, Schoenefeld DA (1997) Placing text labels on maps and diagrams using genetic algorithms with masking. INFORMS J Comput 9:266–275 · Zbl 0893.90181
[24] Wagner F, Wolff A, Kapoor V, Strijk T (2001) Three rules suffice for good label placement. Algorithmica 30:334–349 · Zbl 0984.65015
[25] Wolff A (1999) Automated label placement in theory and practice. PhD thesis, Fachbereich Mathematik und Informatik, Freie Universität Berlin
[26] Wolff A, Strijk T (2006) The map labeling bibliography. http://i11www.ilkd.uni-karlsruhe.de/\(\sim\)awolff/map-labeling/bibliography/ . Cited 10 July 2003 · Zbl 1074.68653
[27] Yamamoto M, Lorena LAN (2005) A constructive genetic approach to point-feature cartographic label placement. In: Ibaraki T, Nonobe K, Yagiura M (eds) Metaheuristics: progress as real problem solvers. Kluwer Academic, Dordrecht, pp 285–300
[28] Yamamoto M, Câmara G, Lorena LAN (2002) Tabu search heuristic for point-feature cartographic label placement. Geoinf Int J Adv Comput Sci Geogr Inf Syst 6(1):77–90 · Zbl 1034.68702
[29] Zoraster S (1986) Integer programming applied to the map label placement problem. Cartographica 23(3):16–27
[30] Zoraster S (1990) The solution of large 0–1 integer programming problems encountered in automated cartography. Oper Res 38(5):752–759
[31] Zoraster S (1991) Expert systems and the map label placement problem. Cartographica 28(1):1–9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.