IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v286y2020i3p839-848.html
   My bibliography  Save this article

A fresh view on the Discrete Ordered Median Problem based on partial monotonicity

Author

Listed:
  • Marín, Alfredo
  • Ponce, Diego
  • Puerto, Justo

Abstract

This paper presents new results for the Discrete Ordered Median Problem (DOMP). It exploits properties of k-sum optimization to derive specific formulations for the monotone DOMP (MDOMP), that arises when the λ weights are non-decreasing monotone, and new formulations for the general non-monotone DOMP. The main idea in our approach is to express ordered weighted averages as telescopic sums whose terms are k-sums, with positive and negative coefficients. Formulations of k-sums with positive coefficients derive from the linear programming representations obtained by Ogryczack and Tamir (2003) and Blanco, Ali, and Puerto (2014). Valid formulations for k-sums with negative coefficients are more elaborated and we present 4 different approaches, all of them based on mixed integer programming formulations. An extensive computational experience based on a collection of well-known instances shows the usefulness of the new formulations to solve difficult problems such as trimmed and anti-trimmed mean.

Suggested Citation

  • Marín, Alfredo & Ponce, Diego & Puerto, Justo, 2020. "A fresh view on the Discrete Ordered Median Problem based on partial monotonicity," European Journal of Operational Research, Elsevier, vol. 286(3), pages 839-848.
    • Handle: RePEc:eee:ejores:v:286:y:2020:i:3:p:839-848
    DOI: 10.1016/j.ejor.2020.04.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172030357X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.04.023?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. Espejo, Inmaculada & Marín, Alfredo & Rodríguez-Chía, Antonio M., 2012. "Closest assignment constraints in discrete location problems," European Journal of Operational Research, Elsevier, vol. 219(1), pages 49-58.
    2. J. Puerto & A. M. Rodríguez-Chía & A. Tamir, 2009. "Minimax Regret Single-Facility Ordered Median Location Problems on Networks," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 77-87, February.
    3. Nickel, Stefan & Velten, Sebastian, 2017. "Optimization problems with flexible objectives: A general modeling approach and applications," European Journal of Operational Research, Elsevier, vol. 258(1), pages 79-88.
    4. Justo Puerto, 2008. "A New Formulation of the Capacitated Discrete Ordered Median Problems with {0, 1}-Assignment," Operations Research Proceedings, in: Jörg Kalcsics & Stefan Nickel (ed.), Operations Research Proceedings 2007, pages 165-170, Springer.
    5. Samuel Deleplanque & Martine Labbé & Diego Ponce & Justo Puerto, 2020. "A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 582-599, July.
    6. Jörg Kalcsics & Stefan Nickel & Justo Puerto & Antonio Rodríguez-Chía, 2010. "The ordered capacitated facility location problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 203-222, July.
    7. Víctor Blanco, 2019. "Ordered p-median problems with neighbourhoods," Computational Optimization and Applications, Springer, vol. 73(2), pages 603-645, June.
    8. Alfredo Marín & Stefan Nickel & Sebastian Velten, 2010. "An extended covering model for flexible discrete and equity location problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 71(1), pages 125-163, February.
    9. Olender, Paweł & Ogryczak, Włodzimierz, 2019. "A revised Variable Neighborhood Search for the Discrete Ordered Median Problem," European Journal of Operational Research, Elsevier, vol. 274(2), pages 445-465.
    10. Sourour Elloumi & Martine Labbé & Yves Pochet, 2004. "A New Formulation and Resolution Method for the p-Center Problem," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 84-94, February.
    11. J. Puerto, 2020. "An exact completely positive programming formulation for the discrete ordered median problem: an extended version," Journal of Global Optimization, Springer, vol. 77(2), pages 341-359, June.
    12. Victor Blanco & Justo Puerto & Safae El Haj Ben Ali, 2014. "Revisiting several problems and algorithms in continuous location with $$\ell _\tau $$ ℓ τ norms," Computational Optimization and Applications, Springer, vol. 58(3), pages 563-595, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Calvino, José J. & López-Haro, Miguel & Muñoz-Ocaña, Juan M. & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "Segmentation of scanning-transmission electron microscopy images using the ordered median problem," European Journal of Operational Research, Elsevier, vol. 302(2), pages 671-687.
    2. Ljubić, Ivana & Pozo, Miguel A. & Puerto, Justo & Torrejón, Alberto, 2024. "Benders decomposition for the discrete ordered median problem," European Journal of Operational Research, Elsevier, vol. 317(3), pages 858-874.
    3. Blanco, Víctor & Gázquez, Ricardo & Ponce, Diego & Puerto, Justo, 2023. "A branch-and-price approach for the continuous multifacility monotone ordered median problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 105-126.
    4. Landete, Mercedes & Muñoz-Ocaña, Juan M. & Rodríguez-Chía, Antonio M. & Saldanha-da-Gama, Francisco, 2024. "Uncapacitated single-allocation hub median location with edge upgrading: Models and exact solution algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 187(C).
    5. Francesco Cesarone & Justo Puerto, 2024. "New approximate stochastic dominance approaches for Enhanced Indexation models," Papers 2401.12669, arXiv.org.

    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. Blanco, Víctor & Gázquez, Ricardo & Ponce, Diego & Puerto, Justo, 2023. "A branch-and-price approach for the continuous multifacility monotone ordered median problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 105-126.
    2. Ljubić, Ivana & Pozo, Miguel A. & Puerto, Justo & Torrejón, Alberto, 2024. "Benders decomposition for the discrete ordered median problem," European Journal of Operational Research, Elsevier, vol. 317(3), pages 858-874.
    3. Enrique Domínguez & Alfredo Marín, 2020. "Discrete ordered median problem with induced order," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(3), pages 793-813, October.
    4. Calvino, José J. & López-Haro, Miguel & Muñoz-Ocaña, Juan M. & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "Segmentation of scanning-transmission electron microscopy images using the ordered median problem," European Journal of Operational Research, Elsevier, vol. 302(2), pages 671-687.
    5. Víctor Blanco, 2019. "Ordered p-median problems with neighbourhoods," Computational Optimization and Applications, Springer, vol. 73(2), pages 603-645, June.
    6. Espejo, Inmaculada & Marín, Alfredo & Rodríguez-Chía, Antonio M., 2015. "Capacitated p-center problem with failure foresight," European Journal of Operational Research, Elsevier, vol. 247(1), pages 229-244.
    7. Luisa I. Martínez-Merino & Diego Ponce & Justo Puerto, 2023. "Constraint relaxation for the discrete ordered median problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(3), pages 538-561, October.
    8. Schnepper, Teresa & Klamroth, Kathrin & Stiglmayr, Michael & Puerto, Justo, 2019. "Exact algorithms for handling outliers in center location problems on networks using k-max functions," European Journal of Operational Research, Elsevier, vol. 273(2), pages 441-451.
    9. Samuel Deleplanque & Martine Labbé & Diego Ponce & Justo Puerto, 2020. "A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 582-599, July.
    10. Puerto, Justo & Pérez-Brito, Dionisio & García-González, Carlos G., 2014. "A modified variable neighborhood search for the discrete ordered median problem," European Journal of Operational Research, Elsevier, vol. 234(1), pages 61-76.
    11. Hinojosa, Yolanda & Marín, Alfredo & Puerto, Justo, 2023. "Dynamically second-preferred p-center problem," European Journal of Operational Research, Elsevier, vol. 307(1), pages 33-47.
    12. Nickel, Stefan & Velten, Sebastian, 2017. "Optimization problems with flexible objectives: A general modeling approach and applications," European Journal of Operational Research, Elsevier, vol. 258(1), pages 79-88.
    13. Marín, Alfredo, 2011. "The discrete facility location problem with balanced allocation of customers," European Journal of Operational Research, Elsevier, vol. 210(1), pages 27-38, April.
    14. Jesús Sánchez-Oro & Ana D. López-Sánchez & Anna Martínez-Gavara & Alfredo G. Hernández-Díaz & Abraham Duarte, 2021. "A Hybrid Strategic Oscillation with Path Relinking Algorithm for the Multiobjective k -Balanced Center Location Problem," Mathematics, MDPI, vol. 9(8), pages 1-21, April.
    15. Bronfman, Andrés & Marianov, Vladimir & Paredes-Belmar, Germán & Lüer-Villagra, Armin, 2015. "The maximin HAZMAT routing problem," European Journal of Operational Research, Elsevier, vol. 241(1), pages 15-27.
    16. Olender, Paweł & Ogryczak, Włodzimierz, 2019. "A revised Variable Neighborhood Search for the Discrete Ordered Median Problem," European Journal of Operational Research, Elsevier, vol. 274(2), pages 445-465.
    17. Maria Barbati & Giuseppe Bruno & Alfredo Marín, 2016. "Balancing the arrival times of users in a two-stage location problem," Annals of Operations Research, Springer, vol. 246(1), pages 273-288, November.
    18. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    19. Patricia Domínguez-Marín & Stefan Nickel & Pierre Hansen & Nenad Mladenović, 2005. "Heuristic Procedures for Solving the Discrete Ordered Median Problem," Annals of Operations Research, Springer, vol. 136(1), pages 145-173, April.
    20. Argyris, Nikolaos & Karsu, Özlem & Yavuz, Mirel, 2022. "Fair resource allocation: Using welfare-based dominance constraints," European Journal of Operational Research, Elsevier, vol. 297(2), pages 560-578.

    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:eee:ejores:v:286:y:2020:i:3:p:839-848. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.