IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v76y2018icp63-69.html
   My bibliography  Save this article

PROMETHEE is not quadratic: An O(qnlog(n)) algorithm

Author

Listed:
  • Calders, Toon
  • Van Assche, Dimitri

Abstract

It is generally believed that the preference ranking method PROMETHEE has a quadratic time complexity. In this paper, however, we present an exact algorithm that computes PROMETHEE’s net flow scores in time O(qnlog(n)), where q represents the number of criteria and n the number of alternatives. The method is based on first sorting the alternatives after which the unicriterion flow scores of all alternatives can be computed in one scan over the sorted list of alternatives while maintaining a sliding window. This method works with the linear and level criterion preference functions. The algorithm we present is exact and, due to the sub-quadratic time complexity, vastly extends the applicability of the PROMETHEE method. Experiments show that with the new algorithm, PROMETHEE can scale up to millions of tuples.

Suggested Citation

  • Calders, Toon & Van Assche, Dimitri, 2018. "PROMETHEE is not quadratic: An O(qnlog(n)) algorithm," Omega, Elsevier, vol. 76(C), pages 63-69.
    • Handle: RePEc:eee:jomega:v:76:y:2018:i:c:p:63-69
    DOI: 10.1016/j.omega.2017.04.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048317303729
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2017.04.003?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. JosÉ Figueira & Salvatore Greco & Matthias Ehrogott, 2005. "Multiple Criteria Decision Analysis: State of the Art Surveys," International Series in Operations Research and Management Science, Springer, number 978-0-387-23081-8, September.
    2. Bernard Roy, 2005. "Paradigms and Challenges," International Series in Operations Research & Management Science, in: Multiple Criteria Decision Analysis: State of the Art Surveys, chapter 0, pages 3-24, Springer.
    3. Beynon, Malcolm J. & Wells, Peter, 2008. "The lean improvement of the chemical emissions of motor vehicles based on preference ranking: A PROMETHEE uncertainty analysis," Omega, Elsevier, vol. 36(3), pages 384-394, June.
    4. Roy, Bernard & Vincke, Philippe, 1981. "Multicriteria analysis: survey and new directions," European Journal of Operational Research, Elsevier, vol. 8(3), pages 207-218, November.
    5. Corrente, Salvatore & Figueira, José Rui & Greco, Salvatore, 2014. "The SMAA-PROMETHEE method," European Journal of Operational Research, Elsevier, vol. 239(2), pages 514-522.
    6. Behzadian, Majid & Kazemzadeh, R.B. & Albadvi, A. & Aghdasi, M., 2010. "PROMETHEE: A comprehensive literature review on methodologies and applications," European Journal of Operational Research, Elsevier, vol. 200(1), pages 198-215, January.
    7. Govindan, Kannan & Kadziński, Miłosz & Sivakumar, R., 2017. "Application of a novel PROMETHEE-based method for construction of a group compromise ranking to prioritization of green suppliers in food supply chain," Omega, Elsevier, vol. 71(C), pages 129-145.
    8. Siskos, Jean & Wascher, Gerhard & Winkels, Heinz-Michael, 1984. "Outranking approaches versus MAUT in MCDM," European Journal of Operational Research, Elsevier, vol. 16(2), pages 270-271, May.
    9. Eppe, Stefan & De Smet, Yves, 2014. "Approximating Promethee II’s net flow scores by piecewise linear value functions," European Journal of Operational Research, Elsevier, vol. 233(3), pages 651-659.
    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. Leyva López, Juan Carlos & Solano Noriega, Jesús Jaime & Figueira, José Rui & Liu, Jun & Gastélum Chavira, Diego Alonso, 2021. "Non-dominated sorting genetic-based algorithm for exploiting a large-sized fuzzy outranking relation," European Journal of Operational Research, Elsevier, vol. 293(2), pages 615-631.
    2. Parreiras, R.O. & Kokshenev, I. & Carvalho, M.O.M. & Willer, A.C.M. & Dellezzopolles, C.F. & Nacif, D.B. & Santana, J.A., 2019. "A flexible multicriteria decision-making methodology to support the strategic management of Science, Technology and Innovation research funding programs," European Journal of Operational Research, Elsevier, vol. 272(2), pages 725-739.

    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. Govindan, Kannan & Jepsen, Martin Brandt, 2016. "ELECTRE: A comprehensive literature review on methodologies and applications," European Journal of Operational Research, Elsevier, vol. 250(1), pages 1-29.
    2. Marta Bottero & Chiara D’Alpaos & Alessandra Oppio, 2019. "Ranking of Adaptive Reuse Strategies for Abandoned Industrial Heritage in Vulnerable Contexts: A Multiple Criteria Decision Aiding Approach," Sustainability, MDPI, vol. 11(3), pages 1-18, February.
    3. de Almeida Filho, Adiel T. & Clemente, Thárcylla R.N. & Morais, Danielle Costa & de Almeida, Adiel Teixeira, 2018. "Preference modeling experiments with surrogate weighting procedures for the PROMETHEE method," European Journal of Operational Research, Elsevier, vol. 264(2), pages 453-461.
    4. Arcidiacono, Sally Giuseppe & Corrente, Salvatore & Greco, Salvatore, 2018. "GAIA-SMAA-PROMETHEE for a hierarchy of interacting criteria," European Journal of Operational Research, Elsevier, vol. 270(2), pages 606-624.
    5. Eppe, Stefan & De Smet, Yves, 2014. "Approximating Promethee II’s net flow scores by piecewise linear value functions," European Journal of Operational Research, Elsevier, vol. 233(3), pages 651-659.
    6. Kadziński, MiŁosz & Greco, Salvatore & SŁowiński, Roman, 2012. "Extreme ranking analysis in robust ordinal regression," Omega, Elsevier, vol. 40(4), pages 488-501.
    7. Miller, Michael & Mattes, Katharina, 2014. "Demonstration of a multi-criteria based decision support framework for selecting PSS to increase resource efficiency," Working Papers "Sustainability and Innovation" S11/2014, Fraunhofer Institute for Systems and Innovation Research (ISI).
    8. Pelissari, Renata & Oliveira, Maria Célia & Ben Amor, Sarah & Abackerli, Alvaro José, 2019. "A new FlowSort-based method to deal with information imperfections in sorting decision-making problems," European Journal of Operational Research, Elsevier, vol. 276(1), pages 235-246.
    9. Emilios Galariotis & Christophe Germain & Constantin Zopounidis, 2018. "A combined methodology for the concurrent evaluation of the business, financial and sports performance of football clubs: the case of France," Annals of Operations Research, Springer, vol. 266(1), pages 589-612, July.
    10. Tsuen-Ho Hsu & Ling-Zhong Lin, 2014. "Using Fuzzy Preference Method for Group Package Tour Based on the Risk Perception," Group Decision and Negotiation, Springer, vol. 23(2), pages 299-323, March.
    11. Shmelev, Stanislav E. & Rodríguez-Labajos, Beatriz, 2009. "Dynamic multidimensional assessment of sustainability at the macro level: The case of Austria," Ecological Economics, Elsevier, vol. 68(10), pages 2560-2573, August.
    12. Marina Segura & Concepción Maroto & Baldomero Segura, 2019. "Quantifying the Sustainability of Products and Suppliers in Food Distribution Companies," Sustainability, MDPI, vol. 11(21), pages 1-18, October.
    13. Fancello, Giovanna & Tsoukiàs, Alexis, 2021. "Learning urban capabilities from behaviours. A focus on visitors values for urban planning," Socio-Economic Planning Sciences, Elsevier, vol. 76(C).
    14. Corrente, Salvatore & Figueira, José Rui & Greco, Salvatore, 2014. "The SMAA-PROMETHEE method," European Journal of Operational Research, Elsevier, vol. 239(2), pages 514-522.
    15. Roszkowska, Ewa & Wachowicz, Tomasz, 2015. "Application of fuzzy TOPSIS to scoring the negotiation offers in ill-structured negotiation problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 920-932.
    16. Ute Weißfloch & Jutta Geldermann, 2016. "Assessment of product-service systems for increasing the energy efficiency of compressed air systems," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 10(3), pages 341-366.
    17. Roy, Bernard & Slowinski, Roman, 2008. "Handling effects of reinforced preference and counter-veto in credibility of outranking," European Journal of Operational Research, Elsevier, vol. 188(1), pages 185-190, July.
    18. Merad, Myriam & Dechy, Nicolas & Serir, Lisa & Grabisch, Michel & Marcel, Frédéric, 2013. "Using a multi-criteria decision aid methodology to implement sustainable development principles within an organization," European Journal of Operational Research, Elsevier, vol. 224(3), pages 603-613.
    19. Aikaterini Papapostolou & Charikleia Karakosta & Kalliopi-Anastasia Kourti & Haris Doukas & John Psarras, 2019. "Supporting Europe’s Energy Policy Towards a Decarbonised Energy System: A Comparative Assessment," Sustainability, MDPI, vol. 11(15), pages 1-26, July.
    20. Doumpos, Michael & Zopounidis, Constantin, 2011. "Preference disaggregation and statistical learning for multicriteria decision support: A review," European Journal of Operational Research, Elsevier, vol. 209(3), pages 203-214, March.

    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:jomega:v:76:y:2018:i:c:p:63-69. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.