Statistical Analysis of Subproblems Bound Distributions in the Branch-and-Bound Algorithm for Random Traveling Salesman Instances

Bo Zhang, Boris Melnikov

Abstract


The statistical properties of subproblem bounds in the Branch-and-Bound (B&B) method applied to the Traveling Salesman Problem (TSP) are investigated. While B&B is a classical exact approach for solving combinatorial optimization problems, the stochastic behavior of its subproblem boundaries under random instances remains largely unexplored. The analysis focuses on the random variable representing the difference between the left and right subproblem bounds. First, we derive and computationally verify the combinatorial count of all admissible reduction sequences for a five-by-five TSP matrix (10 total operations, 5 row and 5 column reductions), which equals 329462, using a Stirling-type formula. Second, we generate 1000 random asymmetric five-by-five TSP matrices and compute the full empirical distributions of the boundary for all possible reduction sequences, obtaining a family of 1000 distinct distributions. Finally, for larger ninety- nine-by-ninety-nine matrices, we employ a Monte Carlo sampling procedure to approximate 1000 distributions based on randomly selected reduction sequences. The results provide new insights into the internal statistical mechanisms of the B&B method and suggest potential pathways for developing adaptive or probabilistic branching heuristics based on empirical bound behavior.

Full Text:

PDF

References


G. B. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a Large-Scale Traveling-Salesman Problem,” RAND Research Memorandum P-510, Apr. 1954.

R. M. Karp, “Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. New York: Plenum, 1972, pp. 85–103.

C. H. Papadimitriou, “The Euclidean Travelling Salesman Prob-lem is NP-Complete,” Theoretical Computer Science, vol. 4, no. 3, pp. 237–244, 1977.

A. H. Land and A. G. Doig, “An Automatic Method of Solving Discrete Programming Problems,” Econometrica, vol. 28, no. 3, pp. 497–520, 1960.

E. L. Lawler and D. E. Wood, “Branch-and-Bound Methods: A Survey,” Operations Research, vol. 14, no. 4, pp. 699–719, 1966.

J. D. C. Little, K. G. Murty, D. W. Sweeney, and C. Karel, “An Algorithm for the Traveling Salesman Problem,” Operations Research, vol. 11, no. 6, pp. 972–989, 1963.

M. Padberg and G. Rinaldi, “A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Prob-lems,” SIAM Review, vol. 33, no. 1, pp. 60–100, 1991.

D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook, The Traveling Salesman Problem: A Computational Study. Princeton, NJ: Princeton Univ. Press, 2006.

D. Applegate, R. Bixby, V. Chvátal, and W. Cook, “Implementing the Dantzig–Fulkerson–Johnson Algorithm for Large Traveling Salesman Problems,” preprint, 2003.

B. F. Melnikov and E. A. Melnikova, “On the classical version of the branch-and-bound method,” Computer Tools in Education, 2021, pp. 1–25. (In Russ.; Eng. abstract).

M. Held and R. M. Karp, “The Traveling-Salesman Problem and Minimum Spanning Trees,” Operations Research, vol. 18, no. 6, pp. 1138–1162, 1970.

C. C. McGeoch, A Guide to Experimental Algorithmics. Cam-bridge, UK: Cambridge Univ. Press, 2012.

B. F. Melnikov, “Object-oriented implementation of the branch-and-bound method for the travelling salesman problem. Part I,” Modern Information Technologies and IT-Education, vol. 18, no. 2, 2022, pp. 287–299. doi: 10.25559/SITITO.18.202202.287-299. (In Russ.; Eng. abstract).

B. F. Melnikov, “Object-oriented implementation of the branch-and-bound method for the travelling salesman problem. Part II,” Modern Information Technologies and IT-Education, vol. 18, no. 3, 2022, pp. 644–654. doi: 10.25559/SITITO.18.202203.644-654. (In Russ.; Eng. abstract).

S. Lin and B. W. Kernighan, “An Effective Heuristic Algorithm for the Traveling-Salesman Problem,” Operations Research, vol. 21, no. 2, pp. 498–516, 1973.

J. Beardwood, J. H. Halton, and J. M. Hammersley, “The Shortest Path Through Many Points,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 55, no. 4, pp. 299–327, 1959.

D. S. Johnson and L. A. McGeoch, “The Traveling Salesman Problem: A Case Study in Local Optimization,” in Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra, Eds. Chichester, UK: Wiley, 1997, pp. 215–310.

G. Laporte, “The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms,” European Journal of Op-erational Research, vol. 59, no. 2, pp. 231–247, 1992.

B. Melnikov and D. Chaikovskii, “On the Application of Heu-ristics of the TSP for the Task of Restoring the DNA Matrix,” in Artificial Intelligence and Human-Computer Interaction, Y. Ye and P. Siarry, Eds. Amsterdam: IOS Press, 2024, FAIA, vol. 385, pp. 36–43.

B. Melnikov and D. Chaikovskii, “Some General Heuristics in the Traveling Salesman Problem and the Problem of Reconstructing the DNA Chain Distance Matrix,” in Proc. 7th Int. Conf. on Computer Science and Artificial Intelligence (CSAI 2023), Beijing, China. ACM, 2023, pp. 361–368.

B. Melnikov and Y. Terentyeva, “Mathematical Modeling of In-creasing the Level of Safety Using the Traveling Salesman Problem,” in Artificial Intelligence and Human-Computer Inter-action, Y. Ye and H. Zhou, Eds. Amsterdam: IOS Press, 2025, FAIA, vol. 404, pp. 801–(end).

C. P. Robert and G. Casella, Monte Carlo Statistical Methods, 2nd ed. New York: Springer, 2004.

H. W. Kuhn, “The Hungarian Method for the Assignment Prob-lem,” Naval Research Logistics Quarterly, vol. 2, no. 1–2, pp. 83–97, 1955.

R. Jonker and A. Volgenant, “A Shortest Augmenting Path Algo-rithm for Dense and Sparse Linear Assignment Problems,” Computing, vol. 38, no. 4, pp. 325–340, 1987.

J. Cirasella, D. S. Johnson, L. A. McGeoch, and W. Zhang, “The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests,” in Workshop on Algorithm Engineering and Experimentation, Springer, 2001, pp. 32–59.

D. S. Johnson, G. Gutin, L. A. McGeoch, A. Yeo, W. Zhang, and A. Zverovitch, “Experimental Analysis of Heuristics for the ATSP,” in The Traveling Salesman Problem and Its Variations, Springer, 2002, pp. 445–487.

C. Villani et al., Optimal Transport: Old and New, vol. 338, Springer, 2008.

V. M. Panaretos and Y. Zemel, An Invitation to Statistics in Wasserstein Space. Cham, Switzerland: Springer, 2020.

G. Gutin and A. P. Punnen, The Traveling Salesman Problem and Its Variations, vol. 12, Springer Science & Business Media, 2006.

Miller, Clair E., Albert W. Tucker, and Richard A. Zemlin. "Integer programming formulation of traveling salesman prob-lems." Journal of the ACM (JACM) 7.4 (1960): 326-329.

Desrochers, Martin, and Gilbert Laporte. "Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints." Operations Research Letters 10.1 (1991): 27-36.

N. Biggs, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley Online Library, 1986.

Hooker, John N. Integrated methods for optimization. Boston, MA: Springer US, 2007.

Lozier, Daniel W. "NIST digital library of mathematical func-tions." Annals of Mathematics and Artificial Intelligence 38.1 (2003): 105-119.

Graham, Ronald L., Donald E. Knuth, and Oren Patash-nik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Professional, 1994.

Székely, Gábor J., and Maria L. Rizzo. "Energy statistics: A class of statistics based on distances." Journal of statistical planning and inference 143.8 (2013): 1249-1272.

Sejdinovic, Dino, et al. "Equivalence of distance-based and RKHS-based statistics in hypothesis testing." The annals of sta-tistics (2013): 2263-2291.

Asadpour, Arash, et al. "An O (log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Prob-lem." SODA. 2010.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность Monetec 2026 СНЭ

ISSN: 2307-8162