The linear ordering problem with clusters: a new partial ranking
| Autor: | Eva M. García-Nové, Juan F. Monge, Mercedes Ponce Landete, Javier Alcaraz |
|---|---|
| Přispěvatelé: | Departamentos de la UMH::Estadística, Matemáticas e Informática, Universidad de Alicante. Departamento de Fundamentos del Análisis Económico, Estadística, Matemáticas e Informática |
| Rok vydání: | 2020 |
| Předmět: |
Statistics and Probability
Information Systems and Management 0211 other engineering and technologies Metaheuristics 02 engineering and technology Management Science and Operations Research Row and column spaces 01 natural sciences Combinatorics 010104 statistics & probability Matrix (mathematics) Permutation Cluster (physics) Discrete Mathematics and Combinatorics 0101 mathematics Metaheuristic Mathematics Fundamentos del Análisis Económico Bucket ordering problem 021103 operations research Linear model Linear ordering problem Ranking 517 - Análisis Modeling and Simulation Combinatorial optimization Rank aggregation problem |
| Zdroj: | REDIUMH. Depósito Digital de la UMH Universitat Pompeu Fabra REDIUMH: Depósito Digital de la UMH Universidad Miguel Hernández de Elche |
| ISSN: | 1863-8279 1134-5764 |
| DOI: | 10.1007/s11750-020-00552-3 |
| Popis: | 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 This work was supported by the Spanish Ministerio de Ciencia, Innovación y Universidades and Fondo Europeo de Desarrollo Regional (FEDER) through project PGC2018-099428-B-100 and by the Spanish Ministerio de Economía, Industria y Competitividad under Grant MTM2016-79765-P (AEI/FEDER, UE). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink