Probabilistic Prediction of the Complexity of Traveling Salesman Problems Based on Approximating the Complexity Distribution from Experimental Data
- Authors: Goloveshkin V.A.1,2, Zhukova G.N.3, Ulyanov M.V.4,5, Fomichev M.I.3
-
Affiliations:
- Moscow Technological University
- Institute of Applied Mechanics
- National Research University Higher School of Economics
- Institute of Control Sciences
- Lomonosov State University
- Issue: Vol 79, No 7 (2018)
- Pages: 1296-1310
- Section: Optimization, System Analysis, and Operations Research
- URL: https://journals.rcsi.science/0005-1179/article/view/150963
- DOI: https://doi.org/10.1134/S0005117918070093
- ID: 150963
Cite item
Abstract
We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family of probability distributions that represent satisfactory approximations of the complexity distribution with a dimension of the cost matrix from 20 to 49. Our main objective is to make probabilistic predictions of the complexity of individual problems for larger values of the dimension of the cost matrix. We propose a representation of the complexity distribution that makes it possible to predict the complexity. We formulate the unification hypothesis and show directions for further study, in particular proposals on the task of clustering “complex” and “simple” ATSP problems and proposals on the task of directly predicting the complexity of a specific problem instance based on the initial cost matrix.
About the authors
V. A. Goloveshkin
Moscow Technological University; Institute of Applied Mechanics
Author for correspondence.
Email: nikshevolog@yandex.ru
Russian Federation, Moscow; Moscow
G. N. Zhukova
National Research University Higher School of Economics
Email: nikshevolog@yandex.ru
Russian Federation, Moscow
M. V. Ulyanov
Institute of Control Sciences; Lomonosov State University
Email: nikshevolog@yandex.ru
Russian Federation, Moscow; Moscow
M. I. Fomichev
National Research University Higher School of Economics
Email: nikshevolog@yandex.ru
Russian Federation, Moscow
Supplementary files
