Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-11T09:36:36.132Z Has data issue: false hasContentIssue false
  • English
  • Français

Applications of Combinatorial Programming to Data Analysis: The Traveling Salesman and Related Problems

Published online by Cambridge University Press:  01 January 2025

Lawrence J. Hubert  and
Frank B. Baker
Lawrence J. Hubert*
Affiliation:
The University of Wisconsin
Frank B. Baker
Affiliation:
The University of Wisconsin
*
Requests for reprints should be sent to Lawrence J. Hubert, The University of Wisconsin, Department of Educational Psychology, 1025 West Johnson, Madison, Wisconsin 53706.
Get access Rights & Permissions [Opens in a new window]

Abstract

The “Traveling Salesman” and similar combinatorial programming tasks encountered in operations research are discussed as possible data analysis models in psychology, for example, in developmental scaling, Guttman scaling, profile smoothing, and data array clustering. In addition, a short overview of the various computational approaches from this area of combinatorial optimization is included.

Keywords

Hamiltonian pathGuttman scaledevelopmental scale
Type
Original Paper
Information
Psychometrika , Volume 43 , Issue 1 , March 1978 , pp. 81 - 91
Copyright
Copyright © 1978 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

The research of the first author was supported by a research grant SOC-75-07860 from the National Science Foundation.

References

Reference Note

Kadane, J. B. Chronological ordering of archaeological deposits by the minimum path method, 1972, Pennsylvania: Carnegie-Mellon University, Department of Statistics.Google Scholar

References

Allen, J. N. Low overhead sequencing algorithm. Mathematical Biosciences, 1969, 5, 449–460.CrossRefGoogle Scholar
Barachet, L. L. Graphic solution of the traveling salesman problem. Operations Research, 1957, 5, 841–845.CrossRefGoogle Scholar
Bellman, R. Dynamic programming treatment of the traveling salesman problem. Journal of the Association for Computing Machinery, 1962, 9, 61–63.CrossRefGoogle Scholar
Bellmore, M., & Malone, J. C. Pathology of traveling salesman subtour-elimination algorithms. Operations Research, 1971, 19, 278–307.CrossRefGoogle Scholar
Bellmore, M., & Nemhauser, G. L. The traveling salesman problem: A survey. Operations Research, 1968, 16, 538–558.CrossRefGoogle Scholar
Bhat, M. V., & Haupt, A. An efficient clustering algorithm. IEEE Transactions on Systems, Man, and Cybernetics, 1976, 6, 61–64.CrossRefGoogle Scholar
Blin, J. M. On tournament patterns and rational group decisions. Proceedings IEEE 1973 International Conference on Cybernetics and Society, 55–59.Google Scholar
Bock, F. Mathematical programming solution of traveling salesman examples. In Graaves, R. L. & Wolfe, P. (Eds.), Recent advances in mathematical programming, 1963, New York: McGraw-Hill.Google Scholar
Bowden, E. Ordinal scaling of multicategory persisting and disappearing traits. Behavioral Science, 1973, 18, 386–390.CrossRefGoogle Scholar
Breiger, R. L., Boorman, S. A., & Arabie, P. An algorithm for clustering relational data with applications to social network analysis and comparison with multidimensional scaling. Journal of Mathematical Psychology, 1975, 12, 328–383.CrossRefGoogle Scholar
Christofides, N. The shortest Hamiltonian chain of a graph. SIAM Journal of Applied Mathematics, 1970, 19, 689–696.CrossRefGoogle Scholar
Christofides, N. Bounds for the traveling salesman problem. Operations Research, 1972, 20, 1044–1056.CrossRefGoogle Scholar
Christofides, N. Hamiltonian circuits and the traveling salesman problem. In Roy, B. (Eds.), Combinatorial programming: Methods and applications, 1975, Dordrecht, Holland: D. Reidel.Google Scholar
Christofides, N. Graph theory: An algorithmic approach, 1975, New York: Academic Press.Google Scholar
Christofides, N., & Eilon, S. Algorithms for large-scale traveling salesman problems. Operational Research Quarterly, 1972, 23, 511–518.CrossRefGoogle Scholar
Coombs, C. H., & Smith, J. E. K. On the detection of structure in attitudes and developmental processes. Psychological Review, 1973, 80, 337–351.CrossRefGoogle Scholar
Corneil, D. G. The analysis of graph theoretical algorithms. Proceedings of the 5th South-East Conference on Combinatorics, Graph Theory and Computing, 1974, 3-38.Google Scholar
Croes, G. A. A method for solving traveling salesman problems. Operations Research, 1958, 6, 791–812.CrossRefGoogle Scholar
Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. Solution of a large scale traveling salesman problem. Operations Research, 1954, 2, 393–410.Google Scholar
Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. On a linear programming, combinatorial approach to the traveling salesman problem. Operations Research, 1959, 7, 58–66.CrossRefGoogle Scholar
Flood, M. M. The traveling salesman problem. Operations Research, 1956, 4, 61–75.CrossRefGoogle Scholar
Garfinkel, R. S. On partitioning the feasible set in a branch-and-bound algorithm for the asymmetric traveling salesman problem. Operations Research, 1972, 20, 340–343.Google Scholar
Gavett, J. W. Three heuristic rules for sequencing jobs to a single production facility. Management Science, 1965, 11, 166–176.CrossRefGoogle Scholar
Gelfand, A. E. Seriation methods for archaeological materials. American Antiquity, 1971, 36, 263–274.CrossRefGoogle Scholar
Gelfand, A. E. Rapid seriation methods with archaeological applications. In Hodson, F. R., Kendall, D. G., Tautu, P. (Eds.), Mathematics in the archaeological and historical sciences, 1971, Edinburgh: Edinburgh University Press.Google Scholar
Gelfand, A. E. Rapid seriation methods for multivariate observations through similarities. Communications in Statistics, 1974, 3, 635–645.CrossRefGoogle Scholar
Gomory, R. E. The traveling salesman problem. Proceedings IBM Scientific Computing Symposium on Combinatorial Problems, 1964, New York: White Plains.Google Scholar
Green, B. F. A method of scalogram analysis using summary statistics. Psychometrika, 1965, 21, 79–88.CrossRefGoogle Scholar
Gruvaeus, G., & Wainer, H. Two additions to heirarchical cluster analysis. The British Journal of Mathematical and Statistical Psychology, 1972, 25, 200–206.CrossRefGoogle Scholar
Gupta, J. N. D. Traveling salesman problem—A survey of theoretical developments and applications. Opsearch, 1968, 5, 181–192.Google Scholar
Hansen, K. H., & Krarup, J. Improvements of the Held-Karp algorithm for the symmetric traveling salesman problem. Mathematical Programming, 1974, 7, 87–96.CrossRefGoogle Scholar
Hardgrave, W. W., & Nemhauser, G. L. On the relation between the traveling salesman and the longest path problem. Operations Research, 1962, 10, 647–657.CrossRefGoogle Scholar
Hartigan, J. A. Clustering algorithms, 1975, New York: Wiley.Google Scholar
Held, M., & Karp, R. M. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 1962, 10, 196–210.CrossRefGoogle Scholar
Held, M., & Karp, R. M. The traveling salesman problem and minimum spanning trees. Operations Research, 1970, 18, 1138–1162.CrossRefGoogle Scholar
Held, M., & Karp, R. M. The traveling salesman problem and minimum spanning trees: Part II. Mathematical Programming, 1971, 1, 6–25.CrossRefGoogle Scholar
Hubert, L. Problems of seriation using a subject by item response matrix. Psychological Bulletin, 1974, 81, 976–983.CrossRefGoogle Scholar
Hubert, L. Some applications of graph theory and related non-metric techniques to problems of approximate seriation: The case of symmetric proximity measures. The British Journal of Mathematical and Statistical Psychology, 1974, 27, 133–153.CrossRefGoogle Scholar
Hubert, L. Seriation using asymmetric proximity measures. The British Journal of Mathematical and Statistical Psychology, 1976, 29, 32–52.CrossRefGoogle Scholar
Hubert, L., & Schultz, J. Quadratic assignment as a general data analysis strategy. The British Journal of Mathematical and Statistical Psychology, 1976, 29, 190–241.CrossRefGoogle Scholar
Isaac, A. M., & Turban, E. Some comments on the traveling salesman problem. Operations Research, 1969, 17, 543–546.CrossRefGoogle Scholar
Karg, R. L., & Thompson, G. L. A heuristic approach to solving traveling salesman problems. Management Science, 1964, 10, 225–248.CrossRefGoogle Scholar
Karp, R. M. Reducibility among combinatorial problems. In Miller, R. E. and Thatcher, J. W. (Eds.), Complexity of computer computations, 1972, New York: Plenum.Google Scholar
Kendall, D. G. Abundance matrices and seriation in archaeology. Zeitschrift für Wahrscheinlichkeitstheorie, 1971, 17, 104–112.CrossRefGoogle Scholar
Kendall, D. G. Seriation from abundance matrices. In Hodson, F. R., Kendall, D. G., and Tautu, P. (Eds.), Mathematics in the archaeological and historical sciences, 1971, Edinburgh: Edinburgh University Press.Google Scholar
Krolak, P., Felts, W., & Marble, G. A man-machine approach toward solving the traveling salesman problem. Design Automation Workshop, 1970, 7, 250–256.Google Scholar
Lawler, E. L., & Wood, D. E. Branch-and-bound methods: A survey. Operations Research, 1966, 14, 699–719.CrossRefGoogle Scholar
Leik, R. K., & Matthews, M. A scale for developmental processes. American Sociological Review, 1968, 33, 62–75.CrossRefGoogle ScholarPubMed
Lenstra, J. K. Clustering a data array and the traveling salesman problem. Operations Research, 1974, 22, 413–414.CrossRefGoogle Scholar
Lenstra, J. K., & Kan, A. H. G. Rinnooy. Some simple applications of the traveling salesman problem. Operational Research Quarterly, 1975, 26, 717–733.CrossRefGoogle Scholar
Lin, S. Computer solutions of the traveling salesman problem. The Bell System Technical Journal, 1965, 44, 2245–2269.CrossRefGoogle Scholar
Lin, S., & Kernighan, B. W. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 1973, 21, 498–516.CrossRefGoogle Scholar
Lin, S., & Kernighan, B. W. A heuristic technique for solving a class of combinatorial optimization problems. Proceedings of the 5th Annual Princeton Conference on Information Sciences and Systems, 1971, 210-213.Google Scholar
Little, J. D. C., Murty, K. G., Sweeney, D. W., & Karel, C. An algorithm for the traveling salesman problem. Operations Research, 1963, 11, 972-989.CrossRefGoogle Scholar
McCormick, W. T. Jr., Schweitzer, P. J., & White, T. W. Problem decomposition and data reorganization by a clustering technique. Operations Research, 1972, 20, 993-1009.CrossRefGoogle Scholar
Mensch, G. Single-stage linear programming zero-one solutions to some traveling salesman type problems. Infor, 1971, 9, 282-292.Google Scholar
Miller, C. E., Tucker, A. W., & Zemlin, R. A. Integer programming formulation of traveling salesman problems. Journal for the Association of Computing Machinery, 1960, 7, 326-329.CrossRefGoogle Scholar
Morton, G., & Land, A. H. A contribution to the “traveling salesman” problem. Journal of the Royal Statistical Society (Series B), 1955, 17, 185-194.CrossRefGoogle Scholar
Müller-Merbach, H. Optimalereihenfolgen, 1970, Berlin: Springer-Verlag.Google Scholar
Murty, K. G. On the tours of a traveling salesman. SIAM Journal on Control, 1969, 7, 122-131.CrossRefGoogle Scholar
Nicholson, T. A. J. A sequential method for discrete optimization problems and its application to the assignment, traveling salesman, and three machine scheduling problems. Journal of the Institute of Mathematics and its Applications, 1967, 3, 362-375.CrossRefGoogle Scholar
Nicholson, T. A. J. A boundary method for planar traveling salesman problems. Operational Research Quarterly, 1968, 19, 445-452.CrossRefGoogle Scholar
Nicholson, T. A. J. A method for optimizing permutation problems and its industrial applications. In Welsh, P. J. A. (Eds.), Combinatorial mathematics and its applications, 1971, New York: Academic Press.Google Scholar
Obruca, A. K. Spanning tree manipulation and the traveling salesman problem. The Computer Journal, 1968, 10, 374-377.CrossRefGoogle Scholar
Pandit, S. N. N. Some observations on the longest path problem. Operations Research, 1964, 12, 361-364.CrossRefGoogle Scholar
Raymond, T. C. Heuristic algorithm for the traveling salesman problem. IBM Journal of Research and Development, 1969, 13, 400-407.CrossRefGoogle Scholar
Reiter, S., & Sherman, G. Discrete optimizing. Journal of the Society for Industrial and Applied Mathematics, 1965, 13, 864-889.CrossRefGoogle Scholar
Roberts, S. M., & Flores, B. An engineering approach to the traveling salesman problem. Management Science, 1966, 13, 269–288.CrossRefGoogle Scholar
Rosencrantz, D. J., Stearns, R. E., & Lewis, P. M., Approximate algorithms for the traveling salesperson problem. Proceedings 15th Annual Symposium in Switching and Automata Theory, 1974, 33–42.CrossRefGoogle Scholar
Sagi, P. C. A statistical test for the significance of a coefficient of reproducibility. Psychometrika, 1959, 24, 19-27.CrossRefGoogle Scholar
Slagle, J. R., & Chang, C. L., Heller, S. R. A clustering and data-reorganizing algorithm. IEEE Transactions on Systems, Man, and Cybernetics, 1975, 5, 125-128.CrossRefGoogle Scholar
Slagle, J. R., Chang, C. L., & Lee, R. C. T. Experiments with some cluster analysis algorithms. Pattern Recognition, 1974, 6, 181-187.CrossRefGoogle Scholar
Solem, O. Contribution to the solution of sequencing problems in process industry. International Journal of Production Research, 1974, 12, 55-75.CrossRefGoogle Scholar
Steckhan, H. A theorem on symmetric traveling salesman problems. Operations Research, 1970, 18, 1163-1167.CrossRefGoogle Scholar
Steiglitz, K., & Weiner, P. Some improved algorithms for computer solution of the traveling salesman problem. Proceedings of the Allerton Conference on Circuit and System Theory, 1968, 6, 814-821.Google Scholar
Weiner, P., Savage, S. L., & Bagchi, A. Neighborhood search algorithms for finding optimal traveling salesman tours must be inefficient. Proceedings of the 5th Annual ACM Symposium on the Theory of Computing, 1973, 207-213.Google Scholar
Wilkinson, E. M. Archaeological seriation and the traveling salesman problem. In Hodson, F. R., Kendall, D. G., & Tautu, P. (Eds.), Mathematics in the archaeological and historical sciences, 1971, Edinburgh: Edinburgh University Press.Google Scholar
Wiorkowski, J. J., & McElvain, K. A rapid heuristic algorithm for the approximate solution of the traveling salesman problem. Transportation Research, 1975, 9, 181-185.CrossRefGoogle Scholar