A hybrid method for multidimensional scaling using city-block distances. (English) Zbl 1159.90023

Summary: The problem of multidimensional scaling with city-block distances in the embedding space is reduced to a two level optimization problem consisting of a combinatorial problem at the upper level and a quadratic programming problem at the lower level. A hybrid method is proposed combining randomized search for the upper level problem with a standard quadratic programming algorithm for the lower level problem. Several algorithms for the combinatorial problem have been tested and an evolutionary global search algorithm has been proved most suitable. An experimental code of the proposed hybrid multidimensional scaling algorithm is developed and tested using several test problems of two- and three-dimensional scaling.


90C27 Combinatorial optimization
90C20 Quadratic programming
90C90 Applications of mathematical programming


Genocop; pertsaus2
Full Text: DOI


[1] Arabie P (1991) Was Euclid an unnecessarily sophisticated psychologist?. Psychometrika 56: 567–587 · Zbl 0761.92050 · doi:10.1007/BF02294491
[2] Borg I, Groenen P (2005) Modern multidimensional scaling, 2nd edn. Springer, New York · Zbl 1085.62079
[3] Bortz J (1974) Kritische Bemerkungen über den Einsatz nicht-euklidischer Metriken im Rahmen der multidimensionalen Skalierung. Archiv für Psychologie 126: 196–212
[4] Brusco MJ (2001) A simulated annealing heuristics for unidimensional and multidimensional (city block) scaling of symmetric proximity matrices. J Classif 18: 3–33 · Zbl 1040.91080
[5] Cox T, Cox M (2001) Multidimensional scaling. Chapman & Hall/CRC, London/Boca Raton · Zbl 1004.91067
[6] de Leeuw J (1984) Differentiability of Kruskal’s stress at a local minimum. Psychometrika 49: 111–113 · doi:10.1007/BF02294209
[7] Everett JE (2001) Algorithms for multidimensional scaling. In: Chambers LD(eds) The practical handbook of genetic algorithms, 2nd edn. Chapman & Hall/CRC, London/Boca Raton, pp 203–233
[8] Green P, Carmone F, Smith S (1989) Multidimensional scaling: concepts and applications. Allyn and Bacon, Boston
[9] Groenen PJF, Heiser WJ, Meulman JJ (1998) City-block scaling: smoothing strategies for avoiding local minima. In: Balderjahn I, Mathar R, Schader M(eds) Classification, data analysis, and data highways. Springer, Heidelberg, pp 46–53 · Zbl 1126.91409
[10] Groenen PJF, Heiser WJ, Meulman JJ (1999) Global optimization in least-squares multidimensional scaling by distance smoothing. J Classif 16: 225–254 · Zbl 1006.91055 · doi:10.1007/s003579900055
[11] Groenen PJF, Mathar R, Heiser WJ (1995) The majorization approach to multidimensional scaling for Minkowski distances. J Classif 12: 3–19 · Zbl 0825.92158 · doi:10.1007/BF01202265
[12] Groenen P, Mathar R, Trejos J (2000) Global optimization methods for multidimensional scaling applied to mobile communication. In: Gaul W, Opitz O, Schander M(eds) Data analysis: scientific modeling and practical applications. Springer, Heidelberg, pp 459–475
[13] Hooker JN (1995) Testing heuristics: we have it all wrong. J Heuristics 1: 33–42 · Zbl 0853.68155 · doi:10.1007/BF02430364
[14] Hubert L, Arabie P, Hesson-Mcinnis M (1992) Multidimensional scaling in the city-block metric: a combinatorial approach. J Classif 9: 211–236 · doi:10.1007/BF02621407
[15] Hubert L, Arabie P, Meulman J (2006) The structural representation of proximity matrices with Matlab. SIAM, Philadelphia · Zbl 1093.68147
[16] Leung PL, Lau K (2004) Estimating the city-block two-dimensional scaling model with simulated annealing. Eur J Oper Res 158: 518–524 · Zbl 1067.90130 · doi:10.1016/S0377-2217(03)00357-6
[17] Mathar R, Žilinskas A (1993) On global optimization in two-dimensional scaling. Acta Appl Math 33: 109–118 · Zbl 0792.60023 · doi:10.1007/BF00995497
[18] Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs. Springer, Berlin · Zbl 0841.68047
[19] Murillo A, Vera JF, Heiser WJ (2005) A permutation-translation simulated annealing algorithm for L1 and L2 unidimensional scaling. J Classif 22: 119–138 · Zbl 1084.62055 · doi:10.1007/s00357-005-0008-5
[20] TTörn A, Žilinskas A (1989) Global optimization. Lect Notes Comput Sci 350: 1–250
[21] Žilinskas A, Žilinskas J (2006) Parallel hybrid algorithm for global optimization of problems occurring in MDS-based visualization. Comput Math Appl 52: 211–224 · Zbl 1157.90533 · doi:10.1016/j.camwa.2006.08.016
[22] Žilinskas A, Žilinskas J (2007) Two level minimization in multidimensional scaling. J Global Optim 38: 581–596 · Zbl 1145.90060 · doi:10.1007/s10898-006-9097-x
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.