A linear ordering problem with weighted rank
Abstract
This paper introduces an integer linear program for a variant of the linear ordering problem. This considers, besides the pairwise preferences in the objective function as the linear ordering problem, positional preferences (weighted rank) in the objective. The objective function is mathematically supported, as the full integer linear program is motivated by the instant run-off voting method to aggregate individual preferences. The paper describes two meta-heuristics, iterated local search and Memetic algorithms to deal with large instances which are hard to solve to optimality. These results are compared with the objective value of the linear relaxation. The instances used are the ones available from the LOP library, and new real instances with preferences given by juries.
References
[1]
Alcaraz J, García-Nové EM, Landete M, and Mongel JF The linear ordering problem with clusters: a new partial ranking TOP 2020 28 646-671
[2]
Anderson PE, Chartier TP, Langville AN, and Pedings-Behling KE Fairness and the set of optimal rankings for the linear ordering problem Optim Eng 2021
[3]
Anjos MF and Vieira MVC Facility layout: mathematical optimization techniques and engineering applications 2021 Berlin Springer
[4]
Aparicio J, Landete M, and Monge JF A linear ordering problem of sets Ann Oper Res 2020 288 45-64
[5]
Ceberio J, Mendiburu A, and Lozano JA The linear ordering problem revisited Eur J Oper Res 2015 241 3 686-696
[6]
Ceberio J and Santucci V Using pairwise precedences for solving the linear ordering problem Appl Soft Comput 2020 87
[7]
Charon I and Hudry I A survey on the linear orderign problem for weighted or unweighted tournaments 4OR 2007 5 5-60
[8]
Charon I and Hudry I An updated survey on the linear orderign problem for weighted or unweighted tournaments Ann Oper Res 2010 175 107-158
[9]
Duarte A, Martí R, Álvarez A, and Ángel-Bello F Metaheuristics for the linear ordering problem with cumulative costs Eur J Oper Res 2012 216 2 270-277
[10]
Graham-Squire A and Zayatz N (2020) Lack of monotonicity anomalies in empirical data of instant-runoff elections. Representation
[11]
Grötschel M, Jünger M, and Reinelt G A cutting plane algorithm for the linear ordering problem Oper Res 1984 32 6 1195-1220
[12]
Grötschel M, Jünger M, and Reinelt G Facets of the linear ordering polytope Math Program 1985 33 43-60
[13]
Hautz J, Hungerländer P, Lechner T, Maier K, Rescher P (2020) The weighted linear ordering problem. In: Neufeld JS, Buscher U, Lasch R, Möst D, Schönberger J (eds) Operations research proceedings 2019. Operations research proceedings (GOR (Gesellschaft für Operations Research e.V.)). Springer, Cham
[14]
Hungerländer P and Rendl F A computational study and survey of methods for the single-row facility layout problem Comput Optim Appl 2013 55 1-20
[15]
Hungerländer P and Rendl F Semidefinite relaxations of ordering problems Math Program 2013 140 77-97
[16]
Hungerländer P A semidefinite optimization approach to the Target Visitation Problem Optim Lett 2015 9 1703-1727
[17]
Kemeney JG Mathematics without numbers Daedelus 1959 88 4 577-591
[18]
Laguna M, Martí R, and Campos V Intensification and diversification with elite Tabu search solutions for the linear ordering problem Comput Oper Res 1999 26 12 1217-1230
[19]
Lugo L, Segura C, and Miranda G A diversity-awarememetic algorithm for the linear ordering problem Memetic Comput 2022 14 395-409
[20]
Martí R and Reinelt G The linear ordering problem: exact and heuristic methods in combinatorial optimization 2011 Berlin Springer
[21]
Martí R, Reinelt G, and Duarte A A benchmark library and a comparison of heuristic methods for the linear ordering problem Comput Optim Appl 2012 51 1297-1317
[22]
Méndez-Díaz I, Vulcano G, and Zabala P Analysis of a generalized Linear Ordering Problem via integer programming Discret Appl Math 2019 271 93-107
[23]
Moscato P and Cotta C Glover F and Kochenberger GA A gentle introduction to memetic algorithms Handbook of metaheuristics 2003 Boston Springer
[24]
Qian Y, Lin J, Li D, and Hu H Block-insertion-based algorithms for the linear ordering problem Comput Oper Res 2020 115
[25]
Schiavinotto T and Stützle T The linear ordering problem: instances, search space analysis and algorithms J Math Model Algor 2005 3 367-402
[26]
Tenner BE and Warrington GS Accumulation charts for instant-runoff elections Not Am Math Soc 2019 66 11 1793-1799
Recommendations
Multiple local searches to balance intensification and diversification in a memetic algorithm for the linear ordering problem
HAIS'11: Proceedings of the 6th international conference on Hybrid artificial intelligent systems - Volume Part IIThe Linear Ordering problem (LOP) is an NP-hard problem, which has been solved using different metaheuristic approaches. The best solution for this problem is a memetic algorithm, which uses the traditional approach of hybridizing a genetic algorithm ...
Metaheuristics for large-scale instances of the linear ordering problem
ILS and GDA metaheuristics for the linear ordering problem are introduced.They are able to tackle large instances in line with real applications.Introduced methods are the first of their kind ever applied to large-sized instances.All best known ...
Lagrangian heuristics for the linear ordering problem
MetaheuristicsTwo heuristics for the Linear Ordering Problem are investigated in this paper. These heuristics are embedded within a Lagrangian Relaxation framework and are started with a construction phase. In this process, some Lagrangian (dual) information is used ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 26 February 2024
Accepted: 17 January 2024
Author Tags
Qualifiers
- Research-article
Funding Sources
- Fundação para a Ciência e a Tecnologia (PT)
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024