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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The Kendall–Tau distance (Kendall 1938) is a classical measure for comparing two permutations which counts the number of pairs for which the order is different in both permutations.
References
Alcaraz J, Landete M, Monge JF (2012) Design and analysis of hybrid metaheuristics for the Reliability p-Median Problem. Eur J Oper Res 222:54–64
Alcaraz J, Landete M, Monge JF, Sainz-Pardo JL (2019) Multi-objective evolutionary algorithms for a reliability location problem. Eur J Oper Res. https://doi.org/10.1016/j.ejor.2019.10.043
Andoni A, Fagin R, Kumar R, Patrascu M, Sivakumar D (2008) Efficient similarity search and classification via rank aggregation. In: Proceedings of the ACM SIG-MOD international conference on management of data, pp 1375–1376
Aparicio J, Landete M, Monge JF (2019) A linear ordering problem of sets. Ann Oper Res. https://doi.org/10.1007/s10479-019-03473-y
Boussaid I, Lepagnot J, Siarry P (2013) A survey on optimization metaheuristics. Inf Sci 237:82–117
Campos V, Glover F, Laguna M, Martí R (2001) An experimental evaluation of a scatter search for the linear ordering problem. J Glob Optim 21:397–414
Dwork C, Kumar R, Naor M, Sivakumar D (2001) Rank aggregation methods for the web. In: Proceedings of the tenth international world wide web conference, pp 613–622
Fagin R, Kumar R, Sivakumar D (2003) Efficient similarity search and classification via rank aggregation. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 301–312
Fagin R, Kumar R, Mahdian M, Sivakumar D, Vee E (2004) Comparing and aggregating rankings with ties. In: Proceedings of the ACM symposium on principles of database systems(PODS), pp 47–58
Feng J, Fang Q, Ng W (2008) Discovering bucket orders from full rankings. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data, pp 55–66
Fortelius M, Gionis A, Jernvall J, Mannila H (2006) Spectral ordering and biochronology of european fossil mammals. Paleobiology 32:206–214
García-Nové EM, Alcaraz J, Landete M, Monge JF, Puerto J (2017) Rank aggregation in cyclic sequences. Optim Lett 11:667–678
Gionis A, Mannila H, Puolamaki K, Ukkonen A (2006) Algorithms for discovering bucket orders from data. In: Proceedings of the ACM SIGKDD conference on knowledge discovery and data mining (KDD), pp 561–566
Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8:156–166
Glover F (1994) Genetic algorithms and scatter search unsuspected potentials. Stat Comput 4:131–140
Glover F (1996) Tabu search and adaptive memory programing—advances, applications and challenges. In: Barr RS, Helgason RV, Dennington JL (eds) Interfaces in computer science and operations research. Kluwer Academic Publishers, Dordrecht, pp 1–75
Glover F (1998) A template for scatter search and path relinking. In: Hao JK, Lutton E, Ronald E, Schoenauer M, Snyers D (eds) Artificial evolution, Lectures Notes in Computer Science, vol 1363. Springer, Berlin, pp 13–54
Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Dordrecht
Glover F, Klastorin T, Kongman D (1974) Optimal weighted ancestry relationships. Manag Sci 20:1190–1193
Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653–684
Glover F, Laguna M, Martí R (2004) Scatter search and path relinking. Foundations and advanced designs. In: Onwubolu GC, Babu BV (eds) New optimization techniques in engineering, Studies in Fuzziness and Soft Computing, vol 141. Springer, Berlin, pp 87–100
Grötschel M, Jänger M, Reinelt G (1984) A cutting plane algorithm for the linear ordering problem. Oper Res 32:1195–1220
Halekoh U, Vach W (2004) A Bayesian approach to seriation problems in archeology. Comput Stat Data Anal 45:651–673
Holland HJ (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
Kemeny J (1959) Mathematics without numbers. Daedalus 88:577–591
Kendall M (1938) A new measure of rank correlation. Biometrika 30:81–89
Laguna M, Martí R (2003) Scatter search. In: Sharda CR, Stefan Voss (eds) Methodology and implementations. Kluwer, Dordrecht
Martí R, Reinelt G (2011) The linear ordering problem exact and heuristic methods in combinational optimization, 1st edn. Springer, Berlin
Miklos I, Somodi I, Podani J (2005) Rearrangement of ecological matrices via markov chain monte carlo simulation. Ecology 86:3398–3410
Mladenovic JA, Moreno-Perez JM, Moreno-Vega A (1996) A chain-interchange heuristic method. Yugoslav J Oper Res 6:41–54
Puolamaki M, Fortelius M, Mannila H (2006) Seriation in paleontological data matrices via Markov chain Monte Carlo methods. PLoS Comput Biol 2:62–70
Reinelt G (1985) The linear ordering problem algorithms and applications. Research and exposition in mathematics series. Heldermann, Berlin
Teitz MB, Bart P (1969) Heuristic methods for estimating the generalized vertex median of a weighted graph. Oper Res 16:955–961
Tromble R, Eisner J (2009) Learning linear ordering problems for better translation. In: Proceedings of the 2009 conference on empirical methods in natural language processing, vol 2, pp 1007–1016
Yasutake S, Hatano K, Takimoto E, Takeda M (2012) Online rank aggregation. In: JMLR workshop and conference proceedings, vol 25. Asian conference on machine learning, pp 539–553
Acknowledgements
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).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Alcaraz, J., García-Nové, E.M., Landete, M. et al. The linear ordering problem with clusters: a new partial ranking. TOP 28, 646–671 (2020). https://doi.org/10.1007/s11750-020-00552-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-020-00552-3