The linear ordering problem with clusters: a new partial ranking
- PDF / 1,851,141 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 97 Downloads / 216 Views
The linear ordering problem with clusters: a new partial ranking Javier Alcaraz1 · Eva M. García‑Nové1 · Mercedes Landete1 · Juan F. Monge1 Received: 21 January 2020 / Accepted: 29 February 2020 © Sociedad de Estadística e Investigación Operativa 2020
Abstract The linear ordering problem is among core problems in combinatorial optimization. There is a squared non-negative matrix and the goal is to find the permutation of rows and columns which maximizes the sum of superdiagonal values. In this paper, we consider that columns of the matrix belong to different clusters and that the goal is to order the clusters. We introduce a new approach for the case when exactly one representative is chosen from each cluster. The new problem is called the linear ordering problem with clusters and consists of both choosing a representative for each cluster and a permutation of these representatives, so that the sum of superdiagonal values of the sub-matrix induced by the representatives is maximized. A combinatorial linear model for the linear ordering problem with clusters is given, and eventually, a hybrid metaheuristic is carefully designed and developed. Computational results illustrate the performance of the model as well as the effectiveness of the metaheuristic. Keywords Linear ordering problem · Rank aggregation problem · Bucket ordering problem · Metaheuristics Mathematics Subject Classification 90C27 · 90C59 · 90C05
* Mercedes Landete [email protected] Javier Alcaraz [email protected] Eva M. García‑Nové [email protected] Juan F. Monge [email protected] 1
Carr. de San Vicente del Raspeig, University of Alicante, San Vicente del Raspeig, 03690 Alicante, Spain
13
Vol.:(0123456789)
J. Alcaraz et al.
1 Introduction The linear ordering problem is a well-established combinatorial optimization problem. Given a squared non-negative matrix, the problem consists in finding the permutation of rows and columns that maximizes the sum of superdiagonal values. The linear ordering problem has been studied in many fields including antropology (Glover et al. 1974), machine translation (Tromble and Eisner 2009), and voting theory (Kemeny 1959). It is also related to the single-machine scheduling problem, where the objective is to minimize the total weighted (or average weighted) completion time (Grötschel et al. 1984). Given the broad interest in the problem, different computational strategies either exact or heuristics and metaheuristics have been developed. The book Marti and Reinelt (2011) provides a comprehensive study of the linear ordering problem and a thorough discussion of different solution techniques. When the goal is to obtain the closest permutation of rows and columns to a given set of permutations and the distance among permutations is measured with the Kendall–Tau distance,1 then the problem results in the rank aggregation problem (see Andoni et al. 2008; Dwork et al. 2001; Fagin et al. 2003; Yasutake et al. 2012 for a description and evolution of the rank aggregation problem and its applications). These two problems a
Data Loading...
