An improved exact algorithm for least-squares unidimensional scaling. (English) Zbl 1266.65072

Summary: Given \(n\) objects and an \(n \times n\) symmetric dissimilarity matrix \(D\) with zero main diagonal and nonnegative off-diagonal entries, the least-squares unidimensional scaling problem asks to find an arrangement of objects along a straight line such that the pairwise distances between them reflect dissimilarities represented by the matrix \(D\). In this paper, we propose an improved branch-and-bound algorithm for solving this problem. The main ingredients of the algorithm include an innovative upper bounding technique relying on the linear assignment model and a dominance test which allows considerably reducing the redundancy in the enumeration process. An initial lower bound for the algorithm is provided by an iterated tabu search heuristic. To enhance the performance of this heuristic we develop an efficient method for exploring the pairwise interchange neighborhood of a solution in the search space. The basic principle and formulas of the method are also used in the implementation of the dominance test. We report computational results for both randomly generated and real-life based problem instances. In particular, we were able to solve to guaranteed optimality the problem defined by a \(36 \times 36\) Morse code dissimilarity matrix.


65F35 Numerical computation of matrix norms, conditioning, scaling
Full Text: DOI


[1] I. Borg and P. J. F. Groenen, Modern Multidimensional Scaling: Theory and Appplications, Springer, New York, NY, USA, 2nd edition, 2005. · Zbl 1085.62079
[2] L. Hubert, P. Arabie, and J. Meulman, The Structural Representation of Proximity Matrices with MATLAB, vol. 19, SIAM, Philadelphia, Pa, USA, 2006. · Zbl 1214.82029
[3] S. Meisel and D. Mattfeld, “Synergies of Operations Research and Data Mining,” European Journal of Operational Research, vol. 206, no. 1, pp. 1-10, 2010. · Zbl 1188.90001
[4] G. Caraux and S. Pinloche, “PermutMatrix: a graphical environment to arrange gene expression profiles in optimal linear order,” Bioinformatics, vol. 21, no. 7, pp. 1280-1281, 2005.
[5] M. K. Ng, E. S. Fung, and H.-Y. Liao, “Linkage disequilibrium map by unidimensional nonnegative scaling,” in Proceedings of the 1st International Symposium on Optimization and Systems Biology (OSB ’07), pp. 302-308, Beijing, China, 2007.
[6] P. I. Armstrong, N. A. Fouad, J. Rounds, and L. Hubert, “Quantifying and interpreting group differences in interest profiles,” Journal of Career Assessment, vol. 18, no. 2, pp. 115-132, 2010.
[7] L. Hubert and D. Steinley, “Agreement among supreme court justices: categorical versus continuous representation,” SIAM News, vol. 38, no. 7, 2005.
[8] A. Dahabiah, J. Puentes, and B. Solaiman, “Digestive casebase mining based on possibility theory and linear unidimensional scaling,” in Proceedings of the 8th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering and Data Bases (AIKED ’09), pp. 218-223, World Scientific and Engineering Academy and Society (WSEAS), Stevens Point, Wis, USA, 2009.
[9] A. Dahabiah, J. Puentes, and B. Solaiman, “Possibilistic pattern recognition in a digestive database for mining imperfect data,” WSEAS Transactions on Systems, vol. 8, no. 2, pp. 229-240, 2009. · Zbl 1335.68199
[10] Y. Ge, Y. Leung, and J. Ma, “Unidimensional scaling classifier and its application to remotely sensed data,” in Proceedings of the IEEE International Geoscience and Remote Sensing Symposium (IGARSS ’05), pp. 3841-3844, July 2005.
[11] J. H. Bihn, M. Verhaagh, M. Brändle, and R. Brandl, “Do secondary forests act as refuges for old growth forest animals? Recovery of ant diversity in the Atlantic forest of Brazil,” Biological Conservation, vol. 141, no. 3, pp. 733-743, 2008.
[12] D. Defays, “A short note on a method of seriation,” British Journal of Mathematical and Statistical Psychology, vol. 31, no. 1, pp. 49-53, 1978.
[13] M. J. Brusco and S. Stahl, “Optimal least-squares unidimensional scaling: improved branch-and-bound procedures and comparison to dynamic programming,” Psychometrika, vol. 70, no. 2, pp. 253-270, 2005. · Zbl 1306.62388
[14] L. J. Hubert and P. Arabie, “Unidimensional scaling and combinatorial optimization,” in Multidimensional Data Analysis, J. de Leeuw, W. J. Heiser, J. Meulman, and F. Critchley, Eds., pp. 181-196, DSWO Press, Leiden, The Netherlands, 1986.
[15] L. J. Hubert, P. Arabie, and J. J. Meulman, “Linear unidimensional scaling in the L2-norm: basic optimization methods using MATLAB,” Journal of Classification, vol. 19, no. 2, pp. 303-328, 2002. · Zbl 1040.91081
[16] M. J. Brusco and S. Stahl, Branch-and-Bound Applications in Combinatorial Data Analysis, Springer Science + Business Media, New York, NY, USA, 2005. · Zbl 1093.62006
[17] V. Pliner, “Metric unidimensional scaling and global optimization,” Journal of Classification, vol. 13, no. 1, pp. 3-18, 1996. · Zbl 0857.92026
[18] A. Murillo, J. F. Vera, and W. J. Heiser, “A permutation-translation simulated annealing algorithm for L1 and L2 unidimensional scaling,” Journal of Classification, vol. 22, no. 1, pp. 119-138, 2005. · Zbl 1084.62055
[19] M. J. Brusco, “On the performance of simulated annealing for large-scale L2 unidimensional scaling,” Journal of Classification, vol. 23, no. 2, pp. 255-268, 2006. · Zbl 1336.62174
[20] M. J. Brusco, H. F. Köhn, and S. Stahl, “Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis,” Psychometrika, vol. 73, no. 3, pp. 503-522, 2008. · Zbl 1301.62118
[21] G. Palubeckis, “Iterated tabu search for the maximum diversity problem,” Applied Mathematics and Computation, vol. 189, no. 1, pp. 371-383, 2007. · Zbl 1122.65362
[22] G. Palubeckis, “A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem,” Applied Mathematics and Computation, vol. 215, no. 3, pp. 1106-1117, 2009. · Zbl 1179.90234
[23] J. Kluabwang, D. Puangdownreong, and S. Sujitjorn, “Multipath adaptive tabu search for a vehicle control problem,” Journal of Applied Mathematics, vol. 2012, Article ID 731623, 20 pages, 2012. · Zbl 1242.93090
[24] N. Sarasiri, K. Suthamno, and S. Sujitjorn, “Bacterial foraging-tabu search metaheuristics for identification of nonlinear friction model,” Journal of Applied Mathematics, vol. 2012, Article ID 238563, 23 pages, 2012. · Zbl 1251.74026
[25] A. Jouglet and J. Carlier, “Dominance rules in combinatorial optimization problems,” European Journal of Operational Research, vol. 212, no. 3, pp. 433-444, 2011. · Zbl 1237.90199
[26] E. Z. Rothkopf, “A measure of stimulus similarity and errors in some paired-associate learning tasks,” Journal of Experimental Psychology, vol. 53, no. 2, pp. 94-101, 1957.
[27] I. Düntsch and G. Gediga, “Modal-Style Operators in Qualitative Data Analysis,” Tech. Rep. CS-02-15, Department of Computer Science, Brock University, St. Catharines, Ontario, Canada, 2002.
[28] R. N. Shepard, “Analysis of proximities as a technique for the study of information processing in man,” Human factors, vol. 5, pp. 33-48, 1963.
[29] P. J. F. Groenen and W. J. Heiser, “The tunneling method for global optimization in multidimensional scaling,” Psychometrika, vol. 61, no. 3, pp. 529-550, 1996. · Zbl 0866.92028
[30] L. Hubert, P. Arabie, and J. Meulman, Combinatorial Data Analysis: Optimization by Dynamic Programming, SIAM, Philadelphia, Pa, USA, 2001. · Zbl 0999.90047
[31] B. H. Ross and G. L. Murphy, “Food for thought: cross-classification and category organization in a complex real-world domain,” Cognitive Psychology, vol. 38, no. 4, pp. 495-553, 1999.
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.