IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v15y2008i2d10.1007_s10878-007-9073-5.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Glaydston Mattos Ribeiro & Luiz Antonio Nogueira Lorena, 2008. "Column generation approach for the point-feature cartographic label placement problem," Journal of Combinatorial Optimization, Springer, vol. 15(2), pages 147-164, February.
    • Handle: RePEc:spr:jcomop:v:15:y:2008:i:2:d:10.1007_s10878-007-9073-5
    DOI: 10.1007/s10878-007-9073-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-007-9073-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-007-9073-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Oleg V. Verner & Roger L. Wainwright & Dale A. Schoenefeld, 1997. "Placing Text Labels on Maps and Diagrams using Genetic Algorithms with Masking," INFORMS Journal on Computing, INFORMS, vol. 9(3), pages 266-275, August.
    2. I. Douglas Moon & Sohail S. Chaudhry, 1984. "An Analysis of Network Location Problems with Distance Constraints," Management Science, INFORMS, vol. 30(3), pages 290-307, March.
    3. Steven Zoraster, 1990. "The Solution of Large 0–1 Integer Programming Problems Encountered in Automated Cartography," Operations Research, INFORMS, vol. 38(5), pages 752-759, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Alvim, Adriana C.F. & Taillard, Éric D., 2009. "POPMUSIC for the point feature label placement problem," European Journal of Operational Research, Elsevier, vol. 192(2), pages 396-413, January.
    2. Rabello, Rômulo Louzada & Mauri, Geraldo Regis & Ribeiro, Glaydston Mattos & Lorena, Luiz Antonio Nogueira, 2014. "A Clustering Search metaheuristic for the Point-Feature Cartographic Label Placement Problem," European Journal of Operational Research, Elsevier, vol. 234(3), pages 802-808.
    3. Alan T. Murray & Ran Wei & Richard L. Church & Matthew R. Niblett, 2019. "Addressing risks and uncertainty in forest land use modeling," Journal of Geographical Systems, Springer, vol. 21(3), pages 319-338, September.
    4. E Erkut & R L Francis & T J Lowe, 1988. "A Multimedian Problem with Interdistance Constraints," Environment and Planning B, , vol. 15(2), pages 181-190, June.
    5. Averbakh, Igor & Berman, Oded, 1996. "Locating flow-capturing units on a network with multi-counting and diminishing returns to scale," European Journal of Operational Research, Elsevier, vol. 91(3), pages 495-506, June.
    6. Yaw Asiedu & Mark Rempel, 2011. "A multiobjective coverage‐based model for Civilian search and rescue," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(3), pages 167-179, April.
    7. Alan T Murray & Ran Wei & Tony H Grubesic, 2014. "An Approach for Examining Alternatives Attributable to Locational Uncertainty," Environment and Planning B, , vol. 41(1), pages 93-109, February.
    8. Pablo Adasme & Ali Dehghan Firoozabadi, 2019. "Facility Location with Tree Topology and Radial Distance Constraints," Complexity, Hindawi, vol. 2019, pages 1-29, November.
    9. Ricca, Federica & Scozzari, Andrea, 2024. "Portfolio optimization through a network approach: Network assortative mixing and portfolio diversification," European Journal of Operational Research, Elsevier, vol. 312(2), pages 700-717.
    10. ReVelle, C. S. & Eiselt, H. A., 2005. "Location analysis: A synthesis and survey," European Journal of Operational Research, Elsevier, vol. 165(1), pages 1-19, August.
    11. Erkut, E. & ReVelle, C. & Ulkusal, Y., 1996. "Integer-friendly formulations for the r-separation problem," European Journal of Operational Research, Elsevier, vol. 92(2), pages 342-351, July.
    12. Prokopyev, Oleg A. & Kong, Nan & Martinez-Torres, Dayna L., 2009. "The equitable dispersion problem," European Journal of Operational Research, Elsevier, vol. 197(1), pages 59-67, August.
    13. Welch, S. B. & Salhi, S., 1997. "The obnoxious p facility network location problem with facility interaction," European Journal of Operational Research, Elsevier, vol. 102(2), pages 302-319, October.
    14. Downs, Joni A. & Gates, Robert J. & Murray, Alan T., 2008. "Estimating carrying capacity for sandhill cranes using habitat suitability and spatial optimization models," Ecological Modelling, Elsevier, vol. 214(2), pages 284-292.
    15. Brian J. Lunday & J. Cole Smith & Jeffrey B. Goldberg, 2005. "Algorithms for solving the conditional covering problem on paths," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 293-301, June.
    16. Heewon Chea & Hyun Kim & Shih-Lung Shaw & Yongwan Chun, 2022. "Assessing Trauma Center Accessibility for Healthcare Equity Using an Anti-Covering Approach," IJERPH, MDPI, vol. 19(3), pages 1-21, January.
    17. Yang, Lin & Zhang, Fayong & Kwan, Mei-Po & Wang, Ke & Zuo, Zejun & Xia, Shaotian & Zhang, Zhiyong & Zhao, Xinpei, 2020. "Space-time demand cube for spatial-temporal coverage optimization model of shared bicycle system: A study using big bike GPS data," Journal of Transport Geography, Elsevier, vol. 88(C).
    18. Murray, Alan T. & Church, Richard L., 1997. "Facets for node packing," European Journal of Operational Research, Elsevier, vol. 101(3), pages 598-608, September.
    19. Martí, Rafael & Martínez-Gavara, Anna & Pérez-Peló, Sergio & Sánchez-Oro, Jesús, 2022. "A review on discrete diversity and dispersion maximization from an OR perspective," European Journal of Operational Research, Elsevier, vol. 299(3), pages 795-813.
    20. Lei, Ting L. & Church, Richard L., 2015. "On the unified dispersion problem: Efficient formulations and exact algorithms," European Journal of Operational Research, Elsevier, vol. 241(3), pages 622-630.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:15:y:2008:i:2:d:10.1007_s10878-007-9073-5. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.