zbMATH — the first resource for mathematics

The linear ordering problem with clusters: a new partial ranking. (English) Zbl 1467.90046
Summary: 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.
MSC:
 90C27 Combinatorial optimization 90C59 Approximation methods and heuristics in mathematical programming 90C05 Linear programming
Software:
LOLIB; Scatter Search; Tabu search
Full Text:
References:
 [1] Alcaraz, J.; Landete, M.; Monge, JF, Design and analysis of hybrid metaheuristics for the Reliability p-Median Problem, Eur J Oper Res, 222, 54-64 (2012) · Zbl 1253.90130 [2] Alcaraz J, Landete M, Monge JF, Sainz-Pardo JL (2019) Multi-objective evolutionary algorithms for a reliability location problem. Eur J Oper Res. 10.1016/j.ejor.2019.10.043 · Zbl 1431.90084 [3] 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 [4] Aparicio J, Landete M, Monge JF (2019) A linear ordering problem of sets. Ann Oper Res. 10.1007/s10479-019-03473-y · Zbl 1437.62170 [5] Boussaid, I.; Lepagnot, J.; Siarry, P., A survey on optimization metaheuristics, Inf Sci, 237, 82-117 (2013) · Zbl 1321.90156 [6] Campos, V.; Glover, F.; Laguna, M.; Martí, R., An experimental evaluation of a scatter search for the linear ordering problem, J Glob Optim, 21, 397-414 (2001) · Zbl 1175.90424 [7] 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 [8] 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 [9] 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 [10] 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 [11] Fortelius, M.; Gionis, A.; Jernvall, J.; Mannila, H., Spectral ordering and biochronology of european fossil mammals, Paleobiology, 32, 206-214 (2006) [12] García-Nové, EM; Alcaraz, J.; Landete, M.; Monge, JF; Puerto, J., Rank aggregation in cyclic sequences, Optim Lett, 11, 667-678 (2017) · Zbl 1367.90094 [13] 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 [14] Glover, F., Heuristics for integer programming using surrogate constraints, Decis Sci, 8, 156-166 (1977) [15] Glover, F., Genetic algorithms and scatter search unsuspected potentials, Stat Comput, 4, 131-140 (1994) [16] Glover, F.; Barr, RS; Helgason, RV; Dennington, JL, Tabu search and adaptive memory programing—advances, applications and challenges, Interfaces in computer science and operations research, 1-75 (1996), Dordrecht: Kluwer Academic Publishers, Dordrecht [17] Glover, F.; Hao, JK; Lutton, E.; Ronald, E.; Schoenauer, M.; Snyers, D., A template for scatter search and path relinking, Artificial evolution, Lectures Notes in Computer Science, 13-54 (1998), Berlin: Springer, Berlin [18] Glover, F.; Laguna, M., Tabu search (1997), Dordrecht: Kluwer Academic Publishers, Dordrecht [19] Glover, F.; Klastorin, T.; Kongman, D., Optimal weighted ancestry relationships, Manag Sci, 20, 1190-1193 (1974) · Zbl 0303.90055 [20] Glover, F.; Laguna, M.; Martí, R., Fundamentals of scatter search and path relinking, Control Cybern, 39, 653-684 (2000) · Zbl 0983.90077 [21] Glover, F.; Laguna, M.; Martí, R.; Onwubolu, GC; Babu, BV, Scatter search and path relinking. Foundations and advanced designs, New optimization techniques in engineering, Studies in Fuzziness and Soft Computing, 87-100 (2004), Berlin: Springer, Berlin [22] Grötschel, M.; Jänger, M.; Reinelt, G., A cutting plane algorithm for the linear ordering problem, Oper Res, 32, 1195-1220 (1984) · Zbl 0554.90077 [23] Halekoh, U.; Vach, W., A Bayesian approach to seriation problems in archeology, Comput Stat Data Anal, 45, 651-673 (2004) · Zbl 1429.62718 [24] Holland, HJ, Adaptation in natural and artificial systems (1975), Ann Arbor: University of Michigan Press, Ann Arbor [25] Kemeny, J., Mathematics without numbers, Daedalus, 88, 577-591 (1959) [26] Kendall, M., A new measure of rank correlation, Biometrika, 30, 81-89 (1938) · Zbl 0019.13001 [27] Laguna, M.; Martí, R.; Sharda, CR; Stefan, Voss, Scatter search, Methodology and implementations (2003), Dordrecht: Kluwer, Dordrecht [28] Martí, R.; Reinelt, G., The linear ordering problem exact and heuristic methods in combinational optimization (2011), Berlin: Springer, Berlin [29] Miklos, I.; Somodi, I.; Podani, J., Rearrangement of ecological matrices via markov chain monte carlo simulation, Ecology, 86, 3398-3410 (2005) [30] Mladenovic, JA; Moreno-Perez, JM; Moreno-Vega, A., A chain-interchange heuristic method, Yugoslav J Oper Res, 6, 41-54 (1996) · Zbl 0848.90104 [31] Puolamaki, M.; Fortelius, M.; Mannila, H., Seriation in paleontological data matrices via Markov chain Monte Carlo methods, PLoS Comput Biol, 2, 62-70 (2006) [32] Reinelt, G., The linear ordering problem algorithms and applications. Research and exposition in mathematics series (1985), Berlin: Heldermann, Berlin · Zbl 0565.68058 [33] Teitz, MB; Bart, P., Heuristic methods for estimating the generalized vertex median of a weighted graph, Oper Res, 16, 955-961 (1969) · Zbl 0165.22804 [34] 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 [35] 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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.