Parallel branch and bound for multidimensional scaling with city-block distances. (English) Zbl 1259.90126

Summary: Multidimensional scaling is a technique for exploratory analysis of multidimensional data. The essential part of the technique is the minimization of a multimodal function with unfavorable properties like invariants and nondifferentiability. Recently, a branch-and-bound algorithm for multidimensional scaling with city-block distances has been proposed for solution of medium-size problems exactly. The algorithm exploits piecewise quadratic structure of the objective function. In this paper, a parallel version of the branch-and-bound algorithm for multidimensional scaling with city-block distances is and investigated. Parallel computing enabled solution of larger problems which is not feasible with the sequential version.


90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut


Full Text: DOI


[1] Androulakis I.P., Floudas C.A. (1999) Distributed branch and bound algorithms for global optimization. In: Pardalos P.M. (eds) Parallel Processing of Discrete Problems. The IMA Volumes in Mathematics and its Applications vol. 106.. Springer, Berlin, pp 1–35 · Zbl 0961.90080
[2] Arabie P. (1991) Was Euclid an unnecessarily sophisticated psychologist. Psychometrika 56(4): 567–587. doi: 10.1007/BF02294491 · Zbl 0761.92050 · doi:10.1007/BF02294491
[3] Borg I., Groenen P.J.F. (2005) Modern Multidimensional Scaling: Theory and Applications, 2nd edn. Springer, New York · Zbl 1085.62079
[4] Brusco M.J. (2001) A simulated annealing heuristic for unidimensional and multidimensional (city-block) scaling of symmetric proximity matrices. J. Classif. 18(1): 3–33. doi: 10.1007/s00357-001-0003-4 · Zbl 1040.91080
[5] Brusco M.J., Stahl S. (2005) Branch-and-Bound Applications in Combinatorial Data Analysis. Springer, New York · Zbl 1093.62006
[6] Cox T.F., Cox M.A.A. (2001) Multidimensional Scaling, 2nd edn. Chapman & Hall/CRC, Boca Raton · Zbl 1004.91067
[7] D’Apuzzo M., Marino M., Migdalas A., Pardalos P.M., Toraldo G. (2006) Parallel computing in global optimization. In: Kontoghiorghes E.J. (eds) Handbook of Parallel Computing and Statistics. Chapman & Hall/CRC, Boca Raton, pp 225–258
[8] de Leeuw J. (1984) Differentiability of Kruskal’s stress at a local minimum. Psychometrika 49(1): 111–113. doi: 10.1007/BF02294209 · doi:10.1007/BF02294209
[9] Ferreira, A., Pardalos, P.M. (eds) (1996) Solving Combinatorial Optimization Problems in Parallel: Methods and Techniques, Lecture Notes in Computer Science, vol 1054. Springer, Berlin · Zbl 0847.00057
[10] Gendron B., Crainic T.G. (1994) Parallel branch-and-bound algorithms: Survey and synthesis. Oper. Res. 42(6): 1042–1066 · Zbl 0824.90096 · doi:10.1287/opre.42.6.1042
[11] Green P., Carmone F., Smith S. (1989) Multidimensional Scaling: Concepts and Applications. Allyn and Bacon, Boston
[12] Groenen P.J.F., Heiser W.J., Meulman J.J. (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, Berlin, pp 46–53 · Zbl 1126.91409
[13] Groenen P.J.F., Heiser W.J., Meulman J.J. (1999) Global optimization in least-squares multidimensional scaling by distance smoothing. J. Classif. 16(2): 225–254. doi: 10.1007/s003579900055 · Zbl 1006.91055 · doi:10.1007/s003579900055
[14] Groenen P.J.F., Mathar R., Heiser W.J. (1995) The majorization approach to multidimensional scaling for Minkowski distances. J. Classif. 12(1): 3–19. doi: 10.1007/BF01202265 · Zbl 0825.92158 · doi:10.1007/BF01202265
[15] Hubert L., Arabie P., Hesson-Mcinnis M. (1992) Multidimensional scaling in the city-block metric: a combinatorial approach. J. Classif. 9(2): 211–236. doi: 10.1007/BF02621407 · doi:10.1007/BF02621407
[16] Hwa J., Graham R.M., Perez D.M. (1995) Identification of critical determinants of {\(\alpha\)}1-adrenergic receptor subtype selective agonist binding. J. Biol. Chem. 270(39): 23189–23195 · doi:10.1074/jbc.270.39.23189
[17] Leung P.L., Lau K. (2004) Estimating the city-block two-dimensional scaling model with simulated annealing. Eur. J. Oper. Res. 158(2): 518–524. doi: 10.1016/S0377-2217(03)00357-6 · Zbl 1067.90130 · doi:10.1016/S0377-2217(03)00357-6
[18] Migdalas, A., Pardalos, P.M., Storøy, S. (eds) (1997) Parallel Computing in Optimization, Applied Optimization, vol. 7. Kluwer, Dordrecht · Zbl 0881.00047
[19] Pardalos, P.M. (eds) (1999) Parallel Processing of Discrete Problems, The IMA Volumes in Mathematics and its Applications, vol. 106. springer, Berlin
[20] Rayward-Smith V.J., Rush S.A., McKeown G.P. (1993) Efficiency considerations in the implementation of parallel branch-and-bound. Ann. Oper. Res. 43(2): 123–145. doi: 10.1007/BF02024489 · Zbl 0784.90108 · doi:10.1007/BF02024489
[21] Ruuskanen J.O., Laurila J., Xhaard H., Rantanen V.V., Vuoriluoto K., Wurster S., Marjamäki A., Vainio M., Johnson M.S., Scheinin M. (2005) Conserved structural, pharmacological and functional properties among the three human and five zebrafish {\(\alpha\)}2-adrenoceptors. Br. J. Pharmacol. 144(2): 165–177. doi: 10.1038/sj.bjp.0706057 · doi:10.1038/sj.bjp.0706057
[22] Uhlén S., Dambrova M., Näsman J., Schiöth H.B., Gu Y., Wikberg-Matsson A., Wikberg J.E.S. (1998) [3h]rs79948-197 binding to human, rat, guinea pig and pig {\(\alpha\)}2A-, {\(\alpha\)}2B- and {\(\alpha\)}2C-adrenoceptors. comparison with mk912, rx821002, rauwolscine and yohimbine. Eur. J. Pharmacol. 343(1): 93–101 · doi:10.1016/S0014-2999(97)01521-5
[23] Vera J.F., Heiser W.J., Murillo A. (2007) Global optimization in any Minkowski metric: a permutation-translation simulated annealing algorithm for multidimensional scaling. J. Classif. 24(2): 277–301. doi: 10.1007/s00357-007-0020-1 · Zbl 1159.91469 · doi:10.1007/s00357-007-0020-1
[24] Žilinskas A., Žilinskas J. (2006) Parallel hybrid algorithm for global optimization of problems occurring in MDS based visualization. Comput. Math. Appl. 52(1-2): 211–224. doi: 10.1016/j.camwa.2006.08.016 · Zbl 1157.90533 · doi:10.1016/j.camwa.2006.08.016
[25] Žilinskas A., Žilinskas J. (2007) Two level minimization in multidimensional scaling. J. Global Optim. 38(4): 581–596. doi: 10.1007/s10898-006-9097-x · Zbl 1145.90060 · doi:10.1007/s10898-006-9097-x
[26] Žilinskas A., Žilinskas J. (2008) A hybrid method for multidimensional scaling using city-block distances. Math. Methods Oper. Res. 68(3): 429–443. doi: 10.1007/s00186-008-0238-5 · Zbl 1159.90023 · doi:10.1007/s00186-008-0238-5
[27] Žilinskas A., Žilinskas J. (2009) Branch and bound algorithm for multidimensional scaling with city-block metric. J. Global Optim. 43(2-3): 357–372. doi: 10.1007/s10898-008-9306-x · Zbl 1179.90250 · doi:10.1007/s10898-008-9306-x
[28] Žilinskas J. (2006) Multidimensional scaling in protein and pharmacological sciences. In: Bogle I.D.L., Žilinskas J. (eds) Computer Aided Methods in Optimal Design and Operations. World Scientific, Singapore, pp 139–148 · Zbl 1113.90121
[29] Žilinskas J. (2007) Reducing of search space of multidimensional scaling problems with data exposing symmetries. Inform. Technol. Control 36(4): 377–382
[30] Žilinskas J. (2008) On dimensionality of embedding space in multidimensional scaling. Informatica 19(3): 447–460 · Zbl 1211.90174
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.