Abstract
Multidimensional scaling is a technique for exploratory analysis of multidimensional data. The essential part of the technique is minimization of a multimodal function with unfavorable properties like invariants and non-differentiability. 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 has been proposed and investigated. Parallel computing enabled solution of larger problems what was not feasible with the sequential version.
Similar content being viewed by others
References
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
Arabie P. (1991) Was Euclid an unnecessarily sophisticated psychologist. Psychometrika 56(4): 567–587. doi:10.1007/BF02294491
Borg I., Groenen P.J.F. (2005) Modern Multidimensional Scaling: Theory and Applications, 2nd edn. Springer, New York
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
Brusco M.J., Stahl S. (2005) Branch-and-Bound Applications in Combinatorial Data Analysis. Springer, New York
Cox T.F., Cox M.A.A. (2001) Multidimensional Scaling, 2nd edn. Chapman & Hall/CRC, Boca Raton
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
de Leeuw J. (1984) Differentiability of Kruskal’s stress at a local minimum. Psychometrika 49(1): 111–113. doi:10.1007/BF02294209
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
Gendron B., Crainic T.G. (1994) Parallel branch-and-bound algorithms: Survey and synthesis. Oper. Res. 42(6): 1042–1066
Green P., Carmone F., Smith S. (1989) Multidimensional Scaling: Concepts and Applications. Allyn and Bacon, Boston
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
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
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
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
Hwa J., Graham R.M., Perez D.M. (1995) Identification of critical determinants of α1-adrenergic receptor subtype selective agonist binding. J. Biol. Chem. 270(39): 23189–23195
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
Migdalas, A., Pardalos, P.M., Storøy, S. (eds) (1997) Parallel Computing in Optimization, Applied Optimization, vol. 7. Kluwer, Dordrecht
Pardalos, P.M. (eds) (1999) Parallel Processing of Discrete Problems, The IMA Volumes in Mathematics and its Applications, vol. 106. springer, Berlin
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
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 α2-adrenoceptors. Br. J. Pharmacol. 144(2): 165–177. doi:10.1038/sj.bjp.0706057
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 α2A-, α2B- and α2C-adrenoceptors. comparison with mk912, rx821002, rauwolscine and yohimbine. Eur. J. Pharmacol. 343(1): 93–101
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
Ž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
Ž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
Ž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
Ž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
Ž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
Žilinskas J. (2007) Reducing of search space of multidimensional scaling problems with data exposing symmetries. Inform. Technol. Control 36(4): 377–382
Žilinskas J. (2008) On dimensionality of embedding space in multidimensional scaling. Informatica 19(3): 447–460
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Žilinskas, J. Parallel branch and bound for multidimensional scaling with city-block distances. J Glob Optim 54, 261–274 (2012). https://doi.org/10.1007/s10898-010-9624-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-010-9624-7