Hostname: page-component-599cfd5f84-5kswg Total loading time: 0 Render date: 2025-01-07T08:33:56.813Z Has data issue: false hasContentIssue false
  • English
  • Français

An Interactive Multiobjective Programming Approach to Combinatorial Data Analysis

Published online by Cambridge University Press:  01 January 2025

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

Abstract

Combinatorial optimization problems in the social and behavioral sciences are frequently associated with a variety of alternative objective criteria. Multiobjective programming is an operations research methodology that enables the quantitative analyst to investigate tradeoffs among relevant objective criteria. In this paper, we describe an interactive procedure for multiobjective asymmetric unidimensional seriation problems. This procedure uses a dynamic-programming algorithm to partially generate the efficient set of sequences for small to medium-sized problems, and a multioperation heuristic to estimate the efficient set for larger problems. The interactive multiobjective procedure is applied to an empirical data set from the psychometric literature. We conclude with a discussion of other potential areas of application in combinatorial data analysis.

Keywords

combinatorial optimizationmultiobjective programmingseriation
Type
Articles
Information
Psychometrika , Volume 66 , Issue 1 , March 2001 , pp. 5 - 24
Copyright
Copyright © 2001 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.)

Footnotes

Stephanie Stahl is a freelance writer and editor. She can be reached via e-mail at [email protected].

References

Arabie, P. (1991). Was Euclid an unnecessarily sophisticated psychologist?. Psychometrika, 56, 567–587.CrossRefGoogle Scholar
Arabie, P., Hubert, L.J. (1996). An overview of combinatorial data analysis. In Arabie, P., Hubert, L.J., De Soete, G. (Eds.), Clustering and classification (pp. 5–63). River Edge, NJ: World Scientific Publishing.CrossRefGoogle Scholar
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
Constantine, A.G., Gower, J.C. (1978). Graphical representation of asymmetric matrices. Applied Statistics, 27, 297–304.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
de Leeuw, J., Heiser, W.J. (1977). Convergence of correction-matrix algorithms for multidimensional scaling. In Lingoes, J.C., Roksam, E.E., Borg, I. (Eds.), Geometric representations of relational data: Readings in multidimensional scaling (pp. 735–752). Ann Arbor, MI: Mathesis Press.Google Scholar
de Leeuw, J., Heiser, W.J. (1980). Multidimensional scaling with restrictions on the configuration of points. In Krishnaiah, P.R. (Eds.), Multivariate analysis (pp. 501–522). Amsterdam: North-Holland.Google Scholar
DeSarbo, W.S., Oliver, R.L., Rangaswamy, A. (1989). A simulated annealing methodology for clusterwise linear regression. Psychometrika, 54, 707–736.CrossRefGoogle Scholar
De Soete, G., Hubert, L., Arabie, P. (1988). The comparative performance of simulated annealing on two problems of combinatorial data analysis. In Diday, E. (Eds.), Data analysis and informatics (pp. 489–496). Amsterdam: North Holland.Google Scholar
Evans, G.W. (1984). An overview of techniques for solving multiobjective mathematical programs. Management Science, 30, 1268–1282.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
Geoffrion, A.M. (1968). Proper efficiency and the theory of vector maximization. Journal of Mathematical Analysis and Applications, 22, 618–630.CrossRefGoogle Scholar
Geoffrion, A.M., Dyer, J.S., Feinberg, A. (1972). An interactive approach for multicriterion optimization with an application to the operation of an academic department. Management Science, 19, 357–368.CrossRefGoogle Scholar
Groenen, P.J.F. (1993). The majorization approach to multidimensional scaling: Some problems and extensions. Leiden, The Netherlands: DSWO Press.Google Scholar
Groenen, P.J.F., Heiser, W.J. (1996). The tunneling method for global optimization in multidimensional scaling. Psychometrika, 61, 529–550.CrossRefGoogle Scholar
Hapke, M., Jaszkiewicz, A., Slowinski, R. (1998). Interactive analysis of multiple-criteria project scheduling problems. European Journal of Operational Research, 107, 315–324.CrossRefGoogle Scholar
Held, M., Karp, R.M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10, 196–210.CrossRefGoogle Scholar
Heiser, W.J. (1989). The city-block model for three-way multidimensional scaling. In Coppi, R., Belasco, S. (Eds.), Multiway data analysis (pp. 395–404). Amsterdam: North-Holland.Google Scholar
Holman, E.W. (1979). Monotonic models for asymmetric proximities. Journal of Mathematical Psychology, 20, 1–15.CrossRefGoogle Scholar
Hubert, L. (1974). Some applications of graph theory and related nonmetric techniques to problems of approximate seriation: The case of symmetric proximity measures. British Journal of Mathematical and Statistical Psychology, 27, 133–153.CrossRefGoogle 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., Arabie, P., Hesson-McInnis, M. (1992). Multidimensional scaling in the city-block metric: A combinatorial approach. Journal of Classification, 9, 211–236.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.J., Baker, F.B. (1978). Applications of combinatorial programming to data analysis: The traveling salesman and related problems. Psychometrika, 43, 81–91.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
Hubert, L.J., Schultz, J.V. (1976). Quadratic assignment as a general data analysis strategy. British Journal of Mathematical and Statistical Psychology, 29, 190–241.CrossRefGoogle Scholar
Hutchinson, J.W. (1989). NETSCAL: A network scaling algorithm for nonsymmetric proximity data. Psychometrika, 54, 25–52.CrossRefGoogle Scholar
Kok, M. (1986). The interface with decision makers and some experimental results in interactive multiple objective programming methods. European Journal of Operational Research, 26, 96–107.CrossRefGoogle Scholar
Koopmans, T.C., Beckmann, M. (1957). Assignment problems and the location of economic activities. Econometrica, 25, 53–76.CrossRefGoogle Scholar
Krieger, A.M., Green, P.E. (1996). Modifying cluster-based segments to enhance agreement with an exogenous response variable. Journal of Marketing Research, 33, 351–363.CrossRefGoogle Scholar
Lawler, E.L. (1964). A comment on minimum feedback arc sets. IEEE Transactions on Circuit Theory, 11, 296–297.CrossRefGoogle Scholar
Levin, J., Brown, M. (1979). Scaling a conditional proximity matrix to symmetry. Psychometrika, 44, 239–244.CrossRefGoogle Scholar
Meulman, J.J. (1992). The integration of multidimensional scaling and multivariate analysis with optimal transformations. Psychometrika, 57, 539–565.CrossRefGoogle Scholar
Olson, D.L. (1992). Review of empirical studies in multiobjective mathematical programming: subject reflection of nonlinear utility and learning. Decision Sciences, 23, 1–20.CrossRefGoogle Scholar
Poole, K.T. (1990). Least squares metric, unidimensional scaling of multivariate linear models. Psychometrika, 55, 123–149.CrossRefGoogle Scholar
Pliner, V. (1996). Metric unidimensional scaling and global optimization. Journal of Classification, 13, 3–18.CrossRefGoogle Scholar
Ringuest, J.L. (1992). Multiobjective optimization: Behavioral and computational considerations. Norwell, MA: Kluwer Academic Publishers.CrossRefGoogle Scholar
Rodgers, J.L., Thompson, T.D. (1992). Seriation and multidimensional scaling: A data analysis approach to scaling asymmetric proximity matrices. Applied Psychological Measurement, 16, 105–117.CrossRefGoogle Scholar
Rosenthal, R.E. (1985). Principles of multiobjective optimization. Decision Sciences, 16, 133–152.CrossRefGoogle Scholar
Simantiraki, E. (1996). Unidimensional scaling: A linear programming approach minimizing absolute deviations. Journal of Classification, 13, 19–25.CrossRefGoogle Scholar
Soland, R.M. (1979). Multicriteria optimization: A general characterization of efficient solutions. Decision Sciences, 10, 26–38.CrossRefGoogle Scholar
Späth, H. (1979). Algorithm 39: Clusterwise linear regression. Computing, 22, 367–373.CrossRefGoogle Scholar
Szczotka, F. (1972). On a method of ordering and clustering of objects. Zastosowania Mathemetyki, 13, 23–33.Google Scholar
Thurstone, L.L. (1927). The method of paired comparison of social values. Journal of Abnormal and Social Psychology, 31, 384–400.CrossRefGoogle Scholar
Vriens, M., Wedel, M., Wilms, T. (1996). Metric conjoint segmentation methods: A Monte Carlo comparison. Journal of Marketing Research, 33, 73–85.CrossRefGoogle Scholar
Wallenius, J. (1975). Comparative evaluation of some interactive approaches to multicriterion optimization. Management Science, 21, 1387–1396.CrossRefGoogle Scholar
Weeks, D.G., Bentler, P.M. (1982). Restricted multidimensional scaling models for asymmetric proximities. Psychometrika, 47, 201–208.CrossRefGoogle Scholar
Zielman, B., Heiser, W.J. (1996). Models for asymmetric proximities. British Journal of Mathematical and Statistical Psychology, 49, 127–146.CrossRefGoogle Scholar