Branch and bound algorithm for multidimensional scaling with city-block metric. (English) Zbl 1179.90250

Summary: A two level global optimization algorithm for multidimensional scaling (MDS) with city-block metric is proposed. The piecewise quadratic structure of the objective function is employed. At the upper level a combinatorial global optimization problem is solved by means of branch and bound method, where an objective function is defined as the minimum of a quadratic programming problem. The later is solved at the lower level by a standard quadratic programming algorithm. The proposed algorithm has been applied for auxiliary and practical problems whose global optimization counterpart was of dimensionality up to 24.


90C20 Quadratic programming
90C27 Combinatorial optimization
Full Text: DOI


[1] Arabie, P.: Was Euclid an unnecessarily sophisticated psychologist?. Psychometrika 56(4), 567–587 (1991) · Zbl 0761.92050 · doi:10.1007/BF02294491
[2] Borg, I., Groenen, P.: Modern Multidimensional Scaling, 2nd edn. Springer, New York (2005) · Zbl 1085.62079
[3] Brusco, M.J.: A simulated annealing heuristics for unidimensional and multidimensional (city-block) scaling of symmetric proximity matrices. J. Classif. 18(1), 3–33 (2001) · Zbl 1040.91080
[4] Brusco, M.J., Stahl, S.: Branch-and-Bound Applications in Combinatorial Data Analysis. Springer, New York (2005) · Zbl 1093.62006
[5] Brusco, M.J., Stahl, S.: Optimal least-squares unidimensional scaling: improved branch-and-bound procedures and comparison to dynamic programming. Psychometrika 70(2), 253–270 (2005) · Zbl 1306.62388 · doi:10.1007/s11336-002-1032-6
[6] Cox, T., Cox, M.: Multidimensional Scaling. Chapman and Hall/CRC, Boca Raton (2001)
[7] Defays, D.: A short note on a method of seriation. Br. J. Math. Stat. Psychol. 31, 49–53 (1978)
[8] de Leeuw, J.: Differentiability of Kruskal’s stress at a local minimum. Psychometrika 49(1), 111–113 (1984) · doi:10.1007/BF02294209
[9] Green, P., Carmone, F., Smith, S.: Multidimensional Scaling: Concepts and Applications. Allyn and Bacon, Boston (1989)
[10] Groenen, P.J.F., Mathar, R., Heiser, W.J.: The majorization approach to multidimensional scaling for Minkowski distances. J. Classif. 12(1), 3–19 (1995) · Zbl 0825.92158 · doi:10.1007/BF01202265
[11] Groenen, P.J.F., Heiser, W.J., Meulman, J.J.: City-block scaling: smoothing strategies for avoiding local minima. In: Balderjahn, I., Mathar, R., Schader, M.(eds) Classification, Data Analysis, and Data Highways, pp. 46–53. Springer, Heidelberg (1998) · Zbl 1126.91409
[12] Groenen, P.J.F., Heiser, W.J., Meulman, J.J.: Global optimization in least-squares multidimensional scaling by distance smoothing. J. Classif. 16(2), 225–254 (1999) · Zbl 1006.91055 · doi:10.1007/s003579900055
[13] Hubert, L., Arabie, P., Hesson-Mcinnis, M.: Multidimensional scaling in the city-block metric: a combinatorial approach. J. Classif. 9(2), 211–236 (1992) · doi:10.1007/BF02621407
[14] Hwa, J., Graham, R.M., Perez, D.M.: Identification of critical determinants of {\(\alpha\)}1-adrenergic receptor subtype selective agonist binding. J. Biol. Chem. 270(39), 23189–23195 (1995) · doi:10.1074/jbc.270.39.23189
[15] Ruuskanen, J.O., Laurila, J., Xhaard, H., Rantanen, V.-V., Vuoriluoto, K., Wurster, S., Marjamaki, A., Vainio, M., Johnson, M.S., Scheinin, M.: Conserved structural, pharmacological and functional properties among the three human and five zebrafish {\(\alpha\)}2-adrenoceptors. Br. J. Pharmacol. 144(2), 165–177 (2005) · doi:10.1038/sj.bjp.0706057
[16] Uhlén, S., Dambrova, M., Näsman, J., Schiöth, H.B., Gu, Y., Wikberg-Matsson, A., Wikberg, J.E.S.: [3H]RS79948-197 binding to human, rat, guinea pig and pig {\(\alpha\)}2A-, {\(\alpha\)}2B- and {\(\alpha\)}2C-adrenoceptors, Comparison with MK. 912, RX821002, rauwolscine and yohimbine. Eur. J. Pharmacol. 343(1), 93–101 (1998) · doi:10.1016/S0014-2999(97)01521-5
[17] Žilinskas, J.: Multidimensional scaling in protein and pharmacological sciences. In: Bogle, I.D.L., Žilinskas, J.(eds) Computer Aided Methods in Optimal Design and Operations. Series on Computers and Operations Research, vol. 7, pp. 139–148. World Scientific, Singapore (2006) · Zbl 1113.90121
[18] Žilinskas, J.: Reducing of search space of multidimensional scaling problems with data exposing symmetries. Inform. Technol. Control 36(4), 377–382 (2007)
[19] Žilinskas, A., Žilinskas, J.: Parallel hybrid algorithm for global optimization of problems occurring in MDS-based visualization. Comput. Math. Appl. 52(1–2), 211–224 (2006) · Zbl 1157.90533 · doi:10.1016/j.camwa.2006.08.016
[20] Žilinskas, A., Žilinskas, J.: Two level minimization in multidimensional scaling. J. Global Optim. 38(4), 581–596 (2007) · Zbl 1145.90060 · doi:10.1007/s10898-006-9097-x
[21] Žilinskas, A., Žilinskas, J.: A hybrid method for multidimensional scaling using city-block distances. Math. Method. Oper. Res. accepted (2008) · Zbl 0906.65049
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.