IDEAS home Printed from https://ideas.repec.org/a/wly/jnljam/v2013y2013i1n890589.html

An Improved Exact Algorithm for Least‐Squares Unidimensional Scaling

Author

Listed:
  • Gintaras Palubeckis

Abstract

Given n objects and an n × 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 × 36 Morse code dissimilarity matrix.

Suggested Citation

  • Gintaras Palubeckis, 2013. "An Improved Exact Algorithm for Least‐Squares Unidimensional Scaling," Journal of Applied Mathematics, John Wiley & Sons, vol. 2013(1).
    • Handle: RePEc:wly:jnljam:v:2013:y:2013:i:1:n:890589
    DOI: 10.1155/2013/890589
    as

    Download full text from publisher

    File URL: https://doi.org/10.1155/2013/890589
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2013/890589?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Patrick Groenen & Willem Heiser, 1996. "The tunneling method for global optimization in multidimensional scaling," Psychometrika, Springer;The Psychometric Society, vol. 61(3), pages 529-550, September.
    2. Jukkrit Kluabwang & Deacha Puangdownreong & Sarawut Sujitjorn, 2012. "Multipath Adaptive Tabu Search for a Vehicle Control Problem," Journal of Applied Mathematics, Hindawi, vol. 2012, pages 1-20, February.
    3. Vadim Pliner, 1996. "Metric unidimensional scaling and global optimization," Journal of Classification, Springer;The Classification Society, vol. 13(1), pages 3-18, March.
    4. Jukkrit Kluabwang & Deacha Puangdownreong & Sarawut Sujitjorn, 2012. "Multipath Adaptive Tabu Search for a Vehicle Control Problem," Journal of Applied Mathematics, John Wiley & Sons, vol. 2012(1).
    5. Michael Brusco & Stephanie Stahl, 2005. "Optimal Least-Squares Unidimensional Scaling: Improved Branch-and-Bound Procedures and Comparison to Dynamic Programming," Psychometrika, Springer;The Psychometric Society, vol. 70(2), pages 253-270, June.
    6. Alex Murillo & J. Fernando Vera & Willem J. Heiser, 2005. "A Permutation-Translation Simulated Annealing Algorithm for L 1 and L 2 Unidimensional Scaling," Journal of Classification, Springer;The Classification Society, vol. 22(1), pages 119-138, June.
    7. Nuapett Sarasiri & Kittiwong Suthamno & Sarawut Sujitjorn, 2012. "Bacterial Foraging‐Tabu Search Metaheuristics for Identification of Nonlinear Friction Model," Journal of Applied Mathematics, John Wiley & Sons, vol. 2012(1).
    8. Nuapett Sarasiri & Kittiwong Suthamno & Sarawut Sujitjorn, 2012. "Bacterial Foraging-Tabu Search Metaheuristics for Identification of Nonlinear Friction Model," Journal of Applied Mathematics, Hindawi, vol. 2012, pages 1-23, August.
    9. Michael Brusco & Hans-Friedrich Köhn & Stephanie Stahl, 2008. "Heuristic Implementation of Dynamic Programming for Matrix Permutation Problems in Combinatorial Data Analysis," Psychometrika, Springer;The Psychometric Society, vol. 73(3), pages 503-522, September.
    10. Michael J. Brusco, 2006. "On the Performance of Simulated Annealing for Large-Scale L 2 Unidimensional Scaling," Journal of Classification, Springer;The Classification Society, vol. 23(2), pages 255-268, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Michael Brusco & Hans-Friedrich Köhn & Stephanie Stahl, 2008. "Heuristic Implementation of Dynamic Programming for Matrix Permutation Problems in Combinatorial Data Analysis," Psychometrika, Springer;The Psychometric Society, vol. 73(3), pages 503-522, September.
    2. Groenen, P.J.F. & Borg, I., 2013. "The Past, Present, and Future of Multidimensional Scaling," Econometric Institute Research Papers EI 2013-07, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. Jianxue Wang & Jianming Lu & Zhaohong Bie & Shutang You & Xiaoyu Cao, 2014. "Long‐Term Maintenance Scheduling of Smart Distribution System through a PSO‐TS Algorithm," Journal of Applied Mathematics, John Wiley & Sons, vol. 2014(1).
    4. Michael Brusco & Patrick Doreian, 2015. "An Exact Algorithm for the Two-Mode KL-Means Partitioning Problem," Journal of Classification, Springer;The Classification Society, vol. 32(3), pages 481-515, October.
    5. Michael Brusco & Hans-Friedrich Köhn, 2009. "Exemplar-Based Clustering via Simulated Annealing," Psychometrika, Springer;The Psychometric Society, vol. 74(3), pages 457-475, September.
    6. Michael J. Brusco & Douglas Steinley & Ashley L. Watts, 2022. "Disentangling relationships in symptom networks using matrix permutation methods," Psychometrika, Springer;The Psychometric Society, vol. 87(1), pages 133-155, March.
    7. Michael Brusco & Stephanie Stahl, 2005. "Optimal Least-Squares Unidimensional Scaling: Improved Branch-and-Bound Procedures and Comparison to Dynamic Programming," Psychometrika, Springer;The Psychometric Society, vol. 70(2), pages 253-270, June.
    8. Brusco, Michael J., 2014. "A comparison of simulated annealing algorithms for variable selection in principal component analysis and discriminant analysis," Computational Statistics & Data Analysis, Elsevier, vol. 77(C), pages 38-53.
    9. Michael Brusco & Douglas Steinley, 2011. "A Tabu-Search Heuristic for Deterministic Two-Mode Blockmodeling of Binary Network Matrices," Psychometrika, Springer;The Psychometric Society, vol. 76(4), pages 612-633, October.
    10. Michael Brusco & Stephanie Stahl, 2001. "An interactive multiobjective programming approach to combinatorial data analysis," Psychometrika, Springer;The Psychometric Society, vol. 66(1), pages 5-24, March.
    11. repec:bge:wpaper:573 is not listed on IDEAS
    12. Groenen, Patrick J. F. & Franses, Philip Hans, 2000. "Visualizing time-varying correlations across stock markets," Journal of Empirical Finance, Elsevier, vol. 7(2), pages 155-172, August.
    13. Marc Robini & Pierre-Jean Reissman, 2013. "From simulated annealing to stochastic continuation: a new trend in combinatorial optimization," Journal of Global Optimization, Springer, vol. 56(1), pages 185-215, May.
    14. J. Vera & Rodrigo Macías & Willem Heiser, 2009. "A Latent Class Multidimensional Scaling Model for Two-Way One-Mode Continuous Rating Dissimilarity Data," Psychometrika, Springer;The Psychometric Society, vol. 74(2), pages 297-315, June.
    15. Malone, Samuel W. & Tarazaga, Pablo & Trosset, Michael W., 2002. "Better initial configurations for metric multidimensional scaling," Computational Statistics & Data Analysis, Elsevier, vol. 41(1), pages 143-156, November.
    16. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    17. Michael Brusco & Renu Singh & Douglas Steinley, 2009. "Variable Neighborhood Search Heuristics for Selecting a Subset of Variables in Principal Component Analysis," Psychometrika, Springer;The Psychometric Society, vol. 74(4), pages 705-726, December.
    18. Mirko Armillotta & Konstantinos Fokianos, 2024. "Count network autoregression," Journal of Time Series Analysis, Wiley Blackwell, vol. 45(4), pages 584-612, July.
    19. Groenen, P.J.F. & van de Velden, M., 2004. "Multidimensional scaling," Econometric Institute Research Papers EI 2004-15, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    20. repec:jss:jstsof:31:i03 is not listed on IDEAS
    21. S. Hess & E. Suárez & J. Camacho & G. Ramírez & B. Hernández, 2001. "Reliability of Coordinates Obtained by MINISSA Concerning the Order of Presented Stimuli," Quality & Quantity: International Journal of Methodology, Springer, vol. 35(2), pages 117-128, May.
    22. Jose Apesteguia & Miguel A. Ballester, 2015. "A Measure of Rationality and Welfare," Journal of Political Economy, University of Chicago Press, vol. 123(6), pages 1278-1310.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:jnljam:v:2013:y:2013:i:1:n:890589. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://onlinelibrary.wiley.com/journal/4185 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.