Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-01-08T11:09:12.106Z Has data issue: false hasContentIssue false
  • English
  • Français

A Branch-and-Bound Algorithm for Fitting Anti-Robinson Structures to Symmetric Dissimilarity Matrices

Published online by Cambridge University Press:  01 January 2025

Michael J. Brusco
Michael J. Brusco*
Affiliation:
Florida State University
*
Requests for reprints should be sent to Michael J. Brusco, Department of Marketing, Florida State University, Tallahassee, FL 32306-1110. E-Mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The seriation of proximity matrices is an important problem in combinatorial data analysis and can be conducted using a variety of objective criteria. Some of the most popular criteria for evaluating an ordering of objects are based on (anti-) Robinson forms, which reflect the pattern of elements within each row and/or column of the reordered matrix when moving away from the main diagonal. This paper presents a branch-and-bound algorithm that can be used to seriate a symmetric dissimilarity matrix by identifying a reordering of rows and columns of the matrix optimizing an anti-Robinson criterion. Computational results are provided for several proximity matrices from the literature using four different anti-Robinson criteria. The results suggest that with respect to computational efficiency, the branch-and-bound algorithm is generally competitive with dynamic programming. Further, because it requires much less storage than dynamic programming, the branch-and-bound algorithm can provide guaranteed optimal solutions for matrices that are too large for dynamic programming implementations.

Keywords

combinatorial optimizationbranch and boundseriationanti-Robinson form
Type
Articles
Information
Psychometrika , Volume 67 , Issue 3 , September 2002 , pp. 459 - 471
Copyright
Copyright © 2002 The Psychometric Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baker, F.B., & Hubert, L.J. (1977). Applications of combinatorial programming to data analysis: Seriation using asymmetric proximity measures. British Journal of Mathematical and Statistical Psychology, 30, 154–164.CrossRefGoogle Scholar
Balas, E. (1965). An additive algorithm for solving linear programs with zero-one variables. Operations Research, 13, 517–546.CrossRefGoogle Scholar
Brusco, M.J., & Stahl, S. (2000). Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices. Journal of Classification, 17, 197–223.CrossRefGoogle Scholar
Brusco, M.J., & Stahl, S. (2001). An interactive approach to multiobjective combinatorial data analysis. Psychometrika, 66, 5–24.CrossRefGoogle Scholar
DeCani, J.S. (1972). A branch-and-bound algorithm for maximum likelihood paired comparison ranking. Biometrika, 59, 131–135.CrossRefGoogle Scholar
Defays, D. (1978). A short note on a method of seriation. British Journal of Mathematical and Statistical Psychology, 31, 49–53.CrossRefGoogle Scholar
Flueck, J.A., & Korsh, J.F. (1974). A branch search algorithm for maximum likelihood paired comparison ranking. Biometrika, 61, 621–626.CrossRefGoogle Scholar
Groenen, P.J.F. (1993). The majorization approach to multidimensional scaling: Some problems and extensions. Leiden, Netherlands: DSWO Press.Google Scholar
Hubert, L.J. (1976). Seriation using asymmetric proximity measures. British Journal of Mathematical and Statistical Psychology, 29, 32–52.CrossRefGoogle Scholar
Hubert, L.J. (1987). Assignment methods in combinatorial data analysis. New York, NY: Marcel Dekker.Google Scholar
Hubert, L.J., & Arabie, P. (1986). Unidimensional scaling and combinatorial optimization. In de Leeuw, J., Heiser, W., Meulman, J., & Critchley, F. (Eds.), Multidimensional data analysis (pp. 181–196). Leiden, Netherlands: DSWO Press.Google Scholar
Hubert, L., & Arabie, P. (1994). The analysis of proximity matrices through sums of matrices having (anti-) Robinson forms. British Journal of Mathematical and Statistical Psychology, 47, 1–40.CrossRefGoogle Scholar
Hubert, L., & Arabie, P. (1995). The approximation of two-mode proximity matrices by sums of order-constrained matrices. Psychometrika, 60, 573–605.CrossRefGoogle Scholar
Hubert, L., Arabie, P., & Meulman, J. (1997). Linear and circular unidimensional scaling for symmetric proximity matrices. British Journal of Mathematical and Statistical Psychology, 50, 253–284.CrossRefGoogle Scholar
Hubert, L., Arabie, P., & Meulman, J. (1998). Graph-theoretic representations for proximity matrices through strongly anti-Robinson or circular strongly anti-Robinson matrices. Psychometrika, 63, 341–358.CrossRefGoogle Scholar
Hubert, L., Arabie, P., & Meulman, J. (2001). Combinatorial data analysis: Optimization by dynamic programming. Philadelphia, PA: Society for Industrial and Applied Mathematics.CrossRefGoogle Scholar
Hubert, L.J., & Golledge, R. G. (1981). Matrix reorganization and dynamic programming: Applications to paired comparisons and unidimensional seriation. Psychometrika, 46, 429–441.CrossRefGoogle Scholar
Lawler, E.L. (1964). A comment on minimum feedback arc sets. IEEE Transactions on Circuit Theory, 11, 296–297.CrossRefGoogle Scholar
Robinson, W.S. (1951). A method for chronologically ordering archaeological deposits. American Antiquity, 16, 293–301.CrossRefGoogle Scholar
Ross, B.H., & Murphy, G.L. (1999). Food for thought: Cross-classification and category organization in a complex real-world domain. Cognitive Psychology, 38, 495–553.CrossRefGoogle Scholar
Thurstone, L.L. (1959). The measurement of values. Chicago, IL: University of Chicago Press.Google Scholar
Younger, D.H. (1963). Minimum feedback arc sets for a directed graph. IEEE Transactions on Circuit Theory, 10, 238–245.CrossRefGoogle Scholar