IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i2p308-326.html
   My bibliography  Save this article

Heuristic Search for Rank Aggregation with Application to Label Ranking

Author

Listed:
  • Yangming Zhou

    (Sino-US Global Logistics Institute, Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China; Data-Driven Management Decision Making Lab, Shanghai Jiao Tong University, Shanghai 200030, China)

  • Jin-Kao Hao

    (Department of Computer Science, Université d’Angers, Angers 49045, France)

  • Zhen Li

    (Tencent Technology (Shanghai) Company Limited, Shanghai 200233, China)

Abstract

Rank aggregation combines the preference rankings of multiple alternatives from different voters into a single consensus ranking, providing a useful model for a variety of practical applications but posing a computationally challenging problem. In this paper, we provide an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and an enhanced late acceptance local search method reinforced by a relaxed acceptance and replacement strategy and a fast incremental evaluation mechanism. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on both synthetic and real-world benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, a well-established machine learning task. We additionally analyze several key algorithmic components to gain insight into their operation.

Suggested Citation

  • Yangming Zhou & Jin-Kao Hao & Zhen Li, 2024. "Heuristic Search for Rank Aggregation with Application to Label Ranking," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 308-326, March.
    • Handle: RePEc:inm:orijoc:v:36:y:2024:i:2:p:308-326
    DOI: 10.1287/ijoc.2022.0019
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0019
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.0019?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
    ---><---

    References listed on IDEAS

    as
    1. Sahand Negahban & Sewoong Oh & Devavrat Shah, 2017. "Rank Centrality: Ranking from Pairwise Comparisons," Operations Research, INFORMS, vol. 65(1), pages 266-287, February.
    2. Zan Huang & Daniel Dajun Zeng, 2011. "Why Does Collaborative Filtering Work? Transaction-Based Recommendation Model Validation and Selection by Analyzing Bipartite Random Graphs," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 138-152, February.
    3. Gediminas Adomavicius & Jingjing Zhang, 2016. "Classification, Ranking, and Top-K Stability of Recommendation Algorithms," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 129-147, February.
    4. Zhang-Hua Fu & Jin-Kao Hao, 2015. "Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 221-237, May.
    5. Aledo, Juan A. & Gámez, Jose A. & Molina, David, 2016. "Using extension sets to aggregate partial rankings in a flexible setting," Applied Mathematics and Computation, Elsevier, vol. 290(C), pages 208-223.
    6. Sahand Negahban & Sewoong Oh & Devavrat Shah, 2017. "Rank Centrality: Ranking from Pairwise Comparisons," Operations Research, INFORMS, vol. 65(1), pages 266-287, February.
    7. Ali, Alnur & Meilă, Marina, 2012. "Experiments with Kemeny ranking: What works when?," Mathematical Social Sciences, Elsevier, vol. 64(1), pages 28-40.
    8. Yeawon Yoo & Adolfo R. Escobedo, 2021. "A New Binary Programming Formulation and Social Choice Property for Kemeny Rank Aggregation," Decision Analysis, INFORMS, vol. 18(4), pages 296-320, December.
    9. Destercke, Sébastien & Masson, Marie-Hélène & Poss, Michael, 2015. "Cautious label ranking with label-wise decomposition," European Journal of Operational Research, Elsevier, vol. 246(3), pages 927-935.
    10. Burke, Edmund K. & Bykov, Yuri, 2017. "The late acceptance Hill-Climbing heuristic," European Journal of Operational Research, Elsevier, vol. 258(1), pages 70-78.
    11. Philippe Galinier & Jin-Kao Hao, 1999. "Hybrid Evolutionary Algorithms for Graph Coloring," Journal of Combinatorial Optimization, Springer, vol. 3(4), pages 379-397, December.
    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. Tino Werner, 2022. "Elicitability of Instance and Object Ranking," Decision Analysis, INFORMS, vol. 19(2), pages 123-140, June.
    2. Dipankar Das, 2023. "A Model of Competitive Assortment Planning Algorithm," Papers 2307.09479, arXiv.org.
    3. Christis Katsouris, 2023. "Statistical Estimation for Covariance Structures with Tail Estimates using Nodewise Quantile Predictive Regression Models," Papers 2305.11282, arXiv.org, revised Jul 2023.
    4. Fu, Yelin & Lu, Yihe & Yu, Chen & Lai, Kin Keung, 2022. "Inter-country comparisons of energy system performance with the energy trilemma index: An ensemble ranking methodology based on the half-quadratic theory," Energy, Elsevier, vol. 261(PA).
    5. Weijie J. Su, 2022. "A Truthful Owner-Assisted Scoring Mechanism," Papers 2206.08149, arXiv.org.
    6. Alwyn Lim & Shawn Pope, 2022. "What drives companies to do good? A “universal” ordering of corporate social responsibility motivations," Corporate Social Responsibility and Environmental Management, John Wiley & Sons, vol. 29(1), pages 233-255, January.
    7. Carrizosa, Emilio & Guerrero, Vanesa & Romero Morales, Dolores, 2019. "Visualization of complex dynamic datasets by means of mathematical optimization," Omega, Elsevier, vol. 86(C), pages 125-136.
    8. Francisco Salas-Molina & Filippo Bistaffa & Juan A. Rodriguez-Aguilar, 2024. "A General Approach for Computing a Consensus in Group Decision Making That Integrates Multiple Ethical Principles," Papers 2401.07818, arXiv.org, revised Mar 2024.
    9. Nathan Atkinson & Scott C. Ganz & Dorit S. Hochbaum & James B. Orlin, 2023. "The Strong Maximum Circulation Algorithm: A New Method for Aggregating Preference Rankings," Papers 2307.15702, arXiv.org, revised Oct 2024.
    10. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    11. Noelia Rico & Camino R. Vela & Raúl Pérez-Fernández & Irene Díaz, 2021. "Reducing the Computational Time for the Kemeny Method by Exploiting Condorcet Properties," Mathematics, MDPI, vol. 9(12), pages 1-12, June.
    12. Jingbo Huang & Jiting Li & Yonghao Du & Yanjie Song & Jian Wu & Feng Yao & Pei Wang, 2023. "Research of a Multi-Level Organization Human Resource Network Optimization Model and an Improved Late Acceptance Hill Climbing Algorithm," Mathematics, MDPI, vol. 11(23), pages 1-19, November.
    13. Nicolas Zufferey & Olivier Labarthe & David Schindl, 2012. "Heuristics for a project management problem with incompatibility and assignment costs," Computational Optimization and Applications, Springer, vol. 51(3), pages 1231-1252, April.
    14. Xiao-Feng Xie & Jiming Liu, 2009. "Graph coloring by multiagent fusion search," Journal of Combinatorial Optimization, Springer, vol. 18(2), pages 99-123, August.
    15. Raja Marappan & Gopalakrishnan Sethumadhavan, 2020. "Complexity Analysis and Stochastic Convergence of Some Well-known Evolutionary Operators for Solving Graph Coloring Problem," Mathematics, MDPI, vol. 8(3), pages 1-20, February.
    16. Fagui Liu & Lvshengbiao Wang & Mengke Gui & Yang Zhang & Yulin Lan & Chengqi Lai & Boyuan Zhu, 2023. "A hybrid heuristic algorithm for urban distribution with simultaneous pickup-delivery and time window," Journal of Heuristics, Springer, vol. 29(2), pages 269-311, June.
    17. Bernard Monjardet, 2013. "Marc Barbut au pays des médianes," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-00825005, HAL.
    18. M Plumettaz & D Schindl & N Zufferey, 2010. "Ant Local Search and its efficient adaptation to graph colouring," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 819-826, May.
    19. Kateri, Maria & Nikolov, Nikolay I., 2022. "A generalized Mallows model based on ϕ-divergence measures," Journal of Multivariate Analysis, Elsevier, vol. 190(C).
    20. Kiatsupaibul, Seksan & J. Hayter, Anthony & Liu, Wei, 2017. "Rank constrained distribution and moment computations," Computational Statistics & Data Analysis, Elsevier, vol. 105(C), pages 229-242.

    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:inm:orijoc:v:36:y:2024:i:2:p:308-326. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.